图的遍历算法 有两种 ：深度优先搜索遍历 和 广度 优先搜索遍历。深度优先搜索遍历类似与 树的 先序遍历。广度优先搜索遍历类似与树的层序遍历。只不过 图 可以有 不连通的 节点，所以 得 遍历 整个顶点数组。
深搜遍历 总是 先访问当前节点的邻接点，，而 广搜算法 是 先访问顶点的邻接点 要 先于 后访问顶点的邻接点 被 访问。
具体遍历顺序如下：
以下代码 以 图的 邻接多重表 为 基本结构进行 遍历。
首先更改 上节 的 查找 邻接点 和 下一个邻接点的 返回值，以及 邻接点的 代码 有误,少加了 一句：
if (next->iIndex == location2 || next->jIndex == location2){next = next->iIndex == location1 ? next->iNext : next->jNext;break;}next = next->iIndex == location1 ? next->iNext : next->jNext;
int firstAdj(AMLGraph g,int location){ArcNode * next = g.adjMuList[location].head->iNext;if (next != NULL){int index = next->iIndex == location ? next->jIndex : next->iIndex;return index;}return -1;}int nextAdj(AMLGraph g,int location1 ,int location2){ArcNode * next = g.adjMuList[location1].head->iNext;while (next != NULL){if (next->iIndex == location2 || next->jIndex == location2){next = next->iIndex == location1 ? next->iNext : next->jNext;break;}next = next->iIndex == location1 ? next->iNext : next->jNext;}if (next != NULL){int index = next->iIndex == location1 ? next->jIndex : next->iIndex;return index;}return -1;}
然后 是 深搜 和 广搜的 具体代码：void dfs(AMLGraph g,int i,bool * isVisitedArray){printf("%c",g.adjMuList[i].vexName);isVisitedArray[i] = true;for (int next = firstAdj(g,i); next != -1 ; next = nextAdj(g,i,next)){if (isVisitedArray[next] == false){dfs(g,next,isVisitedArray);}}}//深度优先搜索遍历void dfsTraver(AMLGraph g){bool isVisited[MAX_VEX_NUM] = {false};printf("———-深度优先遍历——————\n");for (int i = 0; i < g.vexNum; i++){if (isVisited[i] == false){dfs(g,i,isVisited);}}printf("\n");}//广度优先搜索遍历void bfsTraverse(AMLGraph g){bool isVisited[MAX_VEX_NUM] = {false};printf("———-广度优先遍历——————\n");LinkQueue queue;queueInit(&queue);for (int i = 0; i < g.vexNum; i++){if (isVisited[i] == false){printf("%c",g.adjMuList[i].vexName);isVisited[i] = true;enqueue(&queue,i);while (!queueEmpty(queue)){int top;dequeue(&queue,&top);for (int next = firstAdj(g,top);next != -1 ; next = nextAdj(g,top,next)){if (isVisited[next] == false){printf("%c",g.adjMuList[next].vexName);isVisited[next] = true;enqueue(&queue,next);}}}}}queueDestory(&queue);}完整 源代码如下：
广搜用到的链队代码没有放进来，想看的 可以 进网盘地址 下载 工程文件。
工程文件网盘地址：点击打开链接
// AMLGraph.cpp : 定义控制台应用程序的入口点。//无向图的邻接多重表#include "stdafx.h"#include <cstdlib>#include "queue.h"#define MAX_VEX_NUM 20enum E_VisitIf{unvisited = 0,visited = 1,};struct ArcNode{E_VisitIf mark;int iIndex,jIndex;//顶点i,j在图中的位置ArcNode * iNext;//与i顶点点相关的下一个弧ArcNode * jNext;//与j顶点点相关的下一个弧};struct VNode{char vexName;ArcNode * head;//头指针};struct AMLGraph{VNode adjMuList[MAX_VEX_NUM];//顶点数组int vexNum,arcNum;};//获取弧 的 头节点ArcNode * getHeadNode(){ArcNode * pNode = (ArcNode *)malloc(sizeof(ArcNode));if (pNode){pNode->iIndex = pNode->jIndex = -1;pNode->iNext = pNode->jNext = NULL;pNode->mark = unvisited;}return pNode;}ArcNode * getArcNode(int iIndex,int jIndex){ArcNode * pNode = getHeadNode();if (pNode){pNode->iIndex = iIndex;pNode->jIndex = jIndex;}return pNode;}int vexLocation(AMLGraph g,char vex){for (int i = 0; i < g.vexNum; i++){if (g.adjMuList[i].vexName == vex){return i;}}return -1;}void createGrahp(AMLGraph * g){printf("输入图的顶点数 和 边（弧）数\n");scanf("%d%d%*c",&g->vexNum,&g->arcNum);//构造顶点集printf("请输入顶点集\n");for (int i = 0; i < g->vexNum; i++){char name;scanf("%c",&name);g->adjMuList[i].vexName = name;g->adjMuList[i].head = getHeadNode();//建立 头节点，并让头指针指向头节点}//构造顶点关系fflush(stdin);printf("请输入顶点的关系\n");for (int i = 0; i < g->arcNum; i++){char vex1,vex2;scanf("%c%c%*c",&vex1,&vex2);int location1 = vexLocation(*g,vex1);int location2 = vexLocation(*g,vex2);ArcNode * pNode = getArcNode(location1,location2);pNode->iNext = g->adjMuList[location1].head->iNext;g->adjMuList[location1].head->iNext = pNode;pNode->jNext = g->adjMuList[location2].head->iNext;g->adjMuList[location2].head->iNext = pNode;} }void destoryGraph(AMLGraph * g){for (int i = 0; i < g->vexNum; i++){ArcNode * next = g->adjMuList[i].head->iNext;while (next != NULL){ArcNode * freeNode = next;next = next->iIndex == i ? next->iNext : next->jNext;if (freeNode->iIndex == i){////只释放 iIndex 等于 i的节点,要不会多次释放free(freeNode);}}free(g->adjMuList[i].head);g->adjMuList[i].head = NULL;g->adjMuList[i].vexName = ' ';g->vexNum = g->arcNum = 0;}}//顶点vex1 和顶点vex2 是否相邻bool graphIsAdj(AMLGraph g,char vex1,char vex2){int location = vexLocation(g,vex1);ArcNode * next = g.adjMuList[location].head->iNext;while (next != NULL){if (g.adjMuList[next->iIndex].vexName == vex2 || g.adjMuList[next->jIndex].vexName == vex2){return true;}next = next->iIndex == location ? next->iNext : next->jNext;}return false;}int graphDegree(AMLGraph g,char vex){int degree = 0;int location = vexLocation(g,vex);ArcNode * next = g.adjMuList[location].head->iNext;//计算所有出度while (next != NULL){degree++;next = next->iIndex == location ? next->iNext : next->jNext;}return degree;}//插入边（弧）void insertArc(AMLGraph * g,char vex1,char vex2){int location1 = vexLocation(*g,vex1);int location2 = vexLocation(*g,vex2);ArcNode * node = getArcNode(location1,location2);node->iNext = g->adjMuList[location1].head->iNext;g->adjMuList[location1].head->iNext = node;node->jNext = g->adjMuList[location2].head->iNext;g->adjMuList[location2].head->iNext = node;g->arcNum ++;}//删除边（弧）void deleteArc(AMLGraph * g,char vex1,char vex2){g->arcNum–;int location1 = vexLocation(*g,vex1);int location2 = vexLocation(*g,vex2);ArcNode * next = g->adjMuList[location1].head->iNext;ArcNode * pre = g->adjMuList[location1].head;while (next != NULL){if (next->iIndex == location2){if (pre == g->adjMuList[location1].head || pre->iIndex == location1){//删除的是第一个节点.或者 前驱的index = location1pre->iNext = next->jNext;}else{pre->jNext = next->jNext;}break;}else if(next->jIndex == location2){if (pre == g->adjMuList[location1].head || pre->iIndex == location1){//删除的是第一个节点.或者 前驱的index = location1pre->iNext = next->iNext;}else{pre->jNext = next->iNext;}break;}pre = next;next = next->iIndex == location1 ? next->iNext : next->jNext;}next = g->adjMuList[location2].head->iNext;pre = g->adjMuList[location2].head;while (next != NULL){if (next->iIndex == location1){if (pre == g->adjMuList[location2].head || pre->iIndex == location2){//删除的是第一个节点.或者 前驱的index = location1pre->iNext = next->jNext;}else{pre->jNext = next->jNext;}free(next);break;}else if(next->jIndex == location1){if (pre == g->adjMuList[location2].head || pre->iIndex == location2){//删除的是第一个节点.或者 前驱的index = location1pre->iNext = next->iNext;}else{pre->jNext = next->iNext;}free(next);break;}pre = next;next = next->iIndex == location2 ? next->iNext : next->jNext;}}//插入顶点void insertVex(AMLGraph * g, char vex){if (g->vexNum < MAX_VEX_NUM){g->adjMuList[g->vexNum].vexName = vex;g->adjMuList[g->vexNum].head = getHeadNode();g->vexNum++;}}//删除顶点void deleteVex(AMLGraph * g,char vex){int location = vexLocation(*g,vex);//删除顶点 同样需要 遍历整个 图 查找 与 vex 相关的弧节点for (int i = 0; i < g->vexNum; i++){ArcNode * next = g->adjMuList[i].head->iNext;while (next != NULL){if (next->iIndex == location || next->jIndex == location){ArcNode * delNode = next;next = next->iIndex == location ? next->iNext : next->jNext;char delData1 = g->adjMuList[delNode->iIndex].vexName;char delData2 = g->adjMuList[delNode->jIndex].vexName;deleteArc(g,delData1,delData2);}else{next = next->iIndex == location ? next->iNext : next->jNext;}}}//更改因删除顶点 而导致的元素位置变化..for (int i = 0; i < g->vexNum; i++){ArcNode * next = g->adjMuList[i].head->iNext;while (next != NULL){if (next->iIndex == i){if(next->iIndex > location){next->iIndex –;}if(next->jIndex > location){next->jIndex –;}}next = next->iIndex == location ? next->iNext : next->jNext;}}free(g->adjMuList[location].head);//释放头节点//vex下面的 顶点上移for (int i = location + 1; i < g->vexNum; i++){g->adjMuList[i-1] = g->adjMuList[i];}g->vexNum –;}void printGrahp(AMLGraph g){for (int i = 0; i < g.vexNum; i++){printf("%c的 邻接点有：",g.adjMuList[i].vexName);ArcNode * next = g.adjMuList[i].head->iNext;//删除所有弧尾while (next != NULL){int index = next->iIndex == i ? next->jIndex : next->iIndex;printf("%c",g.adjMuList[index].vexName);next = next->iIndex == i ? next->iNext : next->jNext;}printf("\n");}}int firstAdj(AMLGraph g,int location){ArcNode * next = g.adjMuList[location].head->iNext;if (next != NULL){int index = next->iIndex == location ? next->jIndex : next->iIndex;return index;}return -1;}int nextAdj(AMLGraph g,int location1 ,int location2){ArcNode * next = g.adjMuList[location1].head->iNext;while (next != NULL){if (next->iIndex == location2 || next->jIndex == location2){next = next->iIndex == location1 ? next->iNext : next->jNext;break;}next = next->iIndex == location1 ? next->iNext : next->jNext;}if (next != NULL){int index = next->iIndex == location1 ? next->jIndex : next->iIndex;return index;}return -1;}void dfs(AMLGraph g,int i,bool * isVisitedArray){printf("%c",g.adjMuList[i].vexName);isVisitedArray[i] = true;for (int next = firstAdj(g,i); next != -1 ; next = nextAdj(g,i,next)){if (isVisitedArray[next] == false){dfs(g,next,isVisitedArray);}}}//深度优先搜索遍历void dfsTraver(AMLGraph g){bool isVisited[MAX_VEX_NUM] = {false};printf("———-深度优先遍历——————\n");for (int i = 0; i < g.vexNum; i++){if (isVisited[i] == false){dfs(g,i,isVisited);}}printf("\n");}//广度优先搜索遍历void bfsTraverse(AMLGraph g){bool isVisited[MAX_VEX_NUM] = {false};printf("———-广度优先遍历——————\n");LinkQueue queue;queueInit(&queue);for (int i = 0; i < g.vexNum; i++){if (isVisited[i] == false){printf("%c",g.adjMuList[i].vexName);isVisited[i] = true;enqueue(&queue,i);while (!queueEmpty(queue)){int top;dequeue(&queue,&top);for (int next = firstAdj(g,top);next != -1 ; next = nextAdj(g,top,next)){if (isVisited[next] == false){printf("%c",g.adjMuList[next].vexName);isVisited[next] = true;enqueue(&queue,next);}}}}}queueDestory(&queue);}//邻接多重表int _tmain(int argc, _TCHAR* argv[]){AMLGraph g;createGrahp(&g);printGrahp(g);dfsTraver(g);bfsTraverse(g);return 0;}运行截图：你挤进地铁时，西藏的山鹰一直盘旋云端，
