当前位置: article > 正文

从零开始学数据结构系列之第四章《拓扑排序代码详解》

作者：Guff_9hys | 2024-08-22 01:03:24

踩

文章目录

代码详解
- 步骤详解
总代码
往期回顾

代码详解

我们的代码思路是这样的：

找到所有入度为 0 的顶点，并将其输出到拓扑序列中。
将这些顶点从图中删除，并将所有以该顶点为起点的边的终点的入度减 1 。
不断重复以上两个操作，直到所有的顶点都被输出到拓扑序列中或者图中不存在入度为 0 的顶点为止。

我们拿这张图来进行代码详解

在这里插入图片描述
图的入度

步骤详解

在这里插入图片描述
首先我们得栈是先进后出，后进先出

第一次我们入栈是 0 ，6，但是出栈的时候是6 先出栈然后 0 再出栈

6 出栈时候，要把它有关联的弧都要去掉，图变成下面这样

在这里插入图片描述
此时图的入度表更新为

1	2	3	4	5	6
0	2	1	1	2	0

之后再次检查入度表是否有新的变成 0 ，发现没有之后继续出栈，这次出栈的是1
在这里插入图片描述
此时图的入度表更新为

1	2	3	4	5	6
0	1	0	0	2	0

之后再次检查入度表是否有新的变成 0 ，发现3,4 以及没有入度了，将3 4 进行入栈，之后再将4进行出栈
在这里插入图片描述
此时图的入度表更新为

1	2	3	4	5	6
0	1	0	0	1	0

之后再次检查入度表是否有新的变成 0 ，发现无，之后再将3进行出栈

在这里插入图片描述
此时图的入度表更新为

1	2	3	4	5	6
0	0	0	0	0	0

之后再次检查入度表是否有新的变成 0 ，发现2，5的入度都变成0了，之后再将5，2进行出栈，此时，排序完成

总代码

#include <stdio.h>
#include <stdlib.h>

typedef struct Graph 
{
    char* vexs;
    int** arcs;
    int vexNum;
    int arcNum;
}Graph;

typedef struct Node 
{
    int data;
    struct Node* next;
}Node;

Node* initStack() 
{
    Node* stack = (Node*)malloc(sizeof(Node));
    stack -> data = 0;
    stack -> next = NULL;
    return stack;
}

int isEmpty(Node* stack) 
{
    if (stack -> next == NULL) 
	{
        return 1;
    }
    else 
	{
        return 0;
    }
}

void push(Node* stack, int data) 
{
    Node* node = (Node*)malloc(sizeof(Node));
    node -> data = data;
    node -> next = stack -> next;
    stack -> next = node;
    stack -> data ++;
}

int pop(Node* stack) 
{
    if (!isEmpty(stack)) 
	{
        Node* node = stack -> next;
        stack -> next = node -> next;
        return node -> data;
    }
    else 
	{
        return -1;
    }
}
/* 寻找入度 */
int* findInDegrees(Graph* G) 
{
	int i=0,j=0;
	int *inDegrees = (int*)malloc(sizeof(int) * G->vexNum);
	for(i=0;i<G->vexNum;i++)
		inDegrees[i] = 0;
	for(i=0;i<G->vexNum;i++)
		for(j=0;j<G->vexNum;j++)
			if(G->arcs[i][j])
				inDegrees[j]+=1;
	return  inDegrees;
}

/* 入栈且拓扑 */
void topologicalSort(Graph* G) 
{
	int i=0;
	int value=0;
	int *inDegrees = findInDegrees(G);
	
	Node *stack = initStack();
	for (i = 0 ; i < G -> vexNum; i++) 
        if (inDegrees[i] == 0) 
            push(stack, i);
	while(!isEmpty(stack))
	{
		value = pop(stack);
		printf("%c  ",G->vexs[value]);
		for(i=0;i<G->vexNum;i++)
			if(G->arcs[value][i])
			{
				inDegrees[i]-=1;
				if (inDegrees[i] == 0) 
					push(stack, i);
			}	
	}
	printf("\r\n");
}

Graph* initGraph(int vexNum) 
{
	int i=0;
    Graph* G = (Graph*)malloc(sizeof(Graph));
    G -> vexs = (char*)malloc(sizeof(char) * vexNum);
    G -> arcs = (int**)malloc(sizeof(int*) * vexNum);
    for (i = 0 ; i < vexNum; i++) 
	{
        G -> arcs[i] = (int*)malloc(sizeof(int) * vexNum);
    }
    G -> vexNum = vexNum;
    G -> arcNum = 0;
    return G;
}

void createGraph(Graph* G, char* vexs, int* arcs) 
{
	int i=0,j=0;
    for (i = 0 ; i < G -> vexNum; i++) 
	{
        G -> vexs[i] = vexs[i];
        for (j = 0; j < G -> vexNum; j++) 
		{
            G -> arcs[i][j] = *(arcs + i * G -> vexNum + j);
            if (G -> arcs[i][j] != 0)
                G -> arcNum ++;
        }
    }
    G -> arcNum /= 2;
}

void DFS(Graph* G, int* visited, int index) 
{
	int i=0;
    printf("%c\t", G -> vexs[index]);
    visited[index] = 1;
    for (i = 0; i < G ->vexNum; i++) 
	{
        if (G -> arcs[index][i] == 1 && !visited[i]) 
		{
            DFS(G, visited, i);
        }
    }
}

int main() 
{
	int i=0;
    Graph* G = initGraph(6);
    int* visited = (int*)malloc(sizeof(int) * G -> vexNum);
	int arcs[6][6] = 
	{
        0,1,1,1,0,0,
        0,0,0,0,0,0,
        0,1,0,0,1,0,
        0,0,0,0,1,0,
        0,0,0,0,0,0,
        0,0,0,1,1,0
    };
    for (i = 0; i < G -> vexNum; i++)
        visited[i] = 0;  
    createGraph(G, "123456", (int*)arcs);
    DFS(G, visited, 0);
    printf("\n");
    topologicalSort(G);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166

在这里插入图片描述

☁️ 以上就是所有内容，对大家有用的话点个关注！感谢大家！

往期回顾

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Guff_9hys/article/detail/1014061?site