图的遍历之深度优先搜索(DFS)

发布于:2021-07-20 06:54:51

1、深度优先遍历的过程


深度优先遍历类似于树的先序遍历,是树的先序遍历的推广。


对于一个连通图,深度优先搜索遍历的过程如下。


(1)从图中某个顶点v出发1,访问v。


(2)找到刚访问过的顶点的第一个未被访问过的邻接点,访问该顶点。以该顶点为新顶点,重


复此步骤,直到刚访问过的顶点没有未被访问的邻接点为止。


(3)返回前一个访问过的且仍有未被访问的邻接点的顶点,找出该顶点的下一个未被访问的


邻接点,访问该顶点。


(4)重复步骤(2)和(3)直到途中所有顶点都被访问过,搜索结束。


2.深度优先遍历的算法实现


显然,深度优先搜索遍历连通图是一个递归的过程。为了在遍历过程中便于区分顶点是否已


被访问,需要附设访问表标志数组visited[n],其初值为“false”,一旦某个顶点被访问,则其相


应的分量置为“true”。


算法描述



bool visited[MVNum] //访问标准数组,其初值为“false”
void DFS (Graph G,int v)
{//从第v个顶点出发递归地深度优先遍历图G
cout< for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
/*依次检查v的所有邻接点w,FirstAdjVex(G,v,w)表示v的第一个邻
接点;NextAdjVex(G,v,w)表示v相对于w的下一个邻接点,w>=
0表示存在邻接点*/
if(!visited[w]) DFS(G,w);//对v的尚未访问的邻接顶点w递归调用DFS
}

根据存储结构的不同,具体可以分为:


? ? ? ?①采用邻接矩阵表示图的深度优先搜索遍历



void DFS?AM(AMGraph G, int v)
{//G为邻接矩阵类型,从第v个顶点出发深度优先搜索遍历图G
cout< for(w=0; W if((G.arcs [v] [w]!=0)&&(!visited[w])) DFS_ AM(G, W);
//G.arcs[v][w]!=0表示w是v的邻接点,如果w未访问,则递归调用 DFS_AM
}

? ? ? ②采用邻接表表示图的深度优先搜索遍历



void DFS_AL(ALGraph G,int v)
{//图G为邻接表类型
cout< p=G.vertices[v].firstarc;//p指向v的边链表的第一个边结点
while(p!=NULL)//边结点非空
{
w=p->adjvex; //表示w是v的邻接点
if(!visited[w]) DFS_AL(G,w);//如果w未访问,递归
p=p->nextarc;// p指向下一个边结点3
}
}

谢谢阅读QAQ



转载于:https://www.cnblogs.com/Knight-Dark-The/p/11057013.html






相关资源:深度优先算法(DFS遍历有向无环寻找最优路径

相关推荐

最新更新

猜你喜欢