拓扑排序：用下面的例子介绍------>
------------------------------------------------------------------------------------------------------------------------
排序后的情况：即先取入度为0的顶点，反应到具体问题上，就是先取没有其他课程限制的课，也就是可以得到一个合理的大学课程排课计划。
#include <queue>#include <cstdio>#include <string>#include <cstring>#include <iostream>#include <algorithm>#define INF 0x3f3f3f3f#define MAX 1010using namespace std;int TopOrder[MAX];//存储排好序的编号typedef struct ENode{int V1, V2;int Weight;}*Edge;struct AdjNode{int Adj;int Weight;AdjNode *Next;};typedef struct ANode{AdjNode *First;int Data;}*AdjList[MAX];typedef struct GNode{int Vertex_num;int EdgeNum;AdjList G;}*LGraph;//图初始化LGraph InitGraph(int VertexNum){LGraph G;G = (LGraph)malloc(sizeof(GNode));G->Vertex_num = VertexNum;G->EdgeNum = 0;for(int i = 0; i < G->Vertex_num; i++)G->G[i]->First = NULL;return G;}//图中边的插入void InsertEdge(LGraph G, Edge E){AdjNode *NewNode;//为V2建立邻接点NewNode = (AdjNode*)malloc(sizeof(AdjNode));NewNode->Adj = E->V2;NewNode->Weight = E->Weight;//将V2插入V1的表头------头插法NewNode->Next = G->G[E->V1]->First;G->G[E->V1]->First = NewNode;}LGraph CreatGraph(){LGraph G;Edge E;int Vertex;cin >> Vertex;G = InitGraph(Vertex);//图初始化cin >> G->EdgeNum; //输入边数if(G->EdgeNum){E = (Edge)malloc(sizeof(ENode));for(int i = 0; i < G->EdgeNum; i++){cin >> E->V1 >> E->V2 >> E->Weight;InsertEdge(G, E); //将边插入G}}}/* 邻接表存储 - 拓扑排序算法 *///此算法可以检测图是否成环；bool TopSort(LGraph G){int InDegree[MAX];//存储入度AdjNode *W;int cnt = 0;queue<int> q;//初始化入度为0memset(InDegree, 0, sizeof(InDegree));//存储每个顶点的入度，V->W,即将指向W的入度++for(int V = 0; V < G->Vertex_num; V++)for(W = G->G[V]->First; W; W = W->Next)InDegree[W->Adj]++;//入度为0的入队，也要优先出队for(int V = 0; V < G->Vertex_num; V++)if(InDegree[V] == 0) q.push(V);while(!q.empty()){int t = q.front();q.pop();//存储出队序号TopOrder[cnt++] = t;//将当前节点的邻接点，即t->W，将W的入度--for(W = G->G[t]->First; W; W = W->Next){InDegree[W->Adj]--;//若减为0，继续入队，等待新的排序if(InDegree[W->Adj] == 0) q.push(W->Adj);}}//若已收录顶点不足图的顶点数，说明图有环，返回falseif(cnt != G->Vertex_num) return false;return true;}int main(){return 0;}
如果觉得《邻接表存储 - 拓扑排序算法》对你有帮助，请点赞、收藏，并留下你的观点哦！
