最小生成树

目录

最小生成树:Kruskal算法和Prim算法的实现

这里直接给出离散数学中的几个定理和推论:

  • 无向图G具有生成树当且仅当G连通.
  • G为n阶m条边的无向连通图,则 m >= n - 1.
  • G是树 $\Leftrightarrow$ G中任意两个顶点之间存在唯一路径 $\Leftrightarrow$ G中无回路且m=n-1$\Leftrightarrow$ G是连通的且m=n-1$\Leftrightarrow$ G中没有回路但在任何2个不同的顶点间加一条新边就能在图中得到唯一的含新边的环圈.
  • 生成子图指的是顶点集相同,但边集是图G的子集的图.
  • 生成树指的是图G的生成子图并且是树.
  • 最小生成树指的是图G的所有生成树中权最小的.

算法第4版中这样定义:

  • 是一幅无环连通图。
  • 连通图的生成树是它的一幅子图,它含有图中的所有顶点且是一棵树。
  • 加权图是一种为每条边关联一个权值或是成本的图模型。
  • 一幅加权图的最小生成树(MST)是它的一棵权值(树中所有边的权值之和)最小的生成树。
  • 图的一种切分是将图的所有顶点分为两个非空且不重叠的两个集合。横切边是一条连接两个属于不同集合的顶点的边。
  • (切分定理)。在一幅加权图中,给定任意的切分,它的横切边中的权重最小者必然属于图的最小生成树。切分定理是解决最小生成树问题的所有算法的基础。

看了一下算法第4版,真的很有帮助,特别是它的几个API的定义,很像ACM模式的输入,对笔试有一定的帮助。

图的表示

邻接矩阵?需要$n^2$的空间,而有百万个顶点的图是很常见的……

邻接表?可以!用一个顶点为键,值为顶点数组,其中的每个元素都是与该顶点相邻的顶点。

此后记住了,咱一般就是用邻接表。

加权无向图的表示

在邻接表的表示中,可以在链表的结点中增加一个权重域。

Prim 算法:横切边

img

img

  • 初始时只有一个顶点。
  • 每一步都为生长中的树添加一条边,总共添加 $V-1$条。
  • 每次都是加入一条这样的边(横切边):连接树中顶点与不在树中顶点并且权重最小的边。

实现思路:

算法第四版给出了两种实现,一种Lazy的,一种即时的。

我们需要一个顶点集合的布尔数组表示某顶点是否在MST中,一个队列来保存MST中的边,还需要用优先队列来根据权重比较横切边。

如何维护横切边的集合呢?每向树中添加一条边也就添加了一个顶点,那么横切边集合将有失效的。此外,我们感兴趣的只是连接树顶点与非树顶点中权重最小的边,因此只需要保存权重最小的那条边,当有顶点进入树的时候,看顶点的引入是否使得权重更小了。

img

伪代码:

(1) 将顶点0(起点)加入最小生成树,并遍历与起点相连的所有边,将权重最小的放入优先队列pq
(2) while (mstNodeCnt < n) {
		从优先队列pq中取出权重最小的边,将该边加入MST;
		同时将改变对应的顶点V加入MST,并遍历与V相连的所有横切边,找到权重最小的加入优先队列pq;
		mstNodeCnt++;
}

Kruskal 算法:连接一片森林中的两棵树

img

  • 初始时选择最小权重的一条边。
  • 每一步都为生长中的树添加一条边,总共添加 $V-1$条。
  • 每次都是加入一条这样的边:权重最小并且不会和已经加入的边构成环。

实现思路:

我们将会使用一条优先队列来将边按照权重排序,用一个并查集来识别会形成环的边,以及一条队列来保存最小生成树的所有边。

相比Prim算法,我认为 Kruskal 算法实现起来更简单。

伪代码:

(1)对所有的边从小到大排序
(2)while(mstEdgeCnt < n - 1) do{
				取权值最小的边(u,v);
 				if(u,v不连通){
						将(u,v)加入T;
						mstEdgeCnt++;
				}
				将边(u,v)从集合E中删除;
    }

comments powered by Disqus

相关文章

在电脑上安装 Openwrt 作为旁路网关

🤔场景 既然回家了,有了家用路由器,就希望各个设备能够不需要安装对应的软件而直接科学上网、屏蔽广告等。 但原来的路由器太小众,没人提供相应的固件,也就是说没法刷机。 后来,我看到有关旁路网关的介绍,觉得这可能是一种解决方案。

阅读更多
如何在 React 中进行状态管理?使用 Zustand!

计数器 import { create } from 'zustand' const useStore = create(set => ({ count: 1, inc: () => set(state => ({ count: state.count + 1 })), })) function Controls() { const inc = useStore(state => state.inc) return <button onClick={inc}>one up</button> } function Counter() { const count = useStore(state => state.count) return <h1>{count}</h1> } 用法 创建状态 state 操作 action Basic typescript usage doesn’t require anything special except for writing create<State>()(...) instead of create(...)… import { create } from 'zustand' interface BearState { bears: number increase: (by: number) => void } const useBearStore = create<BearState>()((set) => ({ bears: 0, increase: (by) => set((state) => ({ bears: state.bears + by })), })) const useFishStore = create((set) => ({ salmon: 1, tuna: 2, deleteEverything: () => set({}, true), // clears the entire store, actions included deleteTuna: () => set((state) => omit(state, ['tuna']), true), })) const useSoundStore = create((set, get) => ({ sound: "grunt", action: () => { const sound = get().sound // you still have access to state outside of it through get // ... } }) export default useBearStore 在 react 之外使用呢?

阅读更多
什么软件才能让你的 macOS 更好用?

动机 起因是我重置了系统,然后发现过去的习惯都要重新来一遍,于是为什么不写一篇文章呢? brew install --cask microsoft-edge calibre sogouinput mos snipaste iina iterm2 rectangle 这里先给出一份 CheckList: 软件 clash for windows homebrew microsoft onenote & outlook & edge wechat & qq sogouinput、微信输入法 Desktop Pets:App Store 上的有趣软件,养一个电子宠物吧 Notion:必备人生管理软件,管理你的任务、物品、健身情况等,自定义能力超强的数据库 阿里云盘:不限速云盘 Calibre:电子书管理器 mos: 鼠标与触控板方向不一致的解决方案 Snipaste:截图贴图 iina:超好用的播放器,配合网络上资源站的视频地址,完全不会发热 iterm2:可以透明背景、图片背景的终端 Lens:管理 k8s 神器 Rectangle:向 windows 一样排布窗口 Paragon NTFS for Mac:希捷官网下载是免费的 软件和固件下载 | Support Seagate US 系统设置:键盘快捷键、触发角、默认网页浏览器、调度中心使窗口按应用程序成组 ActivityWatch:时间追踪工具 Typora:markdown 编辑器,剪贴板的图片能给你自动复制到当前文件夹下,很适合本地写博客 Squash:图片压缩工具 macOS Assistant: macOS 小助手,一键 bypass 签名 LocalSend:本地传输文件,特别是往安卓设备传输东西 浏览器插件 简悦:纯净阅读 Adblock plus:屏蔽广告 Dark Reader:暗黑模式 Menu fish:古诗词标签页 Relingo:英语生词自动标记 Wayback Machine:网站记录备份 Stylus:重新编辑网站 CSS 样式 Wappalyzer:网站使用了哪些技术栈 Web Clipper(配合语雀):剪藏 FireShot:截屏 篡改猴(浏览器同步脚本) Microsoft编辑器:检查拼写和语法 命令行 oh-my-zsh:一定要用 zsh Roboto Mono for powerline 字体:在 iterm2 中设置 zsh 插件 zsh-syntax-highlighting zsh-autosuggestions spaceship-ember spaceship-vi-mode autojump:j neovim:nvim 开发 TabNine:GitHub Copilot 平替 visual-studio-code:开发必备 主旨 ZSH 配置 Spaceship 安装与配置 https://github.com/spaceship-prompt/spaceship-prompt

阅读更多