IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 拓扑排序 golang实现 -> 正文阅读

[数据结构与算法]拓扑排序 golang实现

拓扑排序 golang实现



定义


对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若<u,v> ∈E(G),则u在线性序列中出现在v之前。

通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。

注意:

1.只有有向无环图才存在拓扑序列;

2.对于一个DAG,可能存在多个拓扑序列;


Kahn算法


利用贪心算法,如果两个顶点,顶点b依赖于顶点a,就将a指向b,当一个顶点的入度为零,将这个顶点就是最优排序点, 并且将顶点从图中移除,将可达顶点的入度减一。


代码


package main

import "fmt"

type graph struct {
	vertex int    //顶点
	list map[int][]int //连接表边
}

//添加边
func (g *graph) addVertex(t int, s int)  {
	g.list[t] = push(g.list[t], s)
}

// KhanSort 拓扑排序
func (g *graph) KhanSort()  {
	// 入度
	var inDegree = make(map[int]int)
	// 储存结果的队列
	var queue []int

	// 增加入度
	for i := 1; i <= g.vertex; i++ {
		for _, m := range g.list[i] {
			inDegree[m]++
		}
	}

	//如果某个节点的入度为0,就加入结果队列
	for i := 0; i <= g.vertex; i++ {
		if inDegree[i] == 0 {
			queue = push(queue, i)
		}
	}

	//当有值加入结果队列
	for len(queue) > 0 {
		var now int
		now, queue = pop(queue)
		fmt.Println("->", now)
		// 将所有相邻的入度减1
		for _, k := range g.list[now] {
			inDegree[k]--
			//如果相邻点的入度恰好变为0,加入结果队列中
			if inDegree[k] == 0 {
				queue = push(queue, k)
			}
		}
	}
}

// NewGraph 创建图
func NewGraph(v int) *graph {
	g := new(graph)
	g.vertex = v
	g.list = map[int][]int{}
	i := 0
	for i < v {
		g.list[i] = make([]int, 0)
		i++
	}
	return g
}

// 取出切片第一个元素
func pop(list []int) (int, []int) {
	if len(list) > 0 {
		a := list[0]
		b := list[1:]
		return a, b
	} else {
		return -1, list
	}
}

// 推入切片
func push(list []int, value int) []int {
	result := append(list, value)
	return result
}

func main() {
	// 创建八个节点的无向图
	g := NewGraph(8)
	g.addVertex(2, 1)
	g.addVertex(3, 1)
	g.addVertex(7, 1)
	g.addVertex(4, 2)
	g.addVertex(5, 2)
	g.addVertex(8, 7)
	g.KhanSort()
}


  数据结构与算法 最新文章
寒假第一周总结
蓝桥杯python(题目思路即解答(笔记,持续
堆排序的理解
如何获得数组长度
NC61 两数之和
简谈ArrayList特有的方法
剑指offer - 调整数组顺序使奇数位于偶数前
【力扣】难度【简单】20. 有效的括号
LeetCode | 373. Find K Pairs with Smalle
链表中为什么要设置虚拟头结点dummy?
上一篇文章      下一篇文章      查看所有文章
加:2021-12-04 13:41:41  更:2021-12-04 13:44:12 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
360图书馆 购物 三丰科技 阅读网 日历 万年历 2022年1日历 -2022/1/20 1:10:35-
图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码