图的遍历算法

1.连通图的深度优先搜索

算法思想：从图中某个顶点vi出发，访问此顶点，然后依次从v1的各个未被访问的邻接点出发进行深度优先搜索来遍历图，直至所有与v1所有路径想通的顶点都被访问到为止。
【算法描述】

1. 访问顶点v
2. 从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历，如此深入下去，当某个顶点的所有邻接点都被访问过时，返回上一层，继续上一层中未被访问的顶点进行深度优先遍历，直至图中所有和v有路径想通的顶点都被访问为止

1.1. 递归

【深度遍历递归】

//基于邻接矩阵的连通图的深度优先遍历递归算法
void df_traver_MGraph(const MGraph* G, int v, int visited[])
{//G的存储结构为矩阵，v为出发编号，标志数组已经初始化为0printf("%d ", G->vexs[v]);//访问出发结点visited[v] = 1;//做已访问标记for (int w = 0; w < G->vexNum; w++){//查找和结点v有邻接关系的结点wif (G->arcs[v][w] != 0 && visited[w] == 0)df_traver_MGraph(G, w, visited);}
}
//基于邻接表的连通图的深度优先遍历递归算法
void df_traver_ALGraph(const ALGraph* G, int v, int visited[])
{//G的存储结构为邻接表，v为出发点编号，标记数组已经初始化为0printf("%d ", G->adjlist[v].vertex);//访问出发结点visited[v] = 1;//做已访问标记ArcNode* p = G->adjlist[v].firstArc;//得到边链表的头指针while (p)//查找与v有邻接关系的邻接点{int w = p->adjvex;//w是v的邻接点if (visited[w] == 0)df_traver_ALGraph(G, w, visited);//递归调用p = p->nextArc;}
}

对于先访问的顶点，其深度优先遍历后结束；后访问的顶点，其深度优先遍历先结束。所以，深度优先遍历可以用栈的结构来进行非递归遍历。
关键：是要找进行深度优先遍历的下一个邻接结点的位置。

1.2.非递归

//基于邻接矩阵的连通图的深度优先遍历非递归算法
void df_traver_no_MGraph(const MGraph* G, int v)
{//MGraph是图的邻接矩阵数据类型，从顶点v出发，深度优先遍历连通图Gassert(G);Stack S; StackInit(&S);//创建栈int visited[20] = { 0 };//标记数组，判断结点是否被访问过//初始化标记数组for (int i = 0; i < 20; i++)visited[i] = 0;//访问出发标号为v的结点printf("%d ", G->vexs[v-1]);//设置标号为v的结点已经被访问visited[v] = 1;//出发结点进栈StackPush(&S, v);//寻找v的第一个邻接结点标号int w = FirstAdjVex_MGraph(G, v);while (!StackEmpty(&S))//栈为空的时候，说明所有结点访问{if (w != 0 && visited[w] == 0)//w存在且，标号为w的结点没有被访问过{printf("%d ", G->vexs[w - 1]);visited[w] = 1;StackPush(&S, w);//编号w进栈}else if(w==0)//栈顶出栈{if (StackEmpty(&S))break;v = StackTop(&S);StackPop(&S);w = FirstAdjVex_MGraph(G, v);continue;}w = NextAdjVex_MGraph(G, v, w);//找v的下一个邻接点编号}//销毁栈StackDestroy(&S);
}
/****************************************************/
//基于邻接表的连通图的深度优先遍历非递归算法
void df_traver_no_AlGraph(const ALGraph* G, int v)
{//ALGraph是图的邻接表数据类型，从顶点v出发，深度优先遍历连通图Gassert(G);Stack S; StackInit(&S);//创建栈int visited[20] = { 0 };//标记数组，判断结点是否被访问过//初始化标记数组for (int i = 0; i < 20; i++)visited[i] = 0;//访问出发标号为v的结点printf("%d ", G->adjlist[v-1].vertex);//设置标号为v的结点已经被访问visited[v] = 1;//出发结点进栈StackPush(&S, v);//寻找v的第一个邻接结点标号int w = FirstAdjVex_ALGraph(G, v);while (!StackEmpty(&S))//栈为空的时候，说明所有结点访问{if (w != 0 && visited[w] == 0)//w存在且，标号为w的结点没有被访问过{printf("%d ", G->adjlist[w - 1].vertex);visited[w] = 1;StackPush(&S, w);//编号w进栈}else if (w == 0)//栈顶出栈{if (StackEmpty(&S))break;v = StackTop(&S);StackPop(&S);w = FirstAdjVex_ALGraph(G, v);continue;}w = NextAdjVex_ALGraph(G, v, w);//找v的下一个邻接点编号}//销毁栈StackDestroy(&S);
}//基于领接矩阵，寻找顶点v第一个领接顶点w标号
int FirstAdjVex_MGraph(const MGraph* G, int v)
{assert(G);int j = 0;for (j = 0; j < G->vexNum; j++){if (G->arcs[v - 1][j] != 0)//坐标为第一个非0，说明顶点v和j+1的顶点有联系return j + 1;//返回第一个与顶点v有联系的邻接结点编号，下标＋1}return 0;//不存在则返回0
}
//基于邻接矩阵，寻找顶点v的下一个邻接顶点编号
int NextAdjVex_MGraph(const MGraph* G, int v, int w)
{assert(G);int j = 0;for (j = w; j < G->vexNum; j++)//从一个邻接结点编号的下一个编号开始寻找{if (G->arcs[v - 1][j] != 0)//坐标为下一个非0，说明顶点v和j+1的顶点有联系return j + 1;//返回第一个与顶点v有联系的邻接结点编号，下标＋1}return 0;//不存在则返回0
}
//基于邻接表，寻找顶点v第一个领接顶点w
int FirstAdjVex_ALGraph(const ALGraph* G, int v)
{assert(G);if (G->adjlist[v - 1].firstArc != NULL){return G->adjlist[v - 1].firstArc->adjvex+1;}return 0;
}
//基于邻接表，寻找顶点v的下一个邻接顶点编号
int NextAdjVex_ALGraph(const ALGraph* G, int v, int w)
{assert(G);ArcNode* p = G->adjlist[v - 1].firstArc;while (p){if (p->adjvex + 1 == w)//找到存放编号为w的边结点break;p = p->nextArc;}if (!p || !p->nextArc)return 0;//没有找到w的下一个邻结点编号else{return p->nextArc->adjvex;}
}

2.连通图的广度优先遍历

算法思想：从图中的某个顶点出发，访问此顶点之后，依次访问v的所有未被访问过的邻接点，之后按这些顶点被访问的先后依次访问它们的邻接结点。
【算法描述】

1. 访问初始顶点，并将其顶点编号入队列。
2. 队列不为空，则队头顶点编号出队列；依次访问它的每一个未访问过的邻接点，并将其顶点编号入队列。
3. 重复2，直至队列为空，遍历结束。

【算法实现】

//基于邻接矩阵的连通图的广度优先遍历算法
void bf_traver_MGraph(const MGraph* G, int v)
{int visited[10] = { 0 };//队列Q存放已经访问过的顶点编号，v为出发点编号Queue Q; QueueInit(&Q);//访问出发结点，将出发结点编号进队列printf("%d ", G->vexs[v - 1]);visited[v] = 1;QueuePush(&Q, v);while (!QueueEmpty(&Q)){int u = QueueFront(&Q); QueuePop(&Q);for (int w = 0; w < G->vexNum; w++)//找出u的所有邻接结点{if (G->arcs[u - 1][w] != 0 && visited[w+1] == 0){printf("%d ", G->vexs[w]);visited[w+1] = 1;QueuePush(&Q, w);}}}
}
//基于邻表的连通图的广度优先遍历算法
void bf_traver_ALGraph(const ALGraph* G, int v)
{int visited[10] = { 0 };//队列Q存放已经访问过的顶点编号，v为出发点编号Queue Q; QueueInit(&Q);//访问出发结点，将出发结点编号进队列printf("%d ", G->adjlist[v - 1].vertex);visited[v] = 1;QueuePush(&Q, v);while (!QueueEmpty(&Q)){int u = QueueFront(&Q); QueuePop(&Q);ArcNode* p = G->adjlist[u - 1].firstArc;while (p != NULL)//找出u的所有邻接点{int w = p->adjvex;//取邻接点编号if (visited[w + 1] == 0){printf("%d ", G->adjlist[w].vertex);visited[w + 1] = 1;QueuePush(&Q, w + 1);}p = p->nextArc;}}
}

3. 非连通图的深度（广度）优先遍历

对每一个未被访问过的顶点进行深度（广度）优先遍历
【算法实现】

//非连通图的深度（广度）优先遍历
void traver(const MGraph* G)
{assert(G);int visited[10] = { 0 };for (int i = 0; i < G->vexNum; i++){if (visited[i] == 0)df_traver_MGraph(G, i, visited);//深度//bf_traver_MGraph(&G, i + 1);广度}
}