图解演示拓扑排序的过程
不是AOV网的情况
由下可知，当前图中存在回路，不是AOV网
拓扑排序的数据结构
编程流程
拓扑排序算法伪代码
完整代码
代码语言：javascript复制#include<iostream>
using namespace std;
#include<stack>
#define MAX 10//最大顶点数为10
//边表结构体
typedef struct EdgeNode
{
int agjvex;//邻接点域，存储顶点对应的下标
//int weight;//用来存储权值，对于非网图这里可以不需要
struct EdgeNode* next;//链域，指向下一个邻接点
}EdgeNode;
//顶点表结构体
typedef struct VertexNode
{
int in;//顶点入度
int data;//顶点域，存储顶点信息
EdgeNode* firstedge;//边表头指针
}VertexNode,AdjList[MAX];//顶点结构体数组最大长度为10
//图
class Graph
{
private:
int verNum;//顶点个数
int arcNum;//边的个数
public:
AdjList adjlist;//顶点结构体数组
Graph(int v[], int n, int e);
void display();
int getVerNum()
{
return verNum;
}
};
Graph::Graph(int v[], int n, int e)
{
verNum = n;
arcNum = e;
//初始化顶点数组
for (int i = 0; i < verNum; i )
{
adjlist[i].data = v[i];
adjlist[i].firstedge = NULL;
adjlist[i].in = 0;
}
//建立边的关系
int vi, vj;
for (int i = 0; i < arcNum; i )
{
cin >> vi >> vj;
EdgeNode* s = new EdgeNode;
s->agjvex = vj;
//头插法
s->next = adjlist[vi].firstedge;
adjlist[vi].firstedge = s;
}
//计算每个顶点的入度
for (int i = 0; i < verNum; i )
{
for (int j = 0; j < verNum; j )
{
EdgeNode* edge = adjlist[j].firstedge;
while (edge)
{
if (edge->agjvex == i)
{
adjlist[i].in ;
}
edge = edge->next;
}
}
}
}
//打印顶点表和边表
void Graph::display()
{
for (int i = 0; i < verNum; i )
{
cout <<"当前顶点的入度："<<adjlist[i].in<<" 当前顶点信息为：" <<adjlist[i].data << "-->";
EdgeNode* move = adjlist[i].firstedge;
while (move)
{
cout << move->agjvex << " ";
move = move->next;
}
cout << endl;
}
}
//拓扑排序
void TopologicalSort(Graph g)
{
//1.栈s初始化，累加器count初始化
stack<VertexNode> s;
int count = 0;
//2.扫描顶点表，将没有前驱的顶点入栈
for (int i = 0; i < g.getVerNum(); i )
{
if (g.adjlist[i].in == 0)
{
s.push(g.adjlist[i]);
//入完栈之后，把该节点的in设置为-1，防止下次重复入栈
g.adjlist[i].in = -1;
}
}
//3.当栈s非空时循环
while (!s.empty())
{
//3.1 Vj=退出栈顶的元素，输出Vj,累加器加1
VertexNode Vj = s.top();
s.pop();
cout << Vj.data << " ";
count ;
//3.2 将顶点Vj的各个邻接点的入度减一
EdgeNode* move = Vj.firstedge;
while (move)
{
g.adjlist[move->agjvex].in--;
move = move->next;
}
//3.3 将新的入度为0的顶点入栈（这里注意，之前入过栈的元素不能再次入栈，不然会造成死循环）
for (int i = 0; i < g.getVerNum(); i )
{
if (g.adjlist[i].in == 0)
{
s.push(g.adjlist[i]);
//入完栈之后，把该节点的in设置为-1，防止下次重复入栈
g.adjlist[i].in = -1;
}
}
}
//4.if(count<vertexNum)输出有回路信息
cout << endl;
if (count < g.getVerNum())
{
cout << "有回路" << endl;
}
}
void test()
{
int v[6] = { 0,1,2,3,4,5 };
Graph g(v,6,9);
cout << "打印顶点表和边表" << endl;
g.display();
cout << "拓扑序列: " << endl;
TopologicalSort(g);
}
int main()
{
test();
system("pause");
return 0;
}
