图的拓扑排序

我不是女神ヾ 2023-07-19 04:55 15阅读 0赞

### 图的基本算法-拓扑序列 ###

*  拓扑排序
 *   *  拓扑排序基本算法
     *  代码示例

# 拓扑排序 #

对于一个有向无环图，简称DAG（Directed Acyclic Graph），进行拓扑排序就是将图中所有的定点排成一个线性序列，使得图中任意一对定点u和v，若边<u,v>则u在拓扑排序中出现在v之前。这样的序列成为满足拓扑次序的序列成为拓扑排序。

## 拓扑排序基本算法 ##

对于一个有向无环图：

*  找到入度为0的顶点，可能有多个，选取其中一个，输出该顶点后，**将与该顶点相关的所有有向边删除**，即该顶点出度减1，且与该顶点相连的所有有向边的另一个顶点的入度减1。
 *  重新扫描图，重复上述步骤，直到输出所有顶点

注意：邻接表表示图的方式中，删除边<u,v>则u的出度减1，v的入度减1

## 代码示例 ##

// 使用邻接表
    struct Vertex {
    	int v;
    	Vertex *next;
    };
    Vertex[n] Graph;
    
    void topo(Vertex g[], int n) 
    {
    	// 初始化有向图所有顶点的入度（用入度来表示所有顶点的边）
    	vector<int> indegree(n, 0);
    	for (int i = 0; i < n; i++) {
    		Vertex *p = g[i]->next;
    		while ( p ) {
    			indegree[p->v]++;
    			p = p->next;
    		}
    	}
    	
    	// 入度为0的边入队，队中为优先删除的顶点
    	queue<int> q;
    	for (in i = 0; i < n; i++) {
    		if (indegree[i] == 0) {
    			q.push(i);
    		}
    	}
    	
    	while (!q.empty()) {
    		int v = q.front();
    		q.pop();
    		printf("%d ", v);
    		
    		// 删除v顶点所有相邻的边
    		Vertex *p = ad[v]->next;
    		while (p) {
    			int n = p->v;
    			indegree[n]--;
    			if (indegree[n] == 0) {
    				q.push(n);
    			}
    			p = p->next;
    		}
    	}
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，15人围观）

还没有评论，来说两句吧...

相关阅读

相关课程表排序问题，图的拓扑排序！

题目描述： ![22a681e2b679464f91791cabc480c0f3.png][] 题解： class Solution {

以你之姓@/ 2023年09月27日 11:44/ 0 赞/ 129 阅读

相关【数据结构】什么是拓扑排序—关于图的拓扑排序

目录一、什么是拓扑排序？二、拓扑排序：基本概念三、拓扑排序：分析四、拓扑排序：步骤五、拓扑排序：实现六、练习 ------------------

待我称王封你为后i/ 2023年09月26日 10:26/ 0 赞/ 16 阅读

相关图的拓扑排序

图的基本算法-拓扑序列拓扑排序拓扑排序基本算法代码示例拓扑排序对于一个有向无环图，简称DAG（Directed Acyc

我不是女神ヾ/ 2023年07月19日 04:55/ 0 赞/ 16 阅读

相关有向图的拓扑排序

一.拓扑排序的步骤如下 1.输出AOV网中没有前驱节点的节点。 2.在AOV网中删除该节点以及对应的出边。 3.重复上述步骤，直到所有节点都输出为止，完成的拓扑排序

秒速五厘米/ 2022年12月28日 00:42/ 0 赞/ 210 阅读

相关【拓扑排序（Topological Sorting）——图】

拓扑排序（Topological Sorting）一、基本概念二、拓扑排序的过程三、拓扑排序的实现 1、设计数据结构

Bertha 。/ 2022年12月21日 06:09/ 0 赞/ 206 阅读

相关有向图的拓扑排序

有向图的拓扑排序本文取自《数据结构与算法》(C语言版)(第三版)，出版社是清华大学出版社。本博文作为学习资料整理。源代码是VC++ 6.0上可执行程序，我挪到了VS20

柔光的暖阳◎/ 2022年08月21日 04:45/ 0 赞/ 202 阅读

相关图的拓扑排序及其应用

拓扑排序的定义对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常

逃离我推掉我的手/ 2022年06月04日 05:47/ 0 赞/ 258 阅读

相关有向图拓扑排序

// // main.cpp // Tu // // Created by 李奕昕 on 2018/6/16. // Copyr

绝地灬酷狼/ 2022年05月22日 08:27/ 0 赞/ 261 阅读

相关数据结构——图——拓扑排序

在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（英语：Topological sorting）。（1）每个顶点出现且只出现一次

Bertha 。/ 2022年04月12日 05:07/ 0 赞/ 291 阅读

相关 DAG图中的拓扑排序

拓扑排序概念思想代码应用概念 > DAG是指有向无环图，而拓扑排序是有向无环图的一个具体应用。拓扑

港控/mmm°/ 2021年09月21日 06:18/ 0 赞/ 327 阅读