所谓深度优先:从图中某个初始顶点v出发,首先访问初始顶点v,然后选择一个与顶点v相邻且没被访问过的顶点w为初始顶点,再从w出发进行深度优先搜索,直到图中与当前顶点v邻接的所有顶点都被访问过为止。显然,这个遍历过程是个递归过程。
对于一个无向图的深度优先访问,需要注意,每条边被访问了两次,对边的第一次访问v-w,存在两种情况:第一种直接进行w的递归调用,因为w没有访问过;第二种情况是w已经被访问过,忽略对w的调用。需要注意的是第二种情况下,v-w是形成了一个回边,也就是说,实际上与原来的递归调用路径形成了一个环。这点很有用。对边的第二次访问,都忽略递归调用,也存在两种情况,第一种是访问的节点是其父节点;第二种是访问的节点的递归调用已经完成,而本节点还在进行递归调用。
总结一句话:边分为树边(进行递归调用的边)和回边(不进行递归调用的边,形成环的边)。根据访问次数,可以分为四种链接:树链接,父链接(树边的两次访问);回链接,下链接(回边的对应的两次访问)。
怎么来识别这些边呢?因为树的递归调用,在调用前,我们使用一个数组ord来记录调用的秩序,类似树的前序遍历,再使用一个数组st来记录每条递归调用边的父节点。通过这两个数组就可以识别上面的边的两次访问情况。
对于每次边的调用v-w
1) ord[w]=-1,那么v-w是树链接,进行递归调用。
2) ord[w]<ord[v],说明w已经原来进行访问过,如果st[v]=w,则v-w是父链接。否则是回链接。(既然是回链接,则指向的节点肯定已经先访问过)。
3) ord[w]>ord[v],则v-w是下链接,w节点的递归调用已经完成,v节点还在进行。
DFS的应用:
1) 环的检测,这个是很容易。根据上面的分析,判断是否是回链接就可以实现。
2) 可分离图:就是说图中存在桥(一个桥是一条特定的边,可以把一个连通图分解为不相交的两个子图)的图。根据DFS的边的特性的分析,回边是不可能是桥。桥v-w有个特性,对于节点w,没有一条回边将其子孙与其某个祖先相连。可以使用一个数组来记录节点w为根的的子树中任何回边所引用的最小前序编号(ord值)。
public void dfs (int v) {
ord[v] = cnt++;
low[v] = ord[v];
for (int w : G.adj(v)) {
if (ord[w] == -1) {
st[w] = v;
dfs2(w);
/**
* 访问完一个节点后,看这个节点子树中回边指向的最小祖先节点
*/
if (low[v] > low[w])
low[v] = low[w];
/**
* 一个节点回边指向的最先祖先节点是其本身,那么这条边是桥
*/
if (low[w] == ord[w]) {
System.out.println(v + "-------------------->" + w
+ " is bridge!");
}
} else
if (st[v] != w && ord[w] < ord[v]) {
/**
* 节点v的子节点的回边的节点小于本节点记录值
*/
if (low[v] > ord[w])
low[v] = ord[w];
}
}
}
3)图的连通性。
分享到:
相关推荐
求无向图的深度优先生成树和广度优先生成树
以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集。 注: 1.代码共182行。 2.代码经过多次编译运行,无错误。
无向图的宽度优先搜索算法和深度优先搜索算法,c++实现
程序设计任务: 设计一个程序,实现以邻接表或者邻接矩阵为存储结构,实现连通无向图的深度优先和广度优先遍历。基本要求:以邻接表或者邻接矩阵为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的...
通过键盘输入图的顶点,以及每一条边的两个顶点,从而建立无向图。实现无向图的深度优先遍历算法。要求以用户给定的结点为起始点,显示深度优先遍历次序。
无向图建立、深度优先遍历和广度优先遍历实现算法[借鉴].pdf
采用深度优先算法(DFS)遍历有向无环图寻找最优路径,经过优化的深度优先算法,在遍历有向无环图的时候保存路径,并计算路径权值,最总返回最优路径及最有路径的权值
无向图的深度优先搜索和广度优先搜索,即DFS和BFS算法
数据结构课程中的深度优先搜索算法、广度优先搜索算法的C语言程序,在Turbo C 2.0上调试通过。
创建一个无向图,输出一个无向图,求出此图的广度、深度优先的算法~~~~~
有向图的算法中包括:广度优先算法 、深度优先搜索、普利姆算法、克鲁斯卡尔算法以及有向图到无向图的转化;无向图的算法中包括:弗洛伊德算法、拓扑排序算法、迪杰斯特拉;在四类存储方式各自算法中,都包括了:...
无向图的连接表存储结构的创建算法 从编号为v的顶点出发,深度优先遍历图的算法 对具有G.vexnum个顶点的图的深度优先遍历的算法 从图G的v顶点出发,广度优先遍历图的算法 对具有G.vexnum个顶点的图的广度优先遍历的...
图的遍历算法:深度优先搜索遍历和广度优先搜索遍历,利用栈的基本操作编写,与树的遍历相似,它们对无向图和有向图均适用。
无向图的深度优先搜索算法/c语言实现 其中图采用邻接矩阵存储
c数据结构链表数组以及深度优先遍历,假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点),则深度优先遍历可定义如下:首先访问出发点v,并将其标记为已访问过;然后依次从v出发搜索v的...
里面有有向图的创建,还有无向图的创建,还有自定义无向图的创建,还有广度优先便利和深度优先便利。 如果和我初学的小伙伴一样敲不出来可以瞅一瞅 刚刚我注释的很全,分开写的。反正不要钱多少看一点!对应的文章我...
基于C的无向图连通分支的算法解决 通过深度优先算法实现
1.键盘输入数据,...采用邻接表存储实现无向图的深度优先非递归遍历。 3. 采用邻接表存储实现无向图的广度优先遍历。 4.采用邻接矩阵存储一个无向图。 5.采用邻接矩阵存储实现无向图的最小生成树的PRIM算法。
使用邻接表表示法创建无向图,然后使用非递归算法进行深度优先遍历和广度优先遍历
对于一个无向连通图,从图中某一顶点出发,...然而图的深度优先搜索(DFS)算法一般采用递归算法来实现,鉴于二叉树遍历算法可以转换为非递归算法来实现,试编写基于DFS的非递归遍历算法的无向图的连通分量的识别程序。