几个概念：有向图、无向图、加权图、简单图、联通、联通分量、生成树、强连通分量、强联通图
图的存储：邻接矩阵（二维、一维）、邻接表
图的遍历：深搜、广搜
（无向加权图）最小生成树：kruskal算法过程及证明、prime算法过程
单源最短距离问题：dijkstra算法
深搜和回溯的区别：个人理解是深搜是图的一种遍历方式（树也属于图），回溯是只用于树
package main
import (
"fmt"
"math"
"sort"
"strconv"
)
func main() {
vertexes := []string{"A", "B", "C", "D", "E", "F"}
edges := []string{
"AB,4", "AC,8", "AD,45", "AF,3",
"BA,4", "BC,14", "BE,20", "BF,5",
"CA,8", "CB,14", "CD,28", "CE,9",
"DA,45", "DC,28", "DE,10",
"EB,20", "EC,9", "EF,13", "ED,10",
"FA,3", "FB,5", "FE,13",
}
g := NewGraph(vertexes, edges)
g.DFS()
g.BFS(0)
g.Kruskal()
g.Prime(0)
g.Dijkstra(0)
}
type Vertex struct {
Name string
FirstEdge *Edge
}
type Edge struct {
V int
W int
Cost int
NextEdge *Edge
}
type Graph struct {
VertexNum int
EdgeNum int
AdjacentList []Vertex
}
func NewGraph(vertexes []string, edges []string) Graph {
g := Graph{}
g.VertexNum = len(vertexes)
g.EdgeNum = len(edges) / 2 // 无向图
g.AdjacentList = make([]Vertex, len(vertexes))
m := map[string]int{}
for i, vertex := range vertexes {
v := Vertex{
Name: vertex,
}
g.AdjacentList[i] = v
m[vertex] = i
}
for _, edgeStr := range edges {
v := m[string(edgeStr[0])]
w := m[string(edgeStr[1])]
cost, _ := strconv.Atoi(edgeStr[3:])
edge := Edge{
V: v,
W: w,
Cost: cost,
NextEdge: g.AdjacentList[v].FirstEdge,
}
g.AdjacentList[v].FirstEdge = &edge
}
return g
}
func (g *Graph) DFS() {
visited := map[int]bool{}
for i, _ := range g.AdjacentList {
g.dfs(i, visited)
}
}
func (g *Graph) dfs(v int, visited map[int]bool) {
if visited[v] {
return
}
vertex := g.AdjacentList[v]
visited[v] = true
fmt.Println("先深遍历", vertex.Name)
edge := vertex.FirstEdge
for edge != nil {
if visited[edge.W] {
edge = edge.NextEdge
continue
}
g.dfs(edge.W, visited)
}
}
func (g *Graph) BFS(start int) {
visited := map[int]bool{}
var queue = []int{
start,
}
i := 0
for ; i < len(queue); i++ {
k := queue[i]
vertex := g.AdjacentList[k]
if visited[k] {
continue
}
fmt.Println("先广遍历", vertex.Name)
visited[k] = true
edge := vertex.FirstEdge
for edge != nil {
if !visited[edge.W] {
queue = append(queue, edge.W)
}
edge = edge.NextEdge
}
}
}
func (g *Graph) Kruskal() (mst []Edge) {
sortedEdges := g.sortEdges()
mst = make([]Edge, g.VertexNum-1)
i := 0
l := 0
selectedVertexes := map[int]bool{}
for l < g.VertexNum-1 {
edge := sortedEdges[i]
if !(selectedVertexes[edge.V] && selectedVertexes[edge.W]) {
selectedVertexes[edge.V] = true
selectedVertexes[edge.W] = true
mst[l] = edge
l++
}
i++
}
fmt.Println("Kruskal结果")
for _, edge := range mst {
fmt.Println(g.AdjacentList[edge.V].Name+g.AdjacentList[edge.W].Name, edge.Cost)
}
return
}
func (g *Graph) sortEdges() []Edge {
visited := map[int]bool{}
edges := make([]Edge, g.EdgeNum)
l := 0
for i, vertex := range g.AdjacentList {
edge := vertex.FirstEdge
for edge != nil {
if !visited[edge.W] {
edges[l] = *edge
l++
}
edge = edge.NextEdge
}
visited[i] = true
}
sort.Slice(edges, func(i, j int) bool {
return edges[i].Cost < edges[j].Cost
})
return edges
}
func (g *Graph) Prime(start int) (mst []Edge) {
fmt.Println("prime计算过程")
selectedVertex := map[int]bool{start: true}
unSelectedVertex := map[int]Edge{}
lastSelectVertex := start
for len(mst) < g.VertexNum-1 {
var minCost = math.MaxInt64
var minEdge Edge
for i, _ := range g.AdjacentList {
if selectedVertex[i] {
continue
}
newCost, _ := g.getCost(lastSelectVertex, i)
if edge, initialized := unSelectedVertex[i]; !initialized || newCost < edge.Cost {
unSelectedVertex[i] = Edge{
V: lastSelectVertex,
W: i,
Cost: newCost,
}
}
if unSelectedVertex[i].Cost < minCost {
minCost = unSelectedVertex[i].Cost
minEdge = unSelectedVertex[i]
}
}
fmt.Println()
for i, edge := range unSelectedVertex {
if selectedVertex[edge.W] {
continue
}
fmt.Println(i, g.AdjacentList[edge.V].Name+g.AdjacentList[edge.W].Name, edge.Cost)
}
fmt.Println("选择最小边: ",
g.AdjacentList[minEdge.V].Name+g.AdjacentList[minEdge.W].Name, minEdge.Cost)
mst = append(mst, minEdge)
lastSelectVertex = minEdge.W
selectedVertex[minEdge.W] = true
}
fmt.Println("最终结果")
for i, edge := range mst {
fmt.Println(i, g.AdjacentList[edge.V].Name+g.AdjacentList[edge.W].Name, edge.Cost)
}
return
}
func (g *Graph) getVertex(i int) Vertex {
return g.AdjacentList[i]
}
func (g *Graph) getCost(from int, to int) (cost int, isInfinity bool) {
startVertex := g.AdjacentList[from]
edge := startVertex.FirstEdge
for edge != nil {
if edge.W == to {
return edge.Cost, false
}
edge = edge.NextEdge
}
return math.MaxInt64, true
}
func (g *Graph) Dijkstra(start int) {
fmt.Println("dijkstra计算过程")
type vertexRecord struct {
path string
cost int
selected bool
}
vertexes := make([]vertexRecord, g.VertexNum)
for i, _ := range g.AdjacentList {
if i == start {
vertexes[start] = vertexRecord{
path: g.getVertex(start).Name,
cost: 0,
selected: true,
}
continue
}
cost, _ := g.getCost(start, i)
vertexes[i] = vertexRecord{
path: g.getVertex(start).Name + g.getVertex(i).Name,
cost: cost,
}
}
lastSelect := start
for i := 0; i < g.VertexNum-1; i++ {
minCost := math.MaxInt64
minCostVertex := 0
for j, _ := range vertexes {
if vertexes[j].selected {
continue
}
lastSelectVertex := vertexes[lastSelect]
cost, isInfinity := g.getCost(lastSelect, j)
if !isInfinity && lastSelectVertex.cost+cost < vertexes[j].cost {
vertexes[j].cost = lastSelectVertex.cost + cost
vertexes[j].path = lastSelectVertex.path + g.getVertex(j).Name
}
fmt.Println(fmt.Sprintf(`A到%s最近的路径是%s，其耗费是%d`,
g.getVertex(j).Name, vertexes[j].path, vertexes[j].cost))
if vertexes[j].cost < minCost {
minCost = vertexes[j].cost
minCostVertex = j
}
}
fmt.Println()
fmt.Println("本次最短路径为", vertexes[minCostVertex].path, vertexes[minCostVertex].cost)
fmt.Println()
vertexes[minCostVertex].selected = true
lastSelect = minCostVertex
}
for i, vertex := range vertexes {
fmt.Println(i, vertex.path, vertex.cost)
}
}
网友评论