图的拓扑排序C/C++代码实现

谁借莪１个温暖的怀抱￠ 2023-02-20 02:07 140阅读 0赞

## AOV-网： ##

一个无环的有向图称作有向无环图(Directed Acycline Graph), 简称**DAG图**。

用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网(Activity On Vertex Netwrok) ,简称**AOV-网**

## 拓扑排序： ##

所谓拓扑排序就是将AOV-网中所有顶点排成一个线性序列。

作用：可用来判断图或网中是否有环。检测的办法是对有向图的顶点进行拓扑排序，若网中所有顶点都在它的拓扑有序序列中，则该AOV-网中必定不存在环，否则有环。  
除了用拓扑排序判断图有无环外，深度优先遍历同样也能判断。

## 具体步骤： ##

(1) 在有向图中选一个无前驱的顶点且输出它。  
(2) 从图中删除该顶点和所有以它为尾的弧(代码可用弧头顶点的入度减1的办法来实现)。  
(3) 重复 (1) 和 (2), 直至不存在无前驱的顶点。  
(4) 若此时输出的顶点数小千有向图中的顶点数，则说明有向图中存在环，否则输出的顶点序列即为一个拓扑序列。

以该图为例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]

## 代码如下： ##

#include<stdio.h>
    
    #define MVNum 100
    typedef char OtherInfo;
    typedef char VerTexType;
    
    //图的邻接表存储结构
    typedef struct ArcNode			//边结点
    {
        
    	int adjvex;	//邻接点域 
    	struct ArcNode *nextarc;//链域
    	OtherInfo info;	//数据域 
    }ArcNode;
    typedef struct VNode			//顶点信息
    {
        
    	VerTexType data;//数据域 
    	ArcNode *firstarc;//链域
    }VNode, AdjList[MVNum];
    typedef struct                  //邻接表
    {
        
    	AdjList vertices;
    	int vexnum, arcnum;
    }ALGraph;
    
    //函数声明
    int LocateVex(ALGraph G, char v);
    void LinkAL(ALGraph &G, int i, int j);
    void FindInDegree(ALGraph G, int indegree[]);
    void printTopo(int topo[], int m);
    
    
    //邻接表创建有向图
    void CreateUDG(ALGraph &G)
    {
        
    	G.vexnum = 6;						//输入总顶点数和边数
    	G.arcnum = 8;
    	G.vertices[0].data = 'v1';			//输入顶点信息
    	G.vertices[0].firstarc = NULL;
    	G.vertices[1].data = 'v2';
    	G.vertices[1].firstarc = NULL;
    	G.vertices[2].data = 'v3';
    	G.vertices[2].firstarc = NULL;
    	G.vertices[3].data = 'v4';
    	G.vertices[3].firstarc = NULL;
    	G.vertices[4].data = 'v5';
    	G.vertices[4].firstarc = NULL;
    	G.vertices[5].data = 'v6';
    	G.vertices[5].firstarc = NULL;
    
    	int i, j;							//输入边信息
    	i = LocateVex(G, 'v1');
    	j = LocateVex(G, 'v2');
    	LinkAL(G, i, j);
    	i = LocateVex(G, 'v1');
    	j = LocateVex(G, 'v3');
    	LinkAL(G, i, j);
    	i = LocateVex(G, 'v1');
    	j = LocateVex(G, 'v4');
    	LinkAL(G, i, j);
    	i = LocateVex(G, 'v3');
    	j = LocateVex(G, 'v2');
    	LinkAL(G, i, j);
    	i = LocateVex(G, 'v3');
    	j = LocateVex(G, 'v5');
    	LinkAL(G, i, j);
    	i = LocateVex(G, 'v4');
    	j = LocateVex(G, 'v5');
    	LinkAL(G, i, j);
    	i = LocateVex(G, 'v6');
    	j = LocateVex(G, 'v4');
    	LinkAL(G, i, j);
    	i = LocateVex(G, 'v6');
    	j = LocateVex(G, 'v5');
    	LinkAL(G, i, j);
    }
    
    //建立边
    void LinkAL(ALGraph &G, int i, int j)
    {
        
    	ArcNode *p1;
    	p1 = new ArcNode;
    	p1->adjvex = j;
    	p1->nextarc = G.vertices[i].firstarc;						  //头插法
    	G.vertices[i].firstarc = p1;
    }
    
    //返回顶点位置下标
    int LocateVex(ALGraph G, char v)
    {
        
    	for (int i = 0; i < G.vexnum; i++)
    	{
        
    		if (G.vertices[i].data == v)
    		{
        
    			return i;
    		}
    	}
    }
    
    //打印输出图
    void printGraph(ALGraph G)
    {
        
    	for (int i = 0; i < G.vexnum; i++)
    	{
        
    		printf("%d :", i);
    		printf("v%d ->", i + 1);
    
    		ArcNode *p;
    		p = G.vertices[i].firstarc;
    		while (p != NULL)
    		{
        
    			printf("%d->", p->adjvex);
    			p = p->nextarc;
    		}
    		printf("\n");
    	}
    }
    
    //邻接表深度优先遍历
    bool visited[MVNum];
    void DFS_AL(ALGraph G, int v)
    {
        
    	printf("v%c->", G.vertices[v].data);
    	visited[v] = true;
    	ArcNode *p;
    	p = G.vertices[v].firstarc;
    	while (p != NULL)
    	{
        
    		int w = p->adjvex;
    		if (!visited[w])
    		{
        
    			DFS_AL(G, w);
    		}
    		p = p->nextarc;
    	}
    }
    
    
    
    //定义栈
    #define MAXSIZE 100
    typedef struct
    {
        
    	int base[MAXSIZE];
    	int *top;
    	int stacksize;
    }SqStack;
    //初始化
    int InitStack(SqStack &S)
    {
        
    	S.top = S.base;
    	S.stacksize = MAXSIZE;
    	return 1;
    }
    //入栈
    int Push(SqStack &S, int e)
    {
        
    	if (S.top - S.base == S.stacksize) return 0;
    	*S.top++ = e;
    	return 1;
    }
    //出栈
    int Pop(SqStack &S, int &e)
    {
        
    	if (S.top == S.base) return 0;
    	e = *--S.top;
    	return 1;
    }
    
    
    
    //拓扑排序
    int indegree[MVNum];		//存放各顶点入度
    int topo[MVNum];			//存放拓扑序列的顶点序号
    SqStack S;					//暂存入度为0的顶点
    int TopologicalSort(ALGraph G, int topo[])
    {
        
    	ArcNode *p;
    	int i, m = 0;				//m用来计数
    	FindInDegree(G, indegree);	//求各顶点的入度存入indegree数组
    	InitStack(S);
    	for (i = 0; i < G.vexnum; i++)
    	{
        
    		if (!indegree[i])
    		{
        
    			Push(S, i);			//入度为0的入栈
    		}
    	}
    
    	while (S.base != S.top)
    	{
        
    		Pop(S, i);
    		topo[m] = i;		//入度为0的出栈并存入topo数组中
    		m++;				//计数加一
    		p = G.vertices[i].firstarc;		//p指向后继边结点
    		while (p != NULL)
    		{
        
    			int k = p->adjvex;			//k为顶点下标值
    			--indegree[k];				//顶点的入度减1来代替删除边的操作
    			if (indegree[k] == 0)		//如果减1后为0 则入栈
    			{
        
    				Push(S, k);
    			}
    			p = p->nextarc;				//继续下一个后继边结点
    		}
    	}
    
    	if (m < G.vexnum)  return 0;		//输出的顶点数小千有向图中的顶点数，则说明有向图中存在环
    	else return m;						//否则投拓扑排序成功，无环
    }
    
    //求各顶点的入度
    void FindInDegree(ALGraph G, int indegree[])
    {
        
    	//初始化
    	for (int i = 0; i < G.vexnum; i++)
    	{
        
    		indegree[i] = 0;
    	}
    
    	ArcNode *p;
    	//遍历整个邻接表求出入度，顶点入度即为邻接表边结点中一共所出现的次数
    	for (int j = 0; j < G.vexnum; j++)
    	{
        
    		p = G.vertices[j].firstarc;
    		while (p != NULL)
    		{
        
    			indegree[p->adjvex]++;
    			p = p->nextarc;
    		}
    	}
    }
    
    //打印拓扑序列
    void printTopo(int topo[], int m)
    {
        
    	printf("\n该图的一个拓扑序列为：");
    	for (int i = 0; i < m; i++)
    	{
        
    		printf("v%d->", topo[i]+1);
    	}
    }
    
    int main()
    {
        
    	ALGraph G;
    	CreateUDG(G);
    	printGraph(G);
    
    	int v = 0;
    	printf("深度优先遍历：");
    	DFS_AL(G, v);
    
    	//拓扑排序
    	printf("\n==========================\n");
    	int loop = TopologicalSort(G, topo);
    	if (loop == 0)
    	{
        
    		printf("\n拓扑排序失败，该图有环！\n");
    	}
    	else 
    	{
        
    		printf("\n拓扑排序成功,该图无环！");
    		printTopo(topo, loop);		//输出拓扑序列
    	}
    }

## 运行结果： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200621171931592.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200621172416899.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70