采用DFS算法实现逆拓扑排序,并判断是否有回路

这篇具有很好参考价值的文章主要介绍了采用DFS算法实现逆拓扑排序,并判断是否有回路。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

问题描述

逆拓扑排序dfs实现算法考虑回路,笔记,算法,深度优先,数据结构
看王道视频的时候,有一道思考题,没有找到理想的答案,所以自己思考了一下,记录一下。
问题问的是:在采用DFS算法实现AOV网的逆拓扑排序时如何判断是否有回路?

思路分析

首先,要理解,在采用DFS算法(深度优先搜索)实现AOV网的拓扑排序,其本质上是对AOV网的DFS生成森林进行中序遍历,也就是相当于对生成森林中的每一棵树进行后根遍历。在对森林中每一棵树进行后根遍历产生的序列就是对AOV网的逆拓扑排序。
例如下面这张AOV网:

逆拓扑排序dfs实现算法考虑回路,笔记,算法,深度优先,数据结构
其DFS生成森林为逆拓扑排序dfs实现算法考虑回路,笔记,算法,深度优先,数据结构
对每一棵树进行后根遍历,得到的序列为2,3,1,0,4,5,也就是AOV网的逆拓扑排序。依次选取图中出度为0的顶点,再删除邻接到该顶点的边(也就是箭头指向该顶点的边),再选取图中出度为0的顶点,直到所有顶点都选过一遍,这样也可以得到上面的逆拓扑排序序列。
所以,在对DFS生成森林中每一棵树进行后根遍历产生的序列就是对AOV网的逆拓扑排序。
现在,DFS生成森林中的边肯定是图中已有的边,现在将图中的其他边表示在DFS生成森林中,如下图所示
逆拓扑排序dfs实现算法考虑回路,笔记,算法,深度优先,数据结构
其实自己试一下,可以发现当图中没有回路时,图中其他不在DFS生成森林当中的弧加到森林中,这些弧都是从右边的子树指向其左边的子树或者是从某结点指向其子孙结点的,可以自己试一下。这也可以解释为什么对DFS生成森林的中序遍历,也就是对森林中每棵树的后根遍历,与逆拓扑排序的思想是一致的。
这里补充一下逆拓扑排序的思想吧
逆拓扑排序:
1.从AOV网中选择一个没有后继(出度为0)的顶点并输出。
2.从网中删除该顶点和所有以它为终点的有向边。
3.重复1和2直到当前的AOV网为空。
出度为0的顶点也就是没有后驱活动的或者后驱活动都已经完成的顶点,本身AOV网就是用顶点表示活动。

对每棵树的后根遍历都是从下往上,从左往右,这样选取的顶点的后驱活动都已经完成了,也就是出度为0的顶点。
上面说,AOV网中其他的,不在DFS生成森林当中的弧加到DFS生成森林中后,这些弧都是从右边的子树指向其左边的子树或者是从某结点指向其子孙结点的,也就是右边的子树的结点的后驱活动只可能在左边的子树里或者其子孙,那么按照对DFS生成森林中每棵树的后根遍历,就能保证每次遍历的结点,它的后驱活动都已经完成了或者它没有后驱活动。

有些啰嗦了,下面进入正题。
什么时候说明AOV网中有回路呢?
如果在DFS的生成森林中的生成树中,出现一条从顶点u到顶点v的回边,且u在生成树上是v的子孙,则AOV网中必定存在包含顶点v和顶点u的环。
也就是说生成树中(此时说的生成树,是指AOV网中不在DFS生成森林当中的弧加到了DFS生成森林中后的树)有子孙到祖先的弧,则说明有回路。
可以用一个isPointed[]数组记录该结点是否被其子孙指向,也就是:是否有其子孙到该结点的弧。
每访问一个结点时,将其指向的结点的isPointed[]设为true。
利用对树的后根遍历,每当从其所有子孙返回时,判断是否有子孙指向该结点,即if(isPointed[v]==true),若有子孙指向该结点,则说明有回路。
首先将根结点作为祖先结点,看是否有子孙指向它,再将根结点的第一个孩子作为祖先结点,看是否有其子孙指向它,其实这里是树的先根遍历的思想,只要把visit();函数放在最前面。
将各结点当做祖先结点,也就是isPointed[]设置为false.

代码实现

下面是C语言的代码

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
//图的存储结构
//邻接矩阵表示法 
#define MaxVertexNum 5 //顶点数目的最大值
typedef struct{
	int Vertex[MaxVertexNum];//顶点 
	int Edge[MaxVertexNum][MaxVertexNum];//边的权 ,或者无权图0/1 
	int vexnum,arcnum;//图的当前顶点数和弧数 
}MGraph;
//采用DFS算法实现逆拓扑排序
//AOV网是有向无环图 
//要判断是否有环
//全局变量 
bool  visited[MaxVertexNum];//访问标记数组,初始都为false,全局变量
bool isPointed[MaxVertexNum];//初始都为false,用于记录当前结点是否被指向
bool flag=0;//用来标记是否出现了回路
int count=0;//用来记录已经输出的顶点个数
int print[MaxVertexNum];//保存要输出的顶点 

int FirstNeighbor(MGraph G,int v);//返回图G中顶点V的第一个邻接点,若有则返回该邻接点的序号,否则返回-1
int NextNeighbor(MGraph G,int v,int w);//返回图G中顶点v在顶点w之后的下一个邻接点,若有则返回该邻接点序号,否则返回-1 
void DFS(MGraph G,int v);

void DFSTraverse(MGraph G){//对图G进行深度优先遍历 
    int i;
    for(i=0;i<G.vexnum;i++){
    	visited[i]=false;//初始化已访问标记数据 
    	isPointed[i]=false;
	} 
	for(i=0;i<G.vexnum;i++){
		if(!visited[i])
		DFS(G,i);
	}
	if(flag==1){
		printf("有回路,输出逆拓扑排序失败\n");
	}
	else{
	    printf("逆拓扑排序为:\n");
		for(i=0;i<G.vexnum;i++){
	    	printf("%d\n",print[i]);//打印逆逆拓扑排序 
		} 
	}
}
void DFS(MGraph G,int v){//从顶点v出发,深度优先遍历图G 
	if(flag==1) return;//说明有回路,逐层返回 
	visited[v]=true;//设已访问标志 
	isPointed[v]=false;//将结点v当做祖先结点 
	for(int w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){ 
	   isPointed[w]=true;//将v指向的结点w的isPointed[]都设置为ture 
	   if(!visited[w]) DFS(G,w);//w为v的尚未访问的邻接顶点 
    }
    if(isPointed[v]==true) flag=1;//说明出现了回路 
    print[count++]=v;//将该顶点加入打印数组中 
}
//int FirstNeighbr(MGraph G,int v);返回图G中顶点V的第一个邻接点,若有则返回该邻接点的序号,否则返回-1
int FirstNeighbor(MGraph G,int v){
	for(int i=0;i<G.vexnum;i++){
		if(G.Edge[v][i]==1) return i;
	}
	return -1;
}
//int NextNeighbor(MGraph G,int v,int w);返回图G中顶点v在顶点w之后的下一个邻接点,若有则返回该邻接点序号,否则返回-1 
int NextNeighbor(MGraph G,int v,int w){
	for(int i=w+1;i<G.vexnum;i++){
		if(G.Edge[v][i]==1) return i;
	}
	return -1;
}
int main(){
	MGraph G;
	int i,j;
	for(i=0;i<MaxVertexNum;i++){
		for(j=0;j<MaxVertexNum;j++){
		   G.Edge[i][j]=0;
		}   
	}
	G.arcnum=5;
	G.vexnum=5;
	G.Edge[0][1]=1;
	G.Edge[0][3]=1;
	G.Edge[1][3]=1;
	G.Edge[2][1]=1;
	G.Edge[3][2]=1;
	G.Edge[4][3]=1;
	G.Edge[4][2]=1;
	DFSTraverse(G); 
	return 0;
}

测试结果:
用下面有回路的AOV网测试,可以判断有回路
逆拓扑排序dfs实现算法考虑回路,笔记,算法,深度优先,数据结构逆拓扑排序dfs实现算法考虑回路,笔记,算法,深度优先,数据结构
将1指定3的这条边改为3指向1,则可以得到逆拓扑排序
逆拓扑排序dfs实现算法考虑回路,笔记,算法,深度优先,数据结构
自己的一点小笔记,有错误的话望指出文章来源地址https://www.toymoban.com/news/detail-661012.html

到了这里,关于采用DFS算法实现逆拓扑排序,并判断是否有回路的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【华为OD机试】启动多任务排序(拓扑排序算法—Java&Python&C++&JS实现)

    本文收录于专栏:算法之翼 本专栏所有题目均包含优质解题思路,高质量解题代码(JavaPythonC++JS分别实现),详细代码讲解,助你深入学习,深度掌握!

    2024年04月15日
    浏览(45)
  • 《图》经典题题解(拓扑排序,DFS,BFS,Floyd,Dijkstra,LCA最近公共祖先,最小生成树,最短路径)(ACM)

    目录 拓扑排序 / 家谱树 p1359租用潜艇 P1938[USACO09NOV] Job Hunt S  最短路计数 797. 所有可能的路径  200.岛屿数量 DFS BFS 695.岛屿的最大面积 DFS BFS P1119 灾后重建  P1629 邮递员送信 法一:Floyd 法二:Dijkstra P3379 【模板】最近公共祖先(LCA) 最小生成树 法一:prim算法 法二:Kruskal算

    2024年04月14日
    浏览(40)
  • C语言-算法-拓扑排序

    有个人的家族很大,辈分关系很混乱,请你帮整理一下这种关系。给出每个人的后代的信息。输出一个序列,使得每个人的后辈都比那个人后列出。 第 1 1 1 行一个整数 N N N ( 1 ≤ N ≤ 100 1 le N le 100 1 ≤ N ≤ 100 ),表示家族的人数。接下来 N N N 行,第 i i i 行描述第 i i i

    2024年01月25日
    浏览(40)
  • 【算法基础】拓扑排序及实战

    这里涉及到图的概念,感兴趣的同学请移驾 –图– 下面还有两个相关概念,大概说一下: 定义:在图论中,如果一个有向图从任意顶点出发无法经过若干条边回到该点,则这个图是一个 有向无环图(DAG,Directed Acyclic Graph) 每条边都带有从一个顶点 指向另一个顶点 的方向

    2024年02月08日
    浏览(78)
  • 算法沉淀——拓扑排序

    首先我们需要知道什么是拓扑排序? 在正式讲解拓扑排序这个算法之前,我们需要了解一些前置知识(和离散数学相关) 1、有向无环图: 指的是一个无回路的有向图。 入度:有向图中某点作为图中边的终点的次数之和 出度:有向图中某点作为图中边的起点的次数之和 2、

    2024年04月09日
    浏览(45)
  • 算法学习系列(二十一):拓扑排序

    这个拓扑排序大家应该都听说过,用的地方也是很多,考研和面试也是经常考,其实这个排序算法的思想比较简单,应用的话就是可以用来判断一个图中是否存在一个环,本文主要是介绍拓扑排序的思想,以及一个简单的模板题,来帮助了解什么是拓扑排序,以及怎么写。

    2024年01月16日
    浏览(48)
  • 王道p40 17.设计一个算法用于判断带头结点的循环双链表是否对称(c语言代码实现)

    补充循环双链表的知识: 循环双链表是一种链表数据结构,在链表的基础上增加了头尾相连的循环特性,即链表的最后一个节点指向第一个节点,同时每个节点除了储存下一个节点的指针外还储存前一个节点的指针,这样可以实现在链表两端快速插入和删除元素的操作。 与

    2024年02月07日
    浏览(46)
  • 拓扑排序 (算法思想+图解+模板+练习题)

    有向无环图一定是拓扑序列,有向有环图一定不是拓扑序列。 无向图没有拓扑序列。 首先我们先来解释一下什么是有向无环图: 有向就是我们两个结点之间的边是有方向的,无环的意思就是整个序列中没有几个结点通过边形成一个圆环。 下图就是一个有向无环图,它也一定

    2024年02月03日
    浏览(70)
  • 探索经典算法 拓扑排序,字符串匹配算法,最小生成树

    拓扑排序、字符串匹配算法和最小生成树是计算机科学中常用的数据结构和算法,它们在解决各种实际问题中具有重要的应用价值。在本文中,我将详细介绍这三个主题,并提供相应的示例代码和应用场景,以帮助读者更好地理解和应用这些概念。 一、拓扑排序: 拓扑排序

    2024年02月05日
    浏览(51)
  • 【算法基础:搜索与图论】3.3 拓扑排序

    https://oi-wiki.org/graph/topo/ 本文主要学习拓扑排序相关知识。 拓扑排序的英文名是 Topological sorting。 拓扑排序要解决的问题是给一个 有向无环图 的 所有节点排序 。 我们可以拿大学每学期排课的例子来描述这个过程,比如学习大学课程中有:程序设计,算法语言,高等数学,

    2024年02月16日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包