C语言实现图的拓扑排序算法

#include
#include

typedef struct Graph
{
	char* vexs;//顶点
	int** arcs;//边--数组（二级指针）
	int vexsnum;
	int arcsnum;
}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* inDegrees = (int*)malloc(sizeof(int) * G->vexsnum);
	for (int i = 0; i < G->vexsnum; i++)//初始化
	{
		inDegrees[i] = 0;
	}
	for (int i = 0; i < G->vexsnum; i++)//统计以第一个节点为起始点的一列的入度
	{
		for (int j = 0; j < G->vexsnum; j++)
		{
			if (G->arcs[i][j])
			{
				inDegrees[j] = inDegrees[j] + 1;
			}
		}
	}
	return inDegrees;
}

void topologicalSort(Graph* G)//拓扑排序
{
	int index = 0;
	int* inDegrees = findInDegrees(G);
	int* top = (int*)malloc(sizeof(int) * G->vexsnum);
	Node* stack = initStack();
	for (int i = 0; i < G->vexsnum; i++)
	{
		if (inDegrees[i] == 0)//如果入度为0，则入栈
		{
			push(stack, i);
		}
	}
	while (!isEmpty(stack))//栈不为空，则出栈
	{
		int vex = pop(stack);
		top[index++] = vex;//记录出栈的元素
		for (int i = 0; i < G->vexsnum; i++)
		{
			if (G->arcs[vex][i])//如果有边，让边减一
			{
				inDegrees[i] = inDegrees[i] - 1;
				if (inDegrees[i] == 0)//如果减到0，继续入栈
				{
					push(stack, i);
				}
			}
			
		}
	}
	for (int i = 0; i < index; i++)//输出其拓扑排序
	{
		printf("%c ", G->vexs[top[i]]);
	}
	printf("\n");
}


Graph* initGraph(int vexsnum)//图的初始化
{
	Graph* G = (Graph*)malloc(sizeof(Graph));//整个图开辟空间
	G->vexs = (char*)malloc(sizeof(char) * vexsnum);//顶点开辟空间
	G->arcs = (int**)malloc(sizeof(int*) * vexsnum);//边开辟空间
	for (int i = 0; i < vexsnum; i++)
	{
		G->arcs[i] = (int*)malloc(sizeof(int) * vexsnum);//把一个一维数组的每个值的指针指向一个一维数组
	}
	G->vexsnum = vexsnum;
	G->arcsnum = 0;
	return G;
}

void createGraph(Graph* G, char* vexs, int* arcs)//把顶点和边赋值给二维数组
{
	for (int i = 0; i < G->vexsnum; i++)
	{
		G->vexs[i] = vexs[i];
		for (int j = 0; j < G->vexsnum; j++)
		{
			G->arcs[i][j] = *(arcs + i * G->vexsnum + j);
			if (G->arcs[i][j] != 0 )//判断是否右边
			{
				G->arcsnum++;
			}
		}
	}
	G->arcsnum /= 2;//（无向图）边只能算一次
}

//深度优先遍历
void DFS(Graph* G, int* visited, int index)//visited看该节点是否被访问，index看访问的那个节点
{
	printf("%c\t", G->vexs[index]);//先访问该节点
	visited[index] = 1;
	for (int i = 0; i < G->vexsnum; i++)//找到相连的顶点
	{
		if (G->arcs[index][i] ==1 && !visited[i])//如果未被访问，则递归
		{
			DFS(G, visited, i);
		}
	}
}

int main()
{
	Graph* G = initGraph(6);
	int* visited = (int*)malloc(sizeof(int) * G->vexsnum);
	for (int i = 0; i < G->vexsnum; i++)
	{
		visited[i] = 0;
	}
	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
	};
	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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187