Minimum Spanning Tree 是用來解決與連通圖（Connected Graph）相關的問題。
生成樹是一種特殊的子圖，它包含了原始圖的所有節點，但只有足夠的邊來確保整個圖是連通的，同時不包含任何形成循環的邊。
最小生成樹則是在所有可能的生成樹中，總權重最小的一棵。
最小生成樹的特點如下：
常見的最小生成樹演算法包括「Kruskal 演算法」和「Prim 演算法」，它們可以用來找到圖中的最小生成樹。這些演算法的運作方式如下：
// Kruskal's algorithm in Kotlin
import java.util.PriorityQueue
// Edge class
data class Edge(val from: Int, val to: Int, val weight: Int)
// Graph class
class Graph(val vertices: Int) {
val nodes = IntArray(vertices)
val edges = mutableListOf<Edge>()
fun addEdge(from: Int, to: Int, weight: Int) {
nodes[from] = from
nodes[to] = to
edges.add(Edge(from, to, weight))
}
}
// Union-Find class
class UnionFind(val size: Int) {
val parent = IntArray(size)
val rank = IntArray(size)
init {
for (i in 0 until size) {
parent[i] = i
}
}
fun find(x: Int): Int {
if (parent[x] != x) {
parent[x] = find(parent[x])
}
return parent[x]
}
fun union(x: Int, y: Int) {
val rootX = find(x)
val rootY = find(y)
if (rootX == rootY) return
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX
} else {
parent[rootY] = rootX
rank[rootX]++
}
}
fun connected(x: Int, y: Int): Boolean {
return find(x) == find(y)
}
}
class Kruskal(val graph: Graph) {
val mst = mutableListOf<Edge>()
val uf = UnionFind(graph.vertices)
val pq = PriorityQueue<Edge>(graph.edges.size, compareBy { it.weight })
fun run() {
for (edge in graph.edges) {
pq.add(edge)
}
while (pq.isNotEmpty()) {
val edge = pq.poll()
if (!uf.connected(edge.from, edge.to)) {
uf.union(edge.from, edge.to)
mst.add(edge)
}
}
}
}
// main function
fun main(args: Array<String>) {
val graph = Graph(5)
graph.addEdge(0, 1, 2)
graph.addEdge(0, 3, 6)
graph.addEdge(1, 2, 3)
graph.addEdge(1, 3, 8)
graph.addEdge(1, 4, 5)
graph.addEdge(2, 4, 7)
graph.addEdge(3, 4, 9)
val kruskal = Kruskal(graph)
kruskal.run()
println("Minimum Spanning Tree:")
for (edge in kruskal.mst) {
println("${edge.from} -> ${edge.to} = ${edge.weight}")
}
}
// Prim's algorithm in Kotlin
import java.util.PriorityQueue
// Edge class
data class Edge(val from: Int, val to: Int, val weight: Int)
// Graph class
class Graph(val vertices: Int) {
val nodes = IntArray(vertices)
val edges = mutableListOf<Edge>()
fun addEdge(from: Int, to: Int, weight: Int) {
nodes[from] = from
nodes[to] = to
edges.add(Edge(from, to, weight))
}
}
class Prim(val graph: Graph) {
val mst = mutableListOf<Edge>()
val visited = mutableSetOf<Int>()
val pq = PriorityQueue<Edge>(graph.edges.size, compareBy { it.weight })
fun run() {
val start = graph.nodes[0]
visited.add(start)
addEdges(start)
while (pq.isNotEmpty()) {
val edge = pq.poll()
if (edge.to !in visited) {
mst.add(edge)
visited.add(edge.to)
addEdges(edge.to)
}
}
}
fun addEdges(node: Int) {
for (edge in graph.edges) {
if (edge.from == node && edge.to !in visited) {
pq.add(edge)
}
}
}
}
// main function
fun main(args: Array<String>) {
val graph = Graph(5)
graph.addEdge(0, 1, 2)
graph.addEdge(0, 3, 6)
graph.addEdge(1, 2, 3)
graph.addEdge(1, 3, 8)
graph.addEdge(1, 4, 5)
graph.addEdge(2, 4, 7)
graph.addEdge(3, 4, 9)
val prim = Prim(graph)
prim.run()
println("Minimum Spanning Tree:")
for (edge in prim.mst) {
println("${edge.from} -> ${edge.to} = ${edge.weight}")
}
}
Shortest Path 是一種在圖形或網絡中找到兩個節點之間最短距離的問題。
在最短路徑問題中，通常有兩種常見的演算法：
// Dijstra algorithm in Kotlin
class Dijkstra {
private val graph: Array<IntArray>
private val n: Int
private val dist: IntArray
private val visited: BooleanArray
constructor(graph: Array<IntArray>, n: Int) {
this.graph = graph
this.n = n
dist = IntArray(n)
visited = BooleanArray(n)
}
fun dijkstra(start: Int) {
for (i in 0 until n) {
dist[i] = Int.MAX_VALUE
visited[i] = false
}
dist[start] = 0
for (i in 0 until n - 1) {
val u = minDistance(dist, visited)
visited[u] = true
for (v in 0 until n) {
if (!visited[v] && graph[u][v] != 0 && dist[u] != Int.MAX_VALUE && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v]
}
}
}
printSolution(dist, n)
}
private fun minDistance(dist: IntArray, visited: BooleanArray): Int {
var min = Int.MAX_VALUE
var minIndex = -1
for (v in 0 until n) {
if (!visited[v] && dist[v] <= min) {
min = dist[v]
minIndex = v
}
}
return minIndex
}
private fun printSolution(dist: IntArray, n: Int) {
println("Vertex Distance from Source")
for (i in 0 until n) {
println(i.toString() + ": " + dist[i])
}
}
}
// main function
fun main(args: Array<String>) {
val graph = arrayOf(intArrayOf(0, 4, 0, 0, 0, 0, 0, 8, 0),
intArrayOf(4, 0, 8, 0, 0, 0, 0, 11, 0),
intArrayOf(0, 8, 0, 7, 0, 4, 0, 0, 2),
intArrayOf(0, 0, 7, 0, 9, 14, 0, 0, 0),
intArrayOf(0, 0, 0, 9, 0, 10, 0, 0, 0),
intArrayOf(0, 0, 4, 14, 10, 0, 2, 0, 0),
intArrayOf(0, 0, 0, 0, 0, 2, 0, 1, 6),
intArrayOf(8, 11, 0, 0, 0, 0, 1, 0, 7),
intArrayOf(0, 0, 2, 0, 0, 0, 6, 7, 0))
val t = Dijkstra(graph, 9)
t.dijkstra(0)
}
// Bellman Ford Algorithm in Kotlin
class BellmanFord {
fun bellmanFord(graph: Array<IntArray>, V: Int, E: Int, src: Int) {
// Initialize distance of all vertices as infinite.
val dis = IntArray(V)
for (i in 0 until V) dis[i] = Int.MAX_VALUE
// initialize distance of source as 0
dis[src] = 0
// Relax all edges |V| - 1 times. A simple shortest
// path from src to any other vertex can have at-most |V| - 1 edges
for (i in 0 until V - 1) {
for (j in 0 until E) {
if (dis[graph[j][0]] != Int.MAX_VALUE && dis[graph[j][0]] + graph[j][2] < dis[graph[j][1]])
dis[graph[j][1]] = dis[graph[j][0]] + graph[j][2]
}
}
// check for negative-weight cycles.
for (i in 0 until E) {
val x = graph[i][0]
val y = graph[i][1]
val weight = graph[i][2]
if (dis[x] != Int.MAX_VALUE && dis[x] + weight < dis[y])
println("Graph contains negative weight cycle")
}
println("Vertex Distance from Source")
for (i in 0 until V) println("$i\t\t${dis[i]}")
}
}
// main function
fun main(args: Array<String>) {
val V = 5 // Number of vertices in graph
val E = 8 // Number of edges in graph
// Every edge has three values (u, v, w) where
// the edge is from vertex u to v. And weight
// of the edge is w.
val graph = arrayOf(
intArrayOf(0, 1, -1),
intArrayOf(0, 2, 4),
intArrayOf(1, 2, 3),
intArrayOf(1, 3, 2),
intArrayOf(1, 4, 2),
intArrayOf(3, 2, 5),
intArrayOf(3, 1, 1),
intArrayOf(4, 3, -3)
)
val bellmanFord = BellmanFord()
bellmanFord.bellmanFord(graph, V, E, 0)
}
所有 Code 可以在 Github 找到 ～
感謝各位讀者，我們明天見！
iThome鐵人賽
看影片追技術