最近要写拓扑排序的程序,然后作为一名渣渣,并不是特别懂。课本上说的只说了大致的,我只知道它的思想,却写不出程序来。有没有大神愿意教我(*´ο`*)
2条回答
- threenewbee 2015-12-27 15:17关注
有向图可以拓扑排序的条件是:图中没有环。
具体方法:
⑴ 从图中选择一个入度为0的点加入拓扑序列。
⑵ 从图中删除该结点以及它的所有出边(即与之相邻点入度减1)。
反复执行这两个步骤,直到所有结点都已经进入拓扑序列。#include <iostream> #include <fstream> #include <stack> using namespace std; ifstream fin("in.txt"); #define MAX_VERTEX_NUM 26 stack<int> s; typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; ArcNode(){nextarc=0;} // InfoType *info; }ArcNode; typedef struct VNode{ int data; ArcNode *firstarc; VNode(){firstarc=0;} }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; int vexnum,arcnum; int kind; }ALGraph; bool TopologicalSort(ALGraph G,int *indegree) { int i,k; for(i=1;i<G.vexnum+1;i++) { if(!indegree[i]){s.push(i);} } int count=0; ArcNode *p; while(!s.empty()) { i = s.top(); s.pop(); cout<<G.vertices[i].data<<"-->"; count++; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { k = p->adjvex; indegree[k]--; if(!indegree[k])s.push(k); } } if(count<G.vexnum) return false; return true; } int main() { int i; ALGraph g; cout<<"输入节点数和边数: "; fin>>g.vexnum>>g.arcnum; for(i=1;i<g.vexnum+1;i++) g.vertices[i].data = i; int b,e; ArcNode *p; int *indegree = new int[g.vexnum+1]; //注意 int *a=new int(n); 申请一个整型变量空间,赋初值为n,并定义一个整型指针a指向该地址空间 //int *indegree=(int *)malloc(sizeof(int)*(g.vexnum+1)); memset(indegree,0,sizeof(int)*(g.vexnum+1)); cout<<"逐一输入边的顶点对,形如 3 5 "<<endl; for(i=1;i<g.arcnum+1;i++) { cout<<"第"<<i<<"条边:"; fin>>b>>e; p = new ArcNode(); p->adjvex = e; p->nextarc = g.vertices[b].firstarc; g.vertices[b].firstarc = p; indegree[e]++; cout<<endl; } if(TopologicalSort(g,indegree))cout<<"正常完成!"<<endl; else cout<<"该有向图有回路!"<<endl; return 0; }
解决 无用评论 打赏 举报
悬赏问题
- ¥15 没有证书,nginx怎么反向代理到只能接受https的公网网站
- ¥50 成都蓉城足球俱乐部小程序抢票
- ¥15 yolov7训练自己的数据集
- ¥15 esp8266与51单片机连接问题(标签-单片机|关键词-串口)(相关搜索:51单片机|单片机|测试代码)
- ¥15 电力市场出清matlab yalmip kkt 双层优化问题
- ¥30 ros小车路径规划实现不了,如何解决?(操作系统-ubuntu)
- ¥20 matlab yalmip kkt 双层优化问题
- ¥15 如何在3D高斯飞溅的渲染的场景中获得一个可控的旋转物体
- ¥88 实在没有想法,需要个思路
- ¥15 MATLAB报错输入参数太多