拓扑排序（C语言）

旧城等待， 2022-10-14 13:54 178阅读 0赞

在一个有向无环图中，用顶点表示活动，用弧表示活动间的优先关系的有向无环图，称为顶点表示活动的网，简称AOV-网。

对AOV-网，可用拓扑排序来得到他们顶点数据的优先关系，即拓扑序列。

拓扑序列并不一定是唯一的。

如下图：  
![在这里插入图片描述][20210521234931637.png]  
拓扑序列就有：  
acbfde、fadcbe等多种。

拓扑序列需要用到栈。

简单思路：  
1.先求出各顶点的入度，并将入度为0的顶点入栈。  
2.栈不空，则重复以下两步：  
①将栈顶顶点v出栈并打印  
②将顶点i的每一个邻接点k的入度减小1，若顶点k的入度变为0，则将k入栈

代码：

#include <stdio.h>
    #include <stdlib.h>
    
    #define MAX_VER_NUM 2000
    #define VertexData int
    #define ERROR 0
    #define OK 1
    
    typedef enum {
         DG, UDG, DN, UDN }GraphKind;
    
    typedef struct ArcNode{
        
    	VertexData adjvex;
    	struct ArcNode* nextarc;
    }ArcNode;
    
    typedef struct VexNode {
        
    	VertexData data;
    	ArcNode* firstArc;
    }VertexNode;
    
    typedef struct {
        
    	VertexNode vertex[MAX_VER_NUM];
    	int num_vex, num_arc;
    	GraphKind kind;
    }AdjList;
    
    typedef struct {
        
    	int data[MAX_VER_NUM];
    	int top;
    }Stack;
    
    Stack InitStack();     //初始化栈
    void PushStack(Stack* S, int v);   //入栈
    void PopStack(Stack* S, int* v);   //出栈
    int LocateVertex(AdjList A, VertexData v);//找到顶点位置
    AdjList* CreateGraph(int n, int m);       //创建图
    void FindID(AdjList A, int indegree[MAX_VER_NUM]);//求入度
    int TopoSort(AdjList A);   //拓扑排序
    
    
    int main()
    {
        
    	int n, m;
    	scanf("%d%d", &n, &m);
    	AdjList *A;
    	A = CreateGraph(n, m);
    	TopoSort(*A);
    	return 0;
    }
    
    Stack InitStack()
    {
           //初始化栈
    	Stack S;
    	S.top = -1;
    	return S;
    }
    
    void PushStack(Stack *S, int v)
    {
           //入栈
    	if (S->top == MAX_VER_NUM - 1) {
        
    		return;
    	}
    	S->top++;
    	S->data[S->top] = v;
    }
    
    void PopStack(Stack* S, int *v)
    {
           //出栈
    	if (S->top == -1) {
        
    		return;
    	}
    	*v = S->data[S->top];
    	S->top--;
    }
    
    int LocateVertex(AdjList A, VertexData v)
    {
           //找到顶点位置
    	for (int i = 0; i < A.num_vex; i++) {
        
    		if (A.vertex[i].data == v) {
        
    			return i;
    		}
    	}
    	return -1;
    }
    
    AdjList* CreateGraph(int n, int m)
    {
           //创建图
    	AdjList *A;
    	A = (AdjList*)malloc(sizeof(AdjList));
    	if (A == NULL) {
        
    		return NULL;
    	}
    	A->kind = DG;
    	A->num_vex = n;
    	A->num_arc = m;
    	for (int i = 0; i < A->num_vex; i++) {
        
    		scanf("%d", &A->vertex[i].data);//若要输入字符则要改变
    		A->vertex[i].firstArc = NULL;
    	}
    	VertexData v1, v2;
    	int loc1;
    	for (int i = 0; i < A->num_arc; i++) {
        
    		scanf("%d%d", &v1, &v2);//若要输入字符则要改变
    		ArcNode* tmp;
    		tmp = (ArcNode*)malloc(sizeof(ArcNode));
    		if (tmp == NULL) {
        
    			return 0;
    		}
    		tmp->adjvex = v2;
    		loc1 = LocateVertex(*A, v1);
    		tmp->nextarc = A->vertex[loc1].firstArc;
    		A->vertex[loc1].firstArc = tmp;
    	}
    	return A;
    }
    
    void FindID(AdjList A, int indegree[MAX_VER_NUM])
    {
           //求入度
    	ArcNode* tmp;
    	tmp = (ArcNode*)malloc(sizeof(ArcNode));
    	if (tmp == NULL) {
        
    		return;
    	}
    	for (int i = 0; i < A.num_vex; i++) {
        
    		indegree[i] = 0;
    	}
    	int loc;
    	for (int i = 0; i < A.num_vex; i++) {
        
    		tmp = A.vertex[i].firstArc;
    		while (tmp != NULL) {
        
    			loc = LocateVertex(A, tmp->adjvex);
    			indegree[loc]++;
    			tmp = tmp->nextarc;
    		}
    	}
    }
    
    int TopoSort(AdjList A)
    {
           //拓扑排序
    	Stack S;
    	int indegree[MAX_VER_NUM];
    	int count = 0;//记录遍历顶点数，若小于A.num_vex，则A中有环
    	ArcNode* tmp;
    	tmp = (ArcNode*)malloc(sizeof(ArcNode));
    	if (tmp == NULL) {
        
    		return 0;
    	}
    	FindID(A, indegree);
    	S = InitStack();
    	for (int i = 0; i < A.num_vex; i++) {
        
    		if (indegree[i] == 0) {
        
    			PushStack(&S, i);
    		}
    	}
    	int v, k, loc_k;
    	while (S.top != -1) {
        
    		PopStack(&S, &v);
    		printf("%d ", A.vertex[v].data);//若要输入字符则要改变
    		count++;
    		tmp = A.vertex[v].firstArc;
    		while (tmp != NULL) {
        
    			k = tmp->adjvex;
    			loc_k = LocateVertex(A, k);
    			indegree[loc_k]--;
    			if (indegree[loc_k] == 0) {
        
    				PushStack(&S, loc_k);
    			}
    			tmp = tmp->nextarc;
    		}
    	}
    	if (count < A.num_vex) {
        
    		return ERROR;
    	}
    	else return OK;
    }

运行截图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]

[20210521234931637.png]: /images/20221014/3f1ea3b216d2417c82f13294a2eb4f30.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]: /images/20221014/3f50e5ee0a8e4e499cf156624e0e375e.png