Java中如何实现最小生成树算法？
- 内容介绍
- 文章标签
- 相关推荐
本文共计3908个文字，预计阅读时间需要16分钟。
定义：在无向图\( G=(V, E) \)中，\( (u, v) \)为连接顶点\( u \)和顶点\( v \)的边，\( (u) \)和\( (v) \)分别为顶点\( u \)和顶点\( v \)的邻接顶点集，\( w(u, v) \)为边\( (u, v) \)的权重。若存在边子集\( T \subseteq E \)且\( (V, T) \)为树，则使用\( w(T)=\sum_{(u, v) \in T} w(u, v) \)最小。
定义在一幅无向图 \(G=(V,E)\) 中，\((u, v)\) 为连接顶点 \(u\) 和顶点 \(v\) 的边，\(w(u,v)\) 为边的权重，若存在边的子集 \(T\subseteq E\) 且 \((V,T)\) 为树，使得
\[w(T)=\sum_{(u,v)\in T}w(u,v) \]最小，这称 \(T\) 为图 \(G\) 的最小生成树。
说的通俗点，最小生成树就是带权无向图中权值和最小的树。下图中黑色边所标识的就是一棵最小生成树（图片来自《算法第四版》），对于权值各不相同的连通图来说最小生成树只会有一棵：
带权图的实现在 《如何在 Java 中实现无向图》 中我们使用邻接表数组实现了无向图，其中邻接表上的每个节点的数据域只是一个整数，代表着一个顶点。为了方便最小生成树的迭代，我们将数据域换成 Edge 实例。Edge 有三个成员：顶点 v、顶点 w 和权重 weight，为了比较每一条边的权重，需要实现 Comparable 接口。
本文共计3908个文字，预计阅读时间需要16分钟。
定义：在无向图\( G=(V, E) \)中，\( (u, v) \)为连接顶点\( u \)和顶点\( v \)的边，\( (u) \)和\( (v) \)分别为顶点\( u \)和顶点\( v \)的邻接顶点集，\( w(u, v) \)为边\( (u, v) \)的权重。若存在边子集\( T \subseteq E \)且\( (V, T) \)为树，则使用\( w(T)=\sum_{(u, v) \in T} w(u, v) \)最小。
定义在一幅无向图 \(G=(V,E)\) 中，\((u, v)\) 为连接顶点 \(u\) 和顶点 \(v\) 的边，\(w(u,v)\) 为边的权重，若存在边的子集 \(T\subseteq E\) 且 \((V,T)\) 为树，使得
\[w(T)=\sum_{(u,v)\in T}w(u,v) \]最小，这称 \(T\) 为图 \(G\) 的最小生成树。
说的通俗点，最小生成树就是带权无向图中权值和最小的树。下图中黑色边所标识的就是一棵最小生成树（图片来自《算法第四版》），对于权值各不相同的连通图来说最小生成树只会有一棵：
带权图的实现在 《如何在 Java 中实现无向图》 中我们使用邻接表数组实现了无向图，其中邻接表上的每个节点的数据域只是一个整数，代表着一个顶点。为了方便最小生成树的迭代，我们将数据域换成 Edge 实例。Edge 有三个成员：顶点 v、顶点 w 和权重 weight，为了比较每一条边的权重，需要实现 Comparable 接口。