一站式网站建设与运营/30个免费货源网站

图解演示拓扑排序的过程

不是AOV网的情况

由下可知，当前图中存在回路，不是AOV网

拓扑排序的数据结构

编程流程

拓扑排序算法伪代码

完整代码

#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,累加器加1VertexNode 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;
}