最近要写拓扑排序的程序,然后作为一名渣渣,并不是特别懂。课本上说的只说了大致的,我只知道它的思想,却写不出程序来。有没有大神愿意教我(*´ο`*)
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 Arcgis相交分析无法绘制一个或多个图形
- ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
- ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
- ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
- ¥30 3天&7天&&15天&销量如何统计同一行
- ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
- ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
- ¥15 vs2019中数据导出问题
- ¥20 云服务Linux系统TCP-MSS值修改?
- ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)