商城网站建设注意什么,网站的外链,网页文字模板,wordpress手机端在哪里调图的遍历1.连通图的深度优先搜索1.1. 递归1.2.非递归2.连通图的广度优先遍历3. 非连通图的深度#xff08;广度#xff09;优先遍历1.连通图的深度优先搜索
算法思想#xff1a;从图中某个顶点vi出发#xff0c;访问此顶点#xff0c;然后依次从v1的各个未被访问的邻接点…
图的遍历1.连通图的深度优先搜索1.1. 递归1.2.非递归2.连通图的广度优先遍历3. 非连通图的深度广度优先遍历1.连通图的深度优先搜索
算法思想从图中某个顶点vi出发访问此顶点然后依次从v1的各个未被访问的邻接点出发进行深度优先搜索来遍历图直至所有与v1所有路径想通的顶点都被访问到为止。 【算法描述】
访问顶点v从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(w0)//栈顶出栈{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和j1的顶点有联系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和j1的顶点有联系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-adjvex1;}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的所有未被访问过的邻接点之后按这些顶点被访问的先后依次访问它们的邻接结点。 【算法描述】
访问初始顶点并将其顶点编号入队列。队列不为空则队头顶点编号出队列依次访问它的每一个未访问过的邻接点并将其顶点编号入队列。重复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[w1] 0){printf(%d , G-vexs[w]);visited[w1] 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);广度}
}
