拓扑排序(判断有向图是否有回路)
来源:学生作业帮 编辑:搜搜考试网作业帮 分类:综合作业 时间:2024/06/23 09:20:54
拓扑排序(判断有向图是否有回路)
![拓扑排序(判断有向图是否有回路)](/uploads/image/z/496836-36-6.jpg?t=%E6%8B%93%E6%89%91%E6%8E%92%E5%BA%8F%EF%BC%88%E5%88%A4%E6%96%AD%E6%9C%89%E5%90%91%E5%9B%BE%E6%98%AF%E5%90%A6%E6%9C%89%E5%9B%9E%E8%B7%AF%EF%BC%89)
#include #include #include using namespace std; //表结点 typedef struct ArcNode{ int adjvex;//该弧所指向的顶点的位置 ArcNode *nextarc; }ArcNode; //头结点 typedef struct VNode{ string data;//顶点信息 ArcNode *firstarc;//第一个表结点的地址,指向第一条依附该顶点的弧的指针 }VNode, AdjList[10]; typedef struct ALGraph{ AdjList vertices; int vexnum, arcnum; }ALGraph; int LocateVex(ALGraph G, string u)//返回顶点u在图中的位置 { for(int i=0; i>G.arcnum; coutnextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=arc; } } void FindIndegree(ALGraph G, int indegree[])//求顶点的入度 { for(int i=0; inextarc; } } } void TopologicalSort(ALGraph G)//拓扑排序 { queue q; int indegree[10]={0};//入度数组 int count=0;//计数,计入队数 FindIndegree(G, indegree); for(int i=0; i