数据结构——拓扑排序算法理解和实现_拓扑排序栈和恶队列实现

AOV网是一个有向图，其顶点之间有着优先顺序，但没有环路结构

意思就是：一件事做了，就不用回头再做

拓扑排序，就是对一个有向图构造拓扑序列的过程
构造拓扑排序时，是按照一种从最开始的逐个往后走的顺序输出 如上图所示。

如果输出的顶点是全部顶点，则是不存在环路的AOV网
如果输出顶点少了一个，则是存在回路的AOV网

拓扑排序的实现思想
1.构造一个有向图的邻接表，存入图的结构信息
2.构造一个栈Q或者队列Q，用来存放入度为0的顶点信息
（也可以构造一个栈T或队列T，用来存放拓扑排序的结果）

3当Q存在顶点m时，
执行下面步骤：
3.1：将顶点m从Q中删除，并将其存入T中
3.2：删除顶点m相关的出度边，<m,n>
3.3:判断顶点n的入度，如果入度为0，则将其存入Q中

上面意思就是 从最开始的入度为0的顶点开始，然后找第二次的顶点，一层层的处理下去。

拓扑排序的实现

#include<iostream>
using namespace std;
#define MAX 25

typedef char Vertype;
typedef int Edgetype;
typedef int Status;

//构造图的有向图的邻接表结构体
typedef struct EdgeNode//边表结点  存放每个顶点的邻接点
{
	int adjvex;//边表下标
	Edgetype weight;//边表权重  若边不存在时即无NULL
	struct EdgeNode *next;//指向下一个邻接点
}EdgeNode;

typedef struct VerNode//顶点表   存放顶点
{
	int in;
	Vertype data;//顶点元素
	EdgeNode *firstedge;
}VerNode, AdjList[MAX];//邻接表的 顶点元素 和指向邻点的指针

typedef struct
{
	AdjList adjList;//邻接表
	int numVer, numEdge;//顶点数目和边的数目
}GraphAdjList;

//构造两个栈
typedef struct Stack
{
	int data[MAX];
	//int pop;
}SqStack;

//生成邻接表
Status CreatGraph(GraphAdjList &G)
{
	int i, j, k;
	Edgetype w;
	EdgeNode *e;
	cout << "Enter the number of vertices :" << endl;
	cin >> G.numVer;
	cout << "Enter the number of Edges :" << endl;
	cin >> G.numEdge;

	cout << "Input vertex content :" << endl;
	for (i = 0; i < G.numVer; i++)
	{
		cin >> G.adjList[i].data;//输入顶点元素
		G.adjList[i].in = 0;
		G.adjList[i].firstedge = NULL;//初始化邻边表为NULL；
	}

	for (k = 0; k < G.numEdge; k++)
	{
		cout << "Enter the vertex number of the edge (Vi->Vj)" << endl;
		cin >> i;
		cin >> j;

		cout << "Enter the weight of edge" << i << "-" << j << endl;
		cin >> w;
		e = new EdgeNode;//将两个顶点相结即可。
		e->adjvex = j;// 邻接序号为j
		e->next = G.adjList[i].firstedge;//i的第一个邻接指针 为e的指针
		e->weight = w;
		G.adjList[i].firstedge = e;
		G.adjList[j].in++;

		//有向图则只有生成一次即可
		/*
		e = new EdgeNode;
		e->adjvex = i;//无向图 重复一遍
		e->next = G.adjList[j].firstedge;
		G.adjList[j].firstedge = e;
		e->weight = w;*/
	}
	return 0;
}

//拓扑排序
Status TOpologicalSort(GraphAdjList &G, SqStack &Q)
{
	EdgeNode *e;
	int i, j, k, gettop;
	int top = 0;
	int count = 0;

	for (i = 0; i < G.numVer; i++)
	{
		if (G.adjList[i].in == 0)
			Q.data[++top] = i;
	}

	while (top != 0)
	{
		gettop = Q.data[top--];//出栈   入度为0的下标
		cout << G.adjList[gettop].data << "->";
		count++;//统计拓扑网顶点数目
		//后面输出其边顶点
		//并删除边，使得边顶点入度-1
		for (e = G.adjList[gettop].firstedge; e; e = e->next)
		{
			j = e->adjvex;
			if (!(--G.adjList[j].in))//如果入度为1时  自减后进入循环   如果入度不为1，自减后 相当于边的数目减1
			{
				Q.data[++top] = j;
			}
		}
	}
	if (count < G.numVer)
	{
		cout << "不是一个网图" << endl;
		return NULL;
	}
	else
		cout << "是一个网图"<< endl;
		return 0;
	return 0;
	
}

int main()
{
	GraphAdjList G;
	CreatGraph(G);
	SqStack Q;
	TOpologicalSort(G, Q);
	system("pause");
	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

如果需要输出则再在++top时加一个队列存入元素