拓扑排序C语言详解

梦里梦外; 2023-05-28 06:49 14阅读 0赞

**1. 拓扑排序是对有向无环图的操作。  
2. 如果有环，则会出现，没有入度为0的点的情况，如图。任务之间相互等待。**

![在这里插入图片描述][20200328121338394.png]

**3. 逐步输出入度为0的点，当入度为0的点有多个时，随意输出。  
4. 建立一个栈的辅助空间，存放入度为0的点，避免每次都需遍历寻找是否有入度为0的结点。  
5. 由第三点，显然拓扑排序结果不唯一。**

## 实现如图AOV网的拓扑排序 ##

![在这里插入图片描述][20200328143752616.png]  
**对应的邻接表**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5MTY2NQ_size_16_color_FFFFFF_t_70]  
**核心代码：**

//**************输出GL的拓扑排序序列**************
    int TopologicalSort(GraphAdjList GL)
    { 
    	EdgeNode* p;
    	int i, k, gettop;
    	int top = 0;												//指向栈顶
    	char* stack;												//建栈存储入度为0的点
    	stack = (char*)malloc(GL->numVertexes * sizeof(char));			//建栈
    	if (stack == NULL)
    		exit(0);
    	for (i = 0; i < GL->numVertexes; i++)								//将入度为0的结点入栈
    		if (GL->adjList[i].in == 0)
    			stack[++top] = i;
    	while (top != 0)													//栈非空
    	{ 
    		gettop = stack[top--];											//出栈
    		printf("%c->", GL->adjList[gettop].data);					//打印此结点的值
    		for (p = GL->adjList[gettop].firstedge; p!=NULL; p = p->next)			//对此顶点的弧表遍历
    		{ 
    			k = p->adjvex;
    			if (!(--GL->adjList[k].in))									//对k号顶点邻接点的入度减一 
    				stack[++top] = k;										// 若减1后入度为0.则入栈
    		}
    	}
    	return 0;
    }

## 所有代码如下，编译环境vc6.0 ##

/* 先根据邻接表逻辑结构图生成对应的图 再对图进行拓扑排序 */
    #include <stdio.h>
    #include <stdlib.h>
    #define MAXVEX 100 //最大顶点数
    #define INFINITY 99999 //用99999表示无限大
    
    //***************************边表结点***************************
    typedef struct EdgeNode
    { 
    	int adjvex;											//邻接点域，存储该结点对应的下标
    	//int weight; //用于存储权值，非网图不需要
    	struct EdgeNode* next;								//指向下一个邻接结点
    }EdgeNode;
    
    //***************************顶点表结点***************************
    typedef struct VertexNode
    { 
    	int in;												//顶点的入度个数
    	char  data;											//顶点域，存储顶点信息
    	EdgeNode* firstedge;								//边表头指针，指向第一个边表结点
    }VertexNode,AdjList[MAXVEX];
    
    //***************************邻接表结构***************************
    typedef struct
    { 
    	AdjList adjList;									//顶点表结点数组
    	int numVertexes, numEdges;							//当前顶点个数和边数
    }graphAdjList, * GraphAdjList;
    
    //**************************无向图邻接表的创建*************************
    void CreateALGraph(GraphAdjList G)
    { 
    	int i, j, k;
    	EdgeNode* e;
    	printf("输入顶点数和边数\n");
    	scanf("%d%d", &G->numVertexes, &G->numEdges);
    	getchar();														//获取缓冲区的 回车符
    
    	for (i = 0; i < G->numVertexes; i++)								//读入顶点信息，建立顶点表
    	{ 
    		printf("输入第%d个顶点值\n", i + 1);
    		scanf("%c", &G->adjList[i].data);							//输入顶点信息
    		getchar();													//获取缓冲区的 回车符
    		G->adjList[i].firstedge = NULL;								//将边表置为空表
    		G->adjList[i].in = 0;										//入度为0
    	}
    	for (k = 0; k < G->numEdges; k++)								//建立边表
    	{ 
    		printf("输入边（vi,vj）的下标：\n");
    		scanf("%d%d", &i, &j);
    		e = (EdgeNode*)malloc(sizeof(EdgeNode));				//向内存申请空间
    		if (e == NULL)
    		{ 
    			printf("内存申请失败\n");
    			exit(0);
    		}
    		G->adjList[j].in++;								//入度加一
    		e->adjvex = j;									//这三步，类似于单链表的头插法
    		e->next = G->adjList[i].firstedge;
    		G->adjList[i].firstedge = e;
    	}
    }
    
    //**************输出GL的拓扑排序序列**************
    int TopologicalSort(GraphAdjList GL)
    { 
    	EdgeNode* p;
    	int i, k, gettop;
    	int top = 0;												//指向栈顶
    	char* stack;												//建栈存储入度为0的点
    	stack = (char*)malloc(GL->numVertexes * sizeof(char));			//建栈
    	if (stack == NULL)
    		exit(0);
    	for (i = 0; i < GL->numVertexes; i++)								//将入度为0的结点入栈
    		if (GL->adjList[i].in == 0)
    			stack[++top] = i;
    	while (top != 0)													//栈非空
    	{ 
    		gettop = stack[top--];											//出栈
    		printf("%c->", GL->adjList[gettop].data);					//打印此结点的值
    		for (p = GL->adjList[gettop].firstedge; p!=NULL; p = p->next)			//对此顶点的弧表遍历
    		{ 
    			k = p->adjvex;
    			if (!(--GL->adjList[k].in))									//对k号顶点邻接点的入度减一 
    				stack[++top] = k;										// 若减1后入度为0.则入栈
    		}
    	}
    	printf("\n");
    	return 0;
    }
    
    int main()
    { 
    	graphAdjList GL;
    	CreateALGraph(&GL);
    	printf("拓扑排序结果如下：\n");
    	TopologicalSort(&GL);
    	return 0;
    }

**输出结果**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5MTY2NQ_size_16_color_FFFFFF_t_70 1]

[20200328121338394.png]: /images/20230528/43d4b6bc7641415ab230f22ac6ea3f4b.png
[20200328143752616.png]: /images/20230528/39289dfae6904f0c8589e7a1a1e5f36c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5MTY2NQ_size_16_color_FFFFFF_t_70]: /images/20230528/864d71f3abf84f1eb6e5d3c98dce583e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5MTY2NQ_size_16_color_FFFFFF_t_70 1]: /images/20230528/82ebc9bfaba74c40825fbf74d8894deb.png