数据结构 — 图 之 拓扑排序 (AOV网)
发布日期:2021-06-30 19:49:34
浏览次数:2
分类:技术文章
本文共 1346 字,大约阅读时间需要 4 分钟。
【度娘说】:
对一个(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个得到该集合上的一个,这个操作称之为拓扑排序。
【实现】:
/*input:6 80 10 20 31 42 42 53 43 5output:V0 V3 V2 V5 V1 V4 */#include#include using namespace std;#define EleType int#define MAX_NUM 100typedef struct node { EleType v; struct node *next;}NodeType,*NodePointer;typedef struct { int idegree; NodePointer next;}GNode,*GPointer;GNode graph[MAX_NUM];int vn,en; //顶点数和边数void CreatG() { EleType et1,et2; NodePointer tail; cin>>vn>>en; for(int i = 0; i >et1>>et2; NodePointer np = new NodeType; np->v = et2; np->next = NULL; if(graph[et1].next == NULL) { graph[et1].next = np; }else { tail = graph[et1].next; while(tail->next != NULL ) { tail = tail->next; } tail->next = np; } graph[et2].idegree++; }}void TopSort() { int n,m; int top; NodePointer np; top = -1; for(int i = 0; i next) { m = np->v; graph[m].idegree--; if(graph[m].idegree == 0) { graph[m].idegree = top; top = m; } } } } cout<
转载地址:https://lipenglin.blog.csdn.net/article/details/50058245 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年05月03日 19时13分37秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
【深度学习笔记】文本分类
2019-04-30
【转载】炼丹实验室:深度学习网络调参技巧
2019-04-30
【论文阅读笔记】文本分类论文汇总
2019-04-30
【NLP学习笔记】One-hot encoding:独热编码
2019-04-30
【工具使用】CSDN编辑器markdown字体、颜色与字号的设置
2019-04-30
【NLP学习笔记】词共现矩阵
2019-04-30
【NLP学习笔记】NLP基础知识框架图
2019-04-30
【深度学习笔记】卷积的输入输出的通道、维度或尺寸变化过程
2019-04-30
【NLP学习笔记】训练集、验证集和测试集的概念及划分
2019-04-30
【NLP学习笔记】conda换源
2019-04-30
【深度学习笔记】标准卷积
2019-04-30
【深度学习笔记】组卷积
2019-04-30
【深度学习笔记】循环神经网络和递归神经网络区别
2019-04-30
【学习笔记】英文科技论文常见英语句式积累
2019-04-30
【深度学习笔记】PixelShuffle
2019-04-30
【python3学习笔记】斜杠和双斜杠运算符的区别
2019-04-30