有向图的拓扑排序

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

拓扑排序。任意给定一个有向图,设计一个算法,对它进行拓扑排序。拓扑排序算法思想:a.在有向图中任选一个没有前趋的顶点输出;b.从图中删除该顶点和所有以它为尾的弧;c.重复上述a、b,直到全部顶点都已输出,此时,顶点输出序列即为一个拓朴有序序列;或者直到图中没有无前趋的顶点为止,此情形表明有向图中存在环。 

拓扑排序算法思想:

  1. 在有向图中任选一个没有前趋的顶点输出;
  2. 从图中删除该顶点和所有以它为尾的弧;
  3. 重复上述1、2、直到全部顶点都已输出,此时,顶点输出序列即为一个拓朴有序序列;或者直到图中没有无前趋的顶点为止,此情形表明有向图中存在环。

拓扑排序算法伪代码如下: 

1. 栈S初始化;累加器count初始化;

2. 扫描顶点表,将没有前驱(即入度为0)的顶点压栈;

3. 当栈S非空时循环

    3.1 vj=退出栈顶元素;输出vj;累加器加1;

3.2 将顶点vj的各个邻接点的入度减1;

3.3 将新的入度为0的顶点入栈;

4. if (count<vertexNum) 输出有回路信息;

代码如下:

#include <stdio.h>
#include <stdlib.h>
#define MAXV 100
#define INF 10000

typedef struct
{
	int data[MAXV];
	int top;
}SqStack;

typedef struct ANode
{
	int adjvex;
	struct ANode *nextarc;
	int weight;
}ArcNode;

typedef struct
{
	int adjvex;
	int count;
	ArcNode *firstarc;

}VNode;

typedef struct
{
	VNode adjlist[MAXV];
	int n,e;
}AdjGraph;

void CreateAdj(AdjGraph *&G,int A[MAXV][MAXV],int n,int e)
{
	int i,j;
	ArcNode *p;
	G=(AdjGraph*)malloc(sizeof(AdjGraph));
	for(i=0;i<n;i++)
    G->adjlist[i].firstarc=NULL;
	for(i=0;i<n;i++) 
	    for(j=n-1;j>=0;j--)
	    if(A[i][j]!=0&&A[i][j]!=INF)
		{
			p=(ArcNode*)malloc(sizeof(ArcNode));
			p->adjvex =j;
			p->weight =A[i][j];
			p->nextarc=G->adjlist[i].firstarc;
			G->adjlist[i].firstarc =p;  
		 } 
		 G->n =n;
		 G->e =e;
 } 

void DispAdj(AdjGraph *G)
 {
 	int i;
 	ArcNode *p;
 	for(i=0;i<G->n ;i++)
 	{
 		p=G->adjlist[i].firstarc;
 		printf("%3d:",i);
 		while(p!=NULL)
 		{
 			printf("%3d[%d]->",p->adjvex,p->weight);
 			p=p->nextarc ;
		 }
		 printf("^\n");
	 }
 }
 
void DestoryAdj(AdjGraph *&G)
{
	int i;ArcNode *pre,*p;
	for(i=0;i<G->n ;i++)
	{
		pre=G->adjlist [i].firstarc;
		if(pre!=NULL)
		{
			p=pre->nextarc ;
			while(p!=NULL)
			{
					free(pre);
					pre=p;
					p=p->nextarc ;
				}
				free(pre);
			}
		}
		free(G);
		
	
}

void InitStack (SqStack *&s)
{
	s=(SqStack *)malloc(sizeof(SqStack));
	s->top =-1;
}

void DestoryStack(SqStack *&s)
{
	free(s);
}

void TopSort(AdjGraph *G)
{
	int i,j,flag=0;
	int a[MAXV];
	int St[MAXV],top=-1;
	ArcNode *p;
	for(i=0;i<G->n;i++)
	G->adjlist [i].count =0;
	for(i=0;i<G->n;i++)
	{
		p=G->adjlist [i].firstarc;
		while(p!=NULL)
		{
			G->adjlist [p->adjvex ].count++;
			p=p->nextarc ;
		}
	}
	for(i=0;i<G->n;i++)
	{
		if(G->adjlist [i].count==0)
		{
			top++;
			St[top]=i;
		}
	} 
	while(top>-1)
	{
		i=St[top];
		top--;
		a[flag++]=i;
		p=G->adjlist [i].firstarc;
		while(p!=NULL)
		{
			j=p->adjvex;
			G->adjlist [j].count--;
				if(G->adjlist [j].count==0)
				{
					top++;
					St[top]=j;
				}
				p=p->nextarc; 
					
		}
	}
		
	if(flag<G->n)
	    printf("该图存在回路,不存在拓扑序列!\n");
	else
	{
		printf("该图的拓扑序列为:");
		for(i=0;i<flag;i++)
		printf("%d",a[i]);
		printf("\n"); 
	}
	
}

int main()
{
	AdjGraph *G;
	int n=7;
	int e=8;
	int A[100][100]={{0,1},{0,0,1,0,0,1},{0,0,0,0,1},{0,0,1,0,1},{0},{0}};
	CreateAdj(G,A,n,e);
	printf("图的邻接表:\n");
	DispAdj(G);
	TopSort(G);
	printf("销毁图的邻接表\n");
	DestoryAdj(G);
	return 0; 
}

有问题可以留言文章来源地址https://www.toymoban.com/news/detail-490048.html

到了这里,关于有向图的拓扑排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 二十一、搜索与图论——拓扑序列(有向图)

    拓扑序列定义: 若一个由图中所有点构成的序列 A满足:对于图中的每条边 (x,y),x在 A中都出现在 y之前,则称 A是该图的一个拓扑序列。 人话: 始终满足每条边的起点在终点前面,从前指向后。 注意:如果在有向图中构成一个环,则必定无法构成拓扑结构,也可以证明有向

    2024年02月04日
    浏览(52)
  • 哪些方法可以判断出一个有向图是否有环

    使用 深度优先遍历 ,若从有向图上的某个顶点u出发,在 DFS(u)结束之前出现一条从顶点v到u的边,由于v在生成树上是u的子孙,则图中必定存在包含u和v的环,因此深度优先遍历可以检测一个有向图是否有环。 拓扑排序 时,当某顶点不为任何边的头时才能加入序列,存在环时环中的

    2024年02月12日
    浏览(40)
  • 用go语言实现一个构建有向图的函数,同时图结构的点和边上都支持添加属性

    当然可以。下面是一个简单的用Go语言实现的有向图构建函数的示例。这个图结构使用map来存储,每个节点都由一个唯一的标识符(id)表示,并且节点和边都可以附加属性。 go 这个示例代码创建了一个有向图,并添加了两个节点(A和B)和一个从A到B的边。每个节点和边都有

    2024年01月20日
    浏览(31)
  • 公开游戏、基于有向图的游戏

    目录 〇,背景 一,公开游戏、策梅洛定理 1,公开游戏 2,策梅洛定理 3,非有向图游戏的公开游戏 力扣 486. 预测赢家(区间DP) 力扣 877. 石子游戏(退化贪心) 力扣 1140. 石子游戏 II(二维DP) 力扣 1406. 石子游戏 III(数列DP) 力扣 1563. 石子游戏 V(区间DP)  力扣 1686.

    2024年02月09日
    浏览(42)
  • 有向图的强连通分量

    对于一个有向图,连通分量:对于分量中任意两点u,v,必然可以从u走到v,且从v走到u. 强连通分量:极大连通分量。 求出强连通分量后,可以通过将强连通分量缩点的方式,将有向图转化成有向无环图。 求强连通分量的方法:tarjan O(n+m),时间复杂度是线性的 1 . 采用dfs来遍历整

    2024年02月10日
    浏览(36)
  • 真题详解(有向图)-软件设计(六十二)

    真题详解(极限编程)-软件设计(六十一) https://blog.csdn.net/ke1ying/article/details/130435971 CMM指软件成熟度模型,一般1级成熟度最低,5级成熟度最高,采用更高级的CMM模型可以提高软件质量。 初始:杂乱无章。 可重复级:建立基本的项目管理过程和跟踪费用项。 已定义(确定)

    2024年02月01日
    浏览(59)
  • 2023-04-09 有向图及相关算法

    有向图的的应用场景 社交网络中的关注 互联网连接 程序模块的引用 任务调度 学习计划 食物链 论文引用 无向图是特殊的有向图,即每条边都是双向的 改进Graph和WeightedGraph类使之支持有向图 Graph类的改动 WeightedGraph类的改动 有些问题,在有向图中不存在,或者我们通常不考

    2024年02月05日
    浏览(44)
  • 有向图的强连通分量算法

    有向图的强连通分量算法 强连通分量定义 在有向图中,某个子集中的顶点可以直接或者间接互相可达,那么这个子集就是此有向图的一个强连通分量,值得注意的是,一旦某个节点划分为特定的强连通分量后,此顶点不能在其它子树中重复使用,隐含了图的遍历过程和极大

    2024年02月06日
    浏览(70)
  • 有向图的邻接表和邻接矩阵

    有向图的邻接表是一种常用的表示方法,用于表示图中各个节点之间的关系。在有向图中,每条边都有一个方向,因此邻接表中的每个节点记录了该节点指向的其他节点。 具体来说,有向图的邻接表由一个由节点和它们的邻居节点列表组成的集合构成。对于每个节点,邻接表

    2024年02月22日
    浏览(37)
  • 使用颜色检测有向图中的循环

    给定一个有向图,检查该图是否包含循环。如果给定的图形至少包含一个循环,您的函数应返回 true,否则返回 false。 例子:   输入:  n = 4, e = 6  0 - 1, 0 - 2, 1 - 2, 2 - 0, 2 - 3, 3 - 3  输出: 是  解释:    

    2024年02月03日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包