图
准备找实习了，把忘了的东西从头捡一捡
基本实现
大一时候有个特别蠢的问题，一直老想为什么不内置图的实现，现在想想真是蠢到家了……
Go语言实现无向无环图
import "fmt"
//Implment by adjacency matrix
type graphadjMat struct {
vertices []int
adjMat [][]int
}
func newGraphAdjMat(vertices []int, edges [][]int) *graphadjMat {
n := len(vertices)
adjMat := make([][]int, n)
for i := range adjMat {
adjMat[i] = make([]int, n)
}
g := &graphadjMat{
vertices: vertices,
adjMat: adjMat,
}
for i := range edges {
g.addEdge(edges[i][0], edges[i][1])
}
return g
}
func (g *graphadjMat) addVertex(val int) {
n := g.size()
g.vertices = append(g.vertices, val)
newRow := make([]int, n)
g.adjMat = append(g.adjMat, newRow)
for i := range g.adjMat {
//Looking at the matirx horizontally,the action is euqivalent to inserting 0 at the end of the row
g.adjMat[i] = append(g.adjMat[i], 0)
}
}
func (g *graphadjMat) removeVertex(index int) {
if index >= g.size() {
fmt.Errorf("%s", "Index out of Bounds")
return
}
g.vertices = append(g.vertices[:index], g.vertices[index+1:]...)
g.adjMat = append(g.adjMat[:index], g.adjMat[index+1:]...)
for i := range g.adjMat {
g.adjMat[i] = append(g.adjMat[i][:index], g.adjMat[i][index+1:]...)
}
}
// acyclic graph [ˌeɪˈsaɪklɪk ɡræf]
func (g *graphadjMat) addEdge(i, j int) {
if i < 0 || j < 0 || i >= g.size() || j >= g.size() || i == j {
fmt.Errorf("%s", "Index out of bounds")
}
g.adjMat[i][j] = 1
g.adjMat[j][i] = 1
}
func (g *graphadjMat) removeEdge(i, j int) {
if i < 0 || j < 0 || i >= g.size() || j >= g.size() || i == j {
fmt.Errorf("%s", "Index out of bounds")
}
g.adjMat[i][j] = 0
g.adjMat[j][i] = 0
}
func (g *graphadjMat) size() int {
return len(g.vertices)
}
func sum[T int | int16 | int32 | int64](nums []T) T {
var sum T
for _, v := range nums {
sum += v
}
return sum
}
func max[T int | int16 | int32 | int64](a, b T) T {
if a > b {
return a
} else {
return b
}
}
func minWithT[T int | int16 | int32 | int64](numList ...T) T {
var minValue T = numList[0]
for _, v := range numList {
if minValue > v {
minValue = v
}
}
return minValue
}
type vertex struct {
val int
}
type graphadjMat struct {
vertices []int
adjMat [][]int
}
type graphAdjList struct {
adjList map[vertex][]vertex
}
//Implement by adjacency list
func newGraphAdjList(edges [][]vertex) *graphAdjList {
g := &graphAdjList{
adjList: make(map[vertex][]vertex),
}
for _, edge := range edges {
g.addVertex(edge[0])
g.addVertex(edge[1])
g.addEdge(edge[0], edge[1])
}
return g
}
func (g *graphAdjList) size() int {
return len(g.adjList)
}
func (g *graphAdjList) addVertex(ver vertex) {
_, ok := g.adjList[ver]
if ok {
fmt.Errorf("%s", "The vertex has been found")
return
}
g.adjList[ver] = make([]vertex, 0)
}
func (g *graphAdjList) deleteVertex(ver vertex) {
_, ok := g.adjList[ver]
if !ok {
panic("error,the vertex cant be found")
}
delete(g.adjList, ver)
for i, list := range g.adjList {
g.adjList[i] = deleteSliceElems(list, ver)
}
}
func (g *graphAdjList) addEdge(ver1, ver2 vertex) {
_, ok1 := g.adjList[ver1]
_, ok2 := g.adjList[ver2]
if !ok1 || !ok2 || ver1 == ver2 {
panic("Error")
}
g.adjList[ver1] = append(g.adjList[ver1], ver2)
g.adjList[ver2] = append(g.adjList[ver2], ver1)
}
func (g *graphAdjList) removeEdge(ver1, ver2 vertex) {
_, ok1 := g.adjList[ver1]
_, ok2 := g.adjList[ver2]
if !ok1 || !ok2 || ver1 == ver2 {
panic("Error")
}
g.adjList[ver1] = deleteSliceElems(g.adjList[ver1], ver1)
g.adjList[ver2] = deleteSliceElems(g.adjList[ver2], ver2)
}
func deleteSliceElems(slice []vertex, ver vertex) []vertex {
for i, v := range slice {
if v == ver {
slice = append(slice[:i], slice[i+1:]...)
break
}
}
return slice
}
Union-Find algorithm（并查集算法）
Overview
作为最小生成树算法的前置内容，以及解决部分问题的有效解法，并查集算法有必要学习并记录下来
API we need to implement（需要实现的API）
type UF struct{
func union(p,q int)
func connected(p,q int) bool
func count() int
}
union函数表示将p与q两节点连通connected函数表示判断p与q节点是否联通count函数将返回图中的连通分量数量- 请注意，上述内容不符合Go语言语法要求，仅是说明举例用途
结合一下离散数学的内容，连通是一种等价关系。满足自反性、对称性、传递性
How to implement（实现思路）
设定每个节点有一个指针指向其父节点，如果父节点是自身的节点就是根节点。所以一开始所有节点应该都算是根节点。
type UF struct{
count int
parents []int
}
func newUF(n int) *UF{
uf:=&UF{count:n,parents:make([]int,n)}
for i:=0;i<n:i++{
//Every node's parents is itself when initilize
uf.parents[i]=i
}
return uf
}
如果A节点需要与B节点联通，只需要将A节点的根节点连接到B节点的根节点即可。
func (uf *UF) unionWithPro(p, q int) {
rootP := uf.findWithPro(p)
rootQ := uf.findWithPro(q)
if rootP == rootQ {
return
}
uf.parents[rootP] = rootQ
uf.count--
}
但这样会出现问题，在极端情况下，可能会经过连接形成一条链表。也就是说此时高度为N，二叉树不平衡，这样会导致如下问题：
如果我们需要判断两节点是否联通，需要判断二者的根节点是否为同一节点，所以就需要一个API可以找到某节点的根节点：
func (uf *UF) findWithPro(x int) int {
for uf.parents[x] != x {
x = uf.parents[x]
}
return x
}
不难分析，这个函数会从某个节点向上遍历直至树根，时间复杂度为高度O(logN)，但可惜正如上面所言，当树极度不平衡时，会退化为O(N)，当数据量极大时，会造成很大的性能损失。所以需要优化。
优化
问题的根源在于union函数只是粗暴的把一个根节点接到另外一个，并没有考虑两种里哪一种可以更好的维护平衡。如果我们每次都将高度较小的树接到高度较大的树下面，就可以避免这一问题了。遂修改代码如下：
type UF struct {
//the amount of connected components in the graph
count int
//a node's parents node
parents []int
//every root node's tree's height
size []int
}
func newUF(n int) *UF {
uf := &UF{count: n, parents: make([]int, n), size: make([]int, n)}
for i := 0; i < n; i++ {
uf.parents[i] = i
uf.size[i] = 1
}
return uf
}
func (uf *UF) union(p, q int) {
rootP := uf.find(p)
rootQ := uf.find(q)
if rootP == rootQ {
return
}
sizeP := uf.size[rootP]
sizeQ := uf.size[rootQ]
if sizeP > sizeQ {
uf.parents[rootQ] = rootP
uf.size[rootP] += sizeQ
} else {
uf.parents[rootP] = rootQ
uf.size[rootQ] += sizeP
}
uf.count--
}
为了判断树对应的高度，我们还需要修改UF数据结构的定义，加入size数组，存储每个根节点对应树的高度。
至此，时间复杂度下降为O(logN)。
路径压缩
此时按照上面的代码，我们也许可以得到一颗这样的树。但其实我们还可以进一步优化，因为我们实际上只关心某两个节点的根节点是不是同一个，以便来判断连通与否。所以我们可以尝试压缩路径到同一层，这样就可以将时间复杂度降为O(1)
可以通过修改find函数的逻辑实现这一操作，有迭代法和递归法两种，此处只记录效果更好的递归法：
func (uf *UF) find(x int) int {
if uf.parents[x] != x {
//we move the current node to previous layer if it doesn't fit the condition
uf.parents[x] = uf.find(uf.parents[x])
}
return uf.parents[x]
}
如果采用迭代写法，会压缩成如下的效果
如果采用递归写法，会压缩成如下：
借助路径压缩，size数组就可以去掉，保留与否均可。
Kruskal
Overview
克鲁斯卡尔是一种贪心算法，用来求图中的最小生成树。每次都选择最小的边加入（前提是保证不会形成回路），以便得到全局权重和最小。所以我们需要以下手段：
- 能够选择权值最小的边（排序解决）
- 能够判断加入后是否形成回路（并查集解决）
实现
1584. 连接所有点的最小费用 - 力扣（LeetCode）
以上题为例，将并查集也用上。
首先解决第一点，将图中权值排序，遍历每个点，计算到其他点的距离，即为此边的权值。最后排序即可。
第二点，是否形成回路，每次我们都从排序好了的边集合中选取，选取前判断此边的两点是否连通，如果已连通就跳过，未连通便加入，并在并查集中连接两点。
有一个结论是，最终形成的最小生成树一定有n(节点数量)-1条边，当我们判断已经加入这么多条边时，就可以返回最后的结果
type UF struct {
count int
parents []int
size []int
}
func newUF(n int) *UF {
uf := &UF{count: n, parents: make([]int, n), size: make([]int, n)}
for i := 0; i < n; i++ {
uf.parents[i] = i
uf.size[i] = 1
}
return uf
}
func (uf *UF) counts() int {
return uf.count
}
func (uf *UF) find(x int) int {
if uf.parents[x] != x {
uf.parents[x] = uf.find(uf.parents[x])
}
return uf.parents[x]
}
func (uf *UF) union(p, q int) {
rootP := uf.find(p)
rootQ := uf.find(q)
if rootP == rootQ {
return
}
if uf.size[rootP] > uf.size[rootQ] {
uf.parents[rootQ] = rootP
uf.size[rootP] += uf.size[rootQ]
} else {
uf.parents[rootP] = rootQ
uf.size[rootQ] += uf.size[rootP]
}
uf.count--
}
func (uf *UF) connected(p, q int) bool {
rootP := uf.find(p)
rootQ := uf.find(q)
return rootP == rootQ
}
func minCostConnectPoints(points [][]int) int {
var ans = 0
type edge struct{ v, w, dis int }
edges := []edge{}
for i := 0; i < len(points); i++ {
for j := i + 1; j < len(points); j++ {
edges = append(edges, edge{i, j, int(cal_distance(points[i][0], points[i][1],
points[j][0], points[j][1]))})
}
}
sort.Slice(edges, func(i, j int) bool { return edges[i].dis < edges[j].dis })
graphUnion := newUF(len(points))
edgeCount := len(points) - 1
for _, v := range edges {
if graphUnion.connected(v.v, v.w) {
continue
} else {
ans += v.dis
edgeCount--
if edgeCount == 0 {
break
}
graphUnion.union(v.v, v.w)
}
}
return ans
}
func cal_distance(x1, y1, x2, y2 int) float64 {
x := math.Abs(float64(x1 - x2))
y := math.Abs(float64(y1 - y2))
return x + y
}