欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图论模板

程序员文章站 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])
	}
}
相关标签: 图论