图论模板
程序员文章站
2022-03-03 11:34:00
...
1. 黑白染色法
黑白染色法可用于判断奇圈,从而判定是否为二分图。
package main
import (
"fmt"
)
const (
Black = -1
Gray = 0
White = 1
)
const (
maxVertexNum = 110
maxEdgeNum = maxVertexNum * maxVertexNum
)
type Edge struct {
u, v, next int
}
// 存储图相关信息
var head [maxVertexNum]int
var edges [maxEdgeNum]Edge
var edgeNum int
// InitGraph 初始化构建
func InitGraph() {
edgeNum = 0
for i := 0; i < maxVertexNum; i++ {
head[i] = -1
}
}
// AddEdge 有向图 或 无向图
func AddEdge(u, v int) {
// 正向边
edges[edgeNum] = Edge{u: u, v: v, next: head[u]}
head[u] = edgeNum
edgeNum++
// 反向边
edges[edgeNum] = Edge{u: v, v: u, next: head[v]}
head[v] = edgeNum
edgeNum++
}
// IsExistOddCycle
func IsExistOddCycle(n int) bool {
color := make([]int, n+1)
var dfs func(u, c int) bool
dfs = func(u, c int) bool {
color[u] = c
for i := head[u]; i != -1; i = edges[i].next {
if color[edges[i].v] == Gray {
return dfs(edges[i].v, -c)
}
if color[u] == color[edges[i].v] {
return true
}
}
return false
}
var isExist bool
for i := 1; i <= n; i++ {
if color[i] == Gray {
isExist = isExist || dfs(i, Black)
}
if isExist {
break
}
}
return isExist
}
func main() {
// 1. 奇环
InitGraph()
AddEdge(1, 2)
AddEdge(2, 3)
AddEdge(3, 1)
fmt.Println(IsExistOddCycle(3))
// 2. 偶环
InitGraph()
AddEdge(1, 2)
AddEdge(2, 1)
fmt.Println(IsExistOddCycle(2))
// 3. 无环
InitGraph()
AddEdge(1, 2)
AddEdge(2, 3)
fmt.Println(IsExistOddCycle(3))
// 4. 奇环 + 偶环
InitGraph()
AddEdge(1, 2)
AddEdge(2, 3)
AddEdge(3, 1)
AddEdge(4, 5)
AddEdge(5, 6)
fmt.Println(IsExistOddCycle(6))
}
2. 次短路径(Dijkstra + Heap)
package main
import (
"container/heap"
"fmt"
)
type Node struct {
d int // 距离 d
v int // 顶点 v
}
// NodeHeap 顶点堆
type NodeHeap []Node
// Len 长度
func (sh *NodeHeap) Len() int { return len(*sh) }
// Less 比较函数
// < : 小顶堆
// > : 大顶堆
func (sh *NodeHeap) Less(i, j int) bool { return (*sh)[i].d < (*sh)[j].d }
// Swap 交换函数
func (sh *NodeHeap) Swap(i, j int) { (*sh)[i], (*sh)[j] = (*sh)[j], (*sh)[i] }
// Pop heap pop
func (sh *NodeHeap) Pop() interface{} {
n := len(*sh)
x := (*sh)[n-1]
*sh = (*sh)[:n-1]
return x
}
// Push heap push
func (sh *NodeHeap) Push(x interface{}) {
*sh = append(*sh, x.(Node))
}
// heap.Init()
// heap.Pop()
// heap.Push()
const (
maxN = 1010
maxE = 1010 * 1010 / 2
inf = 0x3f3f3f3f
)
type Edge struct {
u int
v int
w int
next int
}
var (
dis [maxN][2]int
edges = [maxE]Edge{}
head = [maxN]int{}
edgeNum int
)
// n : 顶点个数,编号 0 ~ n-1
func initGraph(n int) {
edgeNum = 0
for i := 0; i < n; i++ {
head[i] = -1
}
}
// 无向图加边
// 有向图加边
func addEdge(u, v, w int) {
edges[edgeNum] = Edge{u: u, v: v, w: w}
edges[edgeNum].next = head[u]
head[u] = edgeNum
edgeNum++
edges[edgeNum] = Edge{u: v, v: u, w: w}
edges[edgeNum].next = head[v]
head[v] = edgeNum
edgeNum++
}
// n: 顶点编号 0 ~ n-1
// src: 源点
// 注意: 次短路径的求解过程中,路径可以重复走
func solve(n int, src int) {
var (
ndHeap = &NodeHeap{}
nd Node
u int
v int
d int
)
for i := 0; i < n; i++ {
dis[i][0] = inf // 最短路径
dis[i][1] = inf // 次短路径
}
// dis[src][0], dis[src][1] = 0, 0
dis[src][0] = 0
*ndHeap = append(*ndHeap, Node{0, src})
heap.Init(ndHeap)
for len(*ndHeap) > 0 {
nd = heap.Pop(ndHeap).(Node)
if dis[nd.v][1] < nd.d { // 注意: 此处只能取 < ,而不能取 <=
continue
}
u = nd.v
for i := head[u]; i != -1; i = edges[i].next {
v = edges[i].v
d = nd.d + edges[i].w
if dis[v][0] > d {
// TODO: 维护最短路径上前继节点
dis[v][0], d = d, dis[v][0]
heap.Push(ndHeap, Node{dis[v][0], v})
}
if dis[v][0] <= d && dis[v][1] > d { // 注意: dis[v][0] <= d 而不是 dis[v][0] < d
// TODO: 维护次短路径上前继节点
dis[v][1] = d
heap.Push(ndHeap, Node{dis[v][1], v})
}
}
}
return
}
func main() {
// 1. 最短路径唯一
initGraph(3)
addEdge(0, 1, 1)
addEdge(1, 2, 2)
solve(3, 0)
for i := 0; i < 3; i++ {
fmt.Println("Test: ", i, dis[i][0], dis[i][1])
}
fmt.Println("--------------------------")
// 2. 最短路径和次短路径长度不相同
initGraph(4)
addEdge(0, 1, 1)
addEdge(0, 2, 2)
addEdge(1, 3, 1)
addEdge(2, 3, 1)
solve(4, 0)
for i := 0; i < 4; i++ {
fmt.Println("Test: ", i, dis[i][0], dis[i][1])
}
fmt.Println("--------------------------")
// 3. 最短路径和次短路径长度相同
initGraph(4)
addEdge(0, 1, 1)
addEdge(0, 2, 1)
addEdge(1, 3, 1)
addEdge(2, 3, 1)
solve(4, 0)
for i := 0; i < 4; i++ {
fmt.Println("Test: ", i, dis[i][0], dis[i][1])
}
}
下一篇: spring中实例化Bean的三种方式