当前位置：文档之家 › 数据结构有向无环图及其应用

数据结构有向无环图及其应用

  • 格式：ppt
  • 大小：1.12 MB
  • 文档页数：35

下载文档原格式

  / 35

合集下载

7.5有向无环图及其应用(精)

7.5有向无环图及其应用(精)
13
2018/9/21
数据结构
关键活动：关键路径上的活动都是关键 活动。
（1）关键路径上的各项活动能按期或
提前完成，则整个工程则能按期或提前
完成。 （2）如果关键活动拖延了时间，整个 工程的工期必定拖延。
14
2018/9/21
数据结构
1）事件vj的最早发生时间Ve(j)
是从源点到顶点vj的最长路径长度，这个时
6 2018/9/21
数据结构
逆拓扑排序，其方法和步骤与拓扑排序 正好形成对偶关系： （1）在AOV网中选取一个没有后继 （即出度为0）的顶点并输出之。 （2）从AOV网中删除该顶点以及射向 该顶点的所有有向边（可以用有向边发出 的顶点的出度减1实现）。 （3）重复（1）、（2），直至全部顶 点输出完毕（逆拓扑排序成功），或者再 也找不到没有后继的顶点（逆拓扑排序失 败）为止。
10 2018/9/21
7.5.2 关键路径
数据结构
1. AOE网 如果在带权的有向图中，用顶点 表示事件，用有向边表示活动，边上 的权表示活动持续的时间，这种带权 的有向图称为AOE网（Activity On Edge Network）。
11
2018/9/21
数据结构
12
2018/9/21
2. 关键路径
7 2018/9/21
数据结构
#define MAXVER 21 typedef struct listnode { int adjvex; struct listnode *next; }listnode; typedef struct { int indegree; listnode *first; }headnode; typedef struct

第7章 图-有向无环图

第7章 图-有向无环图

算法的执行步骤： 算法的执行步骤： 1、用一个数组记录每个结点的入度。将入度为零的 、用一个数组记录每个结点的入度。 结点进栈。 结点进栈。 2、将栈中入度为零的结点V输出。 、将栈中入度为零的结点 输出 输出。 3、根据邻接表找到结点 的所有的邻接结点， 并将 、根据邻接表找到结点V的所有的邻接结点 的所有的邻接结点， 这些邻接结点的入度减一。 这些邻接结点的入度减一 。 如果某一结点的入度变 为零，则进栈。 为零，则进栈。
3
2
3、找到全为零的第 k 列，输出 k 、 4、将第 k 行的全部元素置为零 、 行的全部元素置为零
…………………
7
53、4；直至所有元素输出完毕。 、 ；直至所有元素输出完毕。
1 2 3 4 5 6 7
0 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0
template<class T> int BinaryTree <T>:: NumOfOne ( node <T> *t )
{ int k=0; if (t==NULL ) //空二叉树 //空二叉树 return 0; if (t所指结点 的度为 k=1 所指结点 的度为1) k=1; d1= NumOfOne ( t->lchild); //递归求左子树叶结点数 //递归求左子树叶结点数 d2= NumOfOne ( t->rchild); } //递归求右子树叶结点数 //递归求右子树叶结点数 return (d1+d2+k);
A B
AOE网络：结点为事件，有向边指向表示事件的执行次序。 网络：结点为事件，有向边指向表示事件的执行次序。 网络 有向边定义为活动，边的权值为活动进行所需要的时间。 有向边定义为活动，边的权值为活动进行所需要的时间。

数据结构-有向无环图及其应用

数据结构-有向无环图及其应用
WENKU DESIGN
WENKU DESIGN
2023-2026
ONE
KEEP VIEW
数据结构-有向无环图 及其应用
WENKU DESIGN
WENKU DESIGN
WENKU
REPORTING
https://
CATALOGUE
目 录
• 引言 • 有向无环图的基本概念 • 有向无环图的构建 • 有向无环图的应用场景 • 有向无环图的实际应用案例 • 有向无环图的未来研究方向和挑战
详细描述
目前有向无环图已经在许多领域得到应用，如社交网络分析、生物信息学和推荐系统等。未来可以进 一步探索有向无环图在金融、交通和能源等领域的应用，挖掘其更大的潜力。
提高有向无环图的表示能力和分析精度
总结词
提高有向无环图的表示能力和分析精度 是另一个重要的研究方向，旨在更好地 表示复杂数据关系和提高分析结果的准 确性。
拓扑排序
有向无环图可以用于进行拓扑排 序，即将图中所有节点按照依赖 关系进行排序，使得对于任何一 条从节点i到节点j的有向边，i都
在j之前出现。
关键路径
在项目管理中有向无环图可以用 于确定项目的关键路ห้องสมุดไป่ตู้，即确定
项目的最短完成时间路径。
PART 03
有向无环图的构建
构建有向无环图的算法
基于邻接矩阵的算法
通过构建一个二维矩阵来表示图的节点之间的关系，如果存在一条从节点i到节点j的 边，则矩阵中第i行第j列的值为1，否则为0。
基于邻接表的算法
使用一个列表来存储每个节点所连接的节点，如果存在一条从节点i到节点j的边 ，则在节点i的列表中添加节点j。
构建有向无环图的步骤
01

有向无环图

有向无环图

有向无环图有向无环图（DAG）是一种重要的图形数据结构，在计算机科学、网络和算法分析等领域中都有广泛的应用。

它与普通无向图有所不同，因为它会在连接时增加一个方向，这就意味着它可以表示有序的数据。

有向无环图被广泛应用于计算机科学领域，比如拓扑排序、分布式处理、编译器设计等等。

概念有向无环图是由一些顶点和一些有序的边组成，它将数据结构中的每个顶点连接起来。

每条边都有一个方向，这就决定了图中的有序性，也决定了如何遍历图中的每个顶点。

它只有在没有重复出现的边时，才能保证从一个顶点开始，能够遍历到整个图中的每个顶点。

另外一个特点是，它不能有环，也就是说，从一个顶点出发，不能回到该顶点本身。

拓扑排序有向无环图是一种很强大的数据结构，它可以用来实现拓扑排序（Topological Sorting）。

拓扑排序是一种重要的技术，可以根据有向边的方向，对顶点进行排序，以便给定时序性任务分配排序方式。

比如，在建筑工程中，需要用到拓扑排序，比如地基建完再搭框架，搭框架后再安装门窗等等。

拓扑排序能保证输出的顺序和输入的顺序一致，也可以用于求解最短路径问题，比如求解从一个城市到另外一个城市的最短路径。

分布式处理有向无环图也可以用来实现分布式处理(Distributed Processing)，它可以把任务分解成一些独立的子任务，然后把它们连接起来，形成有向无环图，这样每一个子任务可以在不同的处理器上完成。

分布式处理可以使用有向无环图的拓扑排序算法，实现对任务的排序，从而保证任务的正确执行。

同时，由于它不存在环路，因此也可以保证它是安全的，不会出现死锁的情况，这样也就可以保证流程的有序性。

编译器设计有向无环图也可以用于编译器设计（Compiler Design）。

编译器是计算机科学中一种重要的应用，它可以把高级语言翻译成机器语言，从而可以让计算机处理高级语言编写的程序。

有向无环图可以用来构建编译器，因为它可以实现对语句的排序，这样可以保证编译器在编译过程中符合语法规则，并且能够正确翻译，从而使程序能够正确执行。

有向无环图(DAG)技术：超越区块链的分布式账本

有向无环图(DAG)技术：超越区块链的分布式账本

区块链 交易量与效率成正比，超越区块链的分布式账本：有向无环图（DAG）技术一、起源DAG（Directed Acyclic Graph，有向无环图）是一种数据结构，最早提出在区块链中加入DAG 概念作为算法，是在2013年的bitcointalk论坛，被称作为“Ghost协议”，这一提议也是为了解决当时比特币的扩容问题。

后来，在NXT社区，又有人提出了DAG of block，将DAG的拓扑结构用来存储区块，解决效率问题。

那时对于DAG的应用，还停留在类似于侧链的一个认识。

众所周知，扩展性是当前区块链技术急需解决的难点之一。

谈到扩展性，首当其冲的便是区块链的扩容问题，当区块链上的交易频繁时，区块链的性能也呈会线性下滑。

参考以太坊的容量，仅仅一个加密猫游戏就让区块链不堪重负，造成了巨大拥堵。

所以，如何有效地扩容，成为了当下区块链技术的一大重点。

在PoW算法的区块链中尤其如此，由于PoW机制是将交易数据打包成区块，在由算力高的节点进行记账，这种算法相对于PoS速度较慢，交易量上升更加会影响到整体的确认速度，以比特币为例，一开始比特币区块链大小为1M，后来交易量的上升使得社区不得不考虑扩容方案，还因此引发了扩容之争与分叉事件。

PoS在确认速度上大为改善，但仍然难以跟上需求。

同时，PoW和PoS算法都有趋向于中心化的理论风险，当拥有的算力或者代币达到了一定数量时，区块链就会变得中心化。

DAG也是一种分布式账本技术，与区块链不同。

因为区块链是由区块组成的一条单链，而DAG则是由交易组成的网络。

但本质上，两者却有着很大的相似之处。

DAG中的交易，就可以看做是一个个“区块”，只不过这些区块也可以作为节点，形成一个复杂交织的网络拓扑结构。

DAG与PoW、PoS相比，DAG有着更加高的性能，甚至可以说交易越多、节点越多，处理速度越快。

二、工作原理DAG技术如何在作为一个分布式账本进行应用呢？IOTA是应用DAG技术较为知名的一个项区块链 目，它将DAG进行了改进，并提出Tangle（缠结）方案。

数据结构-第7章图答案

数据结构-第7章图答案

7.3 图的遍历 从图中某个顶点出发游历图，访遍图中其余顶点， 并且使图中的每个顶点仅被访问一次的过程。 一、深度优先搜索 从图中某个顶点V0 出发，访问此顶点，然后依次 从V0的各个未被访问的邻接点出发深度优先搜索遍 历图，直至图中所有和V0有路径相通的顶点都被访 问到，若此时图中尚有顶点未被访问，则另选图中 一个未曾被访问的顶点作起始点，重复上述过程， 直至图中所有顶点都被访问到为止。
void BFSTraverse(Graph G, Status (*Visit)(int v)) { // 按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组 visited。 for (v=0; v<G.vexnum; ++v) visited[v] = FALSE; InitQueue(Q); // 置空的辅助队列Q for ( v=0; v<G.vexnum; ++v ) if ( !visited[v]) { // v尚未访问 EnQueue(Q, v); // v入队列 while (!QueueEmpty(Q)) { DeQueue(Q, u); // 队头元素出队并置为u visited[u] = TRUE; Visit(u); // 访问u for ( w=FirstAdjVex(G, u); w!=0; w=NextAdjVex(G, u, w) ) if ( ! visited[w]) EnQueue(Q, w); // u的尚未访问的邻接顶点w入队列Q
4。邻接多重表
边结点
mark ivex
顶点结点
ilink
jvex
jlink
info
data
firstedge
#define MAX_VERTEX_NUM 20 typedef emnu {unvisited, visited} VisitIf; typedef struct Ebox { VisitIf mark; // 访问标记 int ivex, jvex; // 该边依附的两个顶点的位置 struct EBox *ilink, *jlink; // 分别指向依附这两个顶点的下一条 边 InfoType *info; // 该边信息指针 } EBox; typedef struct VexBox { VertexType data; EBox *firstedge; // 指向第一条依附该顶点的边 } VexBox; typedef struct { VexBox adjmulist[MAX_VERTEX_NUM]; int vexnum, edgenum; // 无向图的当前顶点数和边数 } AMLGraph;

数据结构(C语言版CHAP7(2)


V1
AOE网
a0
a7
V2 V6
a2 a3
V3
a5
a8
V4
V5
a1
V7 a 6 V 8 a4
结束
第 15 页
7.4
有向无环图的应用
为计算完成整个工程至少需要多少时间，需将每一子工程所需的时 间作为权值赋给AOE网的各边（就象哈夫曼树给结点赋权值一样）。 AOE网与关键路径部分，不作为课程要求。
V1
a0
V0
V1
V3
V4
V5
V6
结束
第 3 页
7.4
有向无环图的应用
2 AOE网( activity on edge net ) 用边表示活动，顶点表示事件的有向图称为AOE网。 事件发生表示以 该事件为起点的活动可以开始，以该事件为终点的活动已经结束。
a1 a2 a3 a4 a5 a6 分别表示例1中的7个子工程V0、V1、V2、V3、V4、V5、V6。a7 a8
结束
第 14 页
7.4
三 AOE网与关键路径
对工程人们关心两类问题：
有向无环图的应用
1）工程能否顺序进行，即工程流程是否“合理” 2）完成整项工程至少需要多少时间，哪些子工程是影响工程进度的关键 子工程？ 为解决第二类问题，通常可用称为AOE网的有向图表示工程流程 用边表示活动，顶点表示事件。 事件发生表示以该事件为起点的活动可 以开始，以该事件为终点的活动已经结束。
结束
第 12 页
7.4
有向无环图的应用
4）拓扑排序算法 Status TopologicalSort(ALGraph G) { //有向图G采用邻接表存储结构。 //若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则ERROR。 FindInDegree(G, indegree); //求各顶点入度indegree[0..vernum-1] InitStack(S); For(i=0; i<G. vexnum; ++i) //建入度为0的顶点栈S indegree 0 0 if (! Indegree[i]) Push(S, i); //入度为0顶点的编号进栈 1 0 6 2 1 5 V3 3 2 4 4 2 3 V1 V4 V6 5 3 S.top 2 6 2 1 1 V2 V5 V7 S.base 0 0

(16)有向无环图及其应用讲解

有向无环图 及其应用
1
一、定义
一个无环的有向图称为有向无环图，简写为 DAG（directed acycline graph）。 与有向二叉树相比，有向无环图是更一般的特 殊有向图。 实例：
有向树
有向无环图
有向图
有向无环图的一个简单应用： 用有向无环图描述 2 算术表达式。
二、拓扑排序
1.引例：现有计算机课程12门，如下表所示：
vertex
adjvexnextadj firstedge
0
v1
v2
13v4源自v3254
v5
v6
另外增设一个存放各顶点的入度值的一维数组indegree:
indegree[0..5] 0 0 2 1 1 2 2 3 3 4 0 5
10
二、拓扑排序
indegree一维数组初值的程序： 4.求 算法说明：为了使说明过程简单起见，我们以下 FindInDegree(ALGraph G,indegree[0..G.vexnum-1]){ 图为例：
拓扑序列：C1 C2 C3 C4 C5 C7 C9 C10 C11 C6 C12 C8
8
二、拓扑排序
3.方法： 注意1 :从某种意义下来说，拓扑排序的结果是不 唯一的。 注意2 :这种以顶点表示活动的有向无环图称为活动 在顶点的网,简称AOV(Activity On Vertex Network) 网。 注意3 :当有向图中包含有向环路时，拓扑排序算法 结束时图中还有若干顶点没有被输出（即有向环路 中的所有顶点没有参加排序）。
C6 C11
6
二、拓扑排序
3.方法：
C4 C5 C2 C1 C3 C7
C12 C9 C10 C8
C6 C11

数据结构-图的定义和术语


继续进行 ·3
·4
搜索。
·5
·6
·7
·3 ·1
·2
·4 从结点 5 出发的搜索序列：
5、6、2、3、1、4、7 适用的数据结构：栈
图的遍历
2、广度（宽度）优先搜索:
• 树：
A
B
C
D
EFG H
I JK
树的按层次进行访问的次序： A、B、C、D、E、F、G、H、 I、J、K、L
适用的数据结构：队列
L A
1
·1
2
12
11
·2
·11
·12
3
6
7
10
·3 ·6 ·7
·10
4
5
8
9
·4 ·5 ·8
·9
图的广度优先的访问次序：
1、2、11、12、3、6、7、10、4、5、8、9
适用的数据结构：队列
图的连通性问题
2、有向图的强连通分量的求法：续 •强连通分量的求法：
1、对有向图 G 进行深度为主的搜索，按照退 出该结点的次序给结点进行编号。最先退 出的结点的编号为 1，其它结点的编号按 次序逐次增大 1。
点1
3 已在U中
16 21 35
0 0 0
lowcost 表示最小距离
4∞ 0
adjvex 表示相应结点(在V －U中的)
5∞
0
lowcost adjvex
U1
6
5 1
25 35 4
3
6
4
2
566 图G
数组：closedge[ 6 ]
00 15 2 20 35 0 46 2 54 2
lowcost adjvex

830数据结构2021-2021真题答案(有错)

2一、 选择题1 1 1 .B 2.A 3.C 4.A 5.D 6.A 7.B 8.A 9.C 10.C1.B 12.C 13.A 14.C 15.B 16.D 17.D 18.D 19.A 20.A5 解释：线索二叉树中某结点是否有左孩子，不能通过左指针域是否为空来判 断，而要判断左标志是否为 1。

二、 填空题1 2 3 .归并排序。

. 能否将关键字均匀影射到哈希空间上.一端 先进后出有无好的解决冲突的方法4 5 6 7 8 9 . 顺序存储或链式存储 （1+n ）/2.从任意节点出发都能访问到整个链表.时间 空间.n-1 n(n-1)/2.2n-1.n n三、 判断题 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 .F.F 非空才成立.F 有向的非强连通图，不成立.T.F 表头没有前驱，表尾没有后序.T.F 先序跟后序不行，中序才行.T.F 不可能0.T1.F2.T3.F4.F5.F四、 应用题1 ．逻辑结构是从操作对象抽象出来的数学模型，结构定义中的“关系”描述的 是数据元素之间的逻辑关系；物理结构是数据结构在计算机中的表示（又称 映像），又称存储结构。

物理结构是指数据具体存放在哪个位置,逻辑结构是2 3．由 AOV 网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存 在入度为 0的顶点为止。

(1) 选择一个入度为 0的顶点并输出之；(2) 从网 中删除此顶点及所有出边。

拓扑序列 1：abcdef 拓扑序列 2：adbcef.二叉树图如下：4 5 .略。

已经不纳入考纲.哈夫曼编码问题编码： 3: 000020: 10 10: 0001 22: 11 18: 001 37: 016.二叉排序树问题比根节点小的往左子树插，大的往右子树插。

图如下：删除50有两种做法：《数据结构》中的解析这里我用第二种做法:五.算法设计题1 & .算法填空（L.elem[i-1]） L.length-1 ++p *p L.length-1;2. 设计算法: 输入 n 个元素的值 创建带头结点的单链线性表 L 。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

拓扑序列： c1 c2 c3 c4 c5 c7 c9 c10 c11 c6 c12 c8
二、拓扑排序
4.算法说明：为了使说明过程简单起见，我们以下 图为例：
G.vertices[0] v1 G.vertices[1] v2 ^ G.vertices[2] v3 G.vertices[3] v4 G.vertices[4] v5 ^ G.vertices[5] v6 4 3 ^ 4 4 ^ 1 ^ 3 2 1 ^
0
v1
v2
1
s
3
v4 v3
2
1
3 ^
5
4
v5
3
v6
另外增设一个存放各顶点的入度值的一维数组indegree:
indegree[0..5] 0 0 0 1 0 2 0 3 1 4 0 5
二、拓扑排序
4.算法说明：为了使说明过程简单起见，我们以下 图为例：
G.vertices[0] v1 G.vertices[1] v2 ^ G.vertices[2] v3 G.vertices[3] v4 G.vertices[4] v5 ^ G.vertices[5] v6 4 3 ^ 4 4 ^ 1 ^ 3 2 1 ^
G.vertices[0] v1 G.vertices[1] v2 ^ G.vertices[2] v3 G.vertices[3] v4 G.vertices[4] v5 ^ G.vertices[5] v6 4 3 ^ 4 4 ^ 1 ^ 3 2 1 ^
0
v1
v2
1
s
3
v4 v3
2
2
3
5
4
v5
v6
0 1 2 3 4 5
二、拓扑排序
4.算法说明：为了使说明过程简单起见，我们以下 图为例：
G.vertices[0] v1 G.vertices[1] v2 ^ G.vertices[2] v3 G.vertices[3] v4 G.vertices[4] v5 ^ G.vertices[5] v6 4 3 ^ 4 4 ^ 1 ^ 3 2 1 ^
一、定义
一个无环的有向图称为有向无环图，简写为 DAG（directed acycline graph）。 与有向二叉树相比，有向无环图是更一般的特 殊有向图。 实例：
有向树
有向无环图
有向图
教材179页给出了有向无环图的一个简单应用： 用有向无环图描述算术表达式。
二、拓扑排序
1.引例：现有计算机课程12门，如下表所示：
c11
c10
c8
二、拓扑排序
3.方法：
c4 c5 c2 c1 c3 c7
c12 c9 c10 c8
c6 c11
拓扑序列： c1 c2 c3 c4 c5 c7 c9 c10 c11 c6 c12 c8
二、拓扑排序
3.方法： 注意1：从某种意义下来说，拓扑排序的结果是不 唯一的。 注意2：这种以顶点表示活动的有向无环图称为活 动在顶点的网，简称AOV(Activity On Vertex Network)网。
另外增设一个存放各顶点的入度值的一维数组indegree:
indegree[0..5] 0 0 0 1 0 2 0 3 1 4 0 5
二、拓扑排序
4.算法说明：为了使说明过程简单起见，我们以下 图为例：
G.vertices[0] v1 G.vertices[1] v2 ^ G.vertices[2] v3 G.vertices[3] v4 G.vertices[4] v5 ^ G.vertices[5] v6 4 3 ^ 4 4 ^ 1 ^ 3 2 1 ^
0
v1
v2
1
s
3
v4 v3
2
2 3
5
4
v5
v6
4号、1号顶点的入 另外增设一个存放各顶点的入度值的一维数组 indegree: 度分别减1
indegree[0..5] 0 0 1 1 0 2 0 3 2 4 0 5
二、拓扑排序
4.算法说明：为了使说明过程简单起见，我们以下 图为例：
G.vertices[0] v1 G.vertices[1] v2 ^ G.vertices[2] v3 G.vertices[3] v4 G.vertices[4] v5 ^ G.vertices[5] v6 4 3 ^ 4 4 ^ 1 ^ 3 2 1 ^
c6
c9
c3,c6 无 c9 c9 c9,c10,c1
二、拓扑排序
2.拓扑排序：
c4 c5 c2 c1 c3 c7
c12 c9 c10 c8
c6 c11
偏序是指集合中仅有部分元素可比较大小(或先后)；
全序是指集合中所有元素均可比较大小（或先后）。
二、拓扑排序
2.拓扑排序：
c4 c5 c2 c1 c3 c7
0
v1
v2
1
s
3
v4 v3
2
5
4
v5
3
v6
另外增设一个存放各顶点的入度值的一维数组indegree:
indegree[0..5] 0 0 0 1 0 2 0 3 1 4 0 5
二、拓扑排序
4号顶点的入度减1 4.算法说明：为了使说明过程简单起见，我们以下 图为例： 打印G.vertices[3].data
0
v1
v2
1
s
3
v4 v3
2
2
3
5
4
v5
v6
另外增设一个存放各顶点的入度值的一维数组indegree:
indegree[0..5] 0 0 1 1 0 2 0 3 2 4 0 5
二、拓扑排序
4.算法说明：为了使说明过程简单起见，我们以下 图为例： 打印G.vertices[2].data
G.vertices[0] v1 G.vertices[1] v2 ^ G.vertices[2] v3 G.vertices[3] v4 G.vertices[4] v5 ^ G.vertices[5] v6 4 3 ^ 4 4 ^ 1 ^ 3 2 1 ^
G.vertices[2] v3 G.vertices[3] v4 G.vertices[4] v5 ^ G.vertices[5] v6 4 3 ^ 4 4 ^ 1 ^
3
v4
v3
2
5 0
5
4
v5
v6
另外增设一个存放各顶点的入度值的一维数组indegree:
indegree[0..5] 0 0 2 1 1 2 2 3 3 4 0 5
0
v1
v2
1
s
3
v4 v3
2
5
4
v5
0
v6
另外增设一个存放各顶点的入度值的一维数组indegree:
indegree[0..5] 0 0 2 1 1 2 1 3 2 4 0 5
二、拓扑排序
4.算法说明：为了使说明过程简单起见，我们以下 图为例： 打印G.vertices[0].data
G.vertices[0] v1 G.vertices[1] v2 ^ G.vertices[2] v3 G.vertices[3] v4 G.vertices[4] v5 ^ 4 4 ^ 1 ^ 3 2 1 ^
0
v1
v2
1
s
3
vቤተ መጻሕፍቲ ባይዱ v3
2
3号、2号、1号顶 G.vertices[5] v6 4 点的入度分别减1
indegree[0..5] 0 0 2 1 1 2 1 3
5
3 ^
4
v5
0
0 5
v6
另外增设一个存放各顶点的入度值的一维数组indegree:
2 4
二、拓扑排序
4.算法说明：为了使说明过程简单起见，我们以下 图为例：
另外增设一个存放各顶点的入度值的一维数组indegree:
indegree[0..5] 0 0 1 1 0 2 0 3 2 4 0 5
二、拓扑排序
4.算法说明：为了使说明过程简单起见，我们以下 图为例：
G.vertices[0] v1 G.vertices[1] v2 ^ G.vertices[2] v3 G.vertices[3] v4 G.vertices[4] v5 ^ G.vertices[5] v6 4 3 ^ 4 4 ^ 1 ^ 3 2 1 ^
data
firstarc
adjvex nextarc
0
v1
v2
1
3
v4
v3
2
5
4
v5
v6
另外增设一个存放各顶点的入度值的一维数组indegree:
indegree[0..5] 0 0 2 1 1 2 2 3 3 4 0 5
二、拓扑排序
indegree一维数组初值的程序： 4.求 算法说明：为了使说明过程简单起见，我们以下 FindInDegree(ALGraph G,indegree[0..G.vexnum-1]{ 图为例：
课程编号
c4
课程名称
c2
c5
先修课程
c1
c1
程序设计基础
离散数学 数据结构 c3 汇编语言
无
c1 c1,c2 c1 c3,c4 c11 c5,c3
c8 c7
c2 c3 c4 c5 c6 c7 c8 c9 c10 c11 c12
c11 c10
语言的设计和分析 c12 计算机组成原理 编译原理 操作系统 高等数学 线性代数 普通物理 数值分析
indegree[0..5] 0 0 2 1 1 2 2 3 3 4 0 5