go语言实现 数据结构 图以及图的遍历

学习c++算法的时候到了图这里就卡住了，学go的时候又重新拿起了书，曾经回过头的南墙，有一天还是会想再撞一撞。

利用深度优先搜索来遍历图

package main

import "fmt"

var vertex = 5
var edge = 5
var sum int
var book[10]int
var arr[10][10]int

func dfs(n int){
    fmt.Println(n)
    sum++
    if sum == vertex {return}
    for i:=1; i<=vertex; i++ {
        if arr[n][i]==1 && book[i]==0 {
            book[i] = 1
            dfs(i)
        }
    }
}

func main(){
    var x , y int
    //初始化二维数组
    for i:=1; i<=vertex; i++    {
        for j:=1; j<=vertex; j++ {
            if i==j {
                arr[i][j]=0
            }else{
                arr[i][j]=9
            }
        }
    }
    //读入边
    for i:=1; i<=edge; i++ {
        fmt.Scan(&x,&y)
        arr[x][y]=1
        arr[y][x]=1
    }
    //从节点1开始遍历
    book[1]=1
    dfs(1)
}

用excel表格做了一个dfs函数运行过程的推导，深度优先搜索遍历的最终结果是1，2，4，3，5。

递归版本的宽搜

package main

import "fmt"

var vertex = 5
var edge = 5
var tail = 1
var que[1001]int 
var book[10]int
var arr[10][10]int

func bfs(n int){
    if tail > vertex {return}
    for i:=1;i<=vertex;i++{
        if arr[que[n]][i] ==1 && book[i] ==0 {
            book[i]=1
            que[tail]=i
            tail++
        }
    }
    bfs(n+1)
}

func main(){
    var x , y int
    //初始化二维数组
    for i:=1; i<=vertex; i++    {
        for j:=1; j<=vertex; j++ {
            if i==j {
                arr[i][j]=0
            }else{
                arr[i][j]=9
            }
        }
    }
    //读入边
    for i:=1; i<=edge; i++ {
        fmt.Scan(&x,&y)
        arr[x][y]=1
        arr[y][x]=1
    }
    //从节点1开始遍历
    que[tail] =1
    tail++
    book[1]=1
    bfs(1)
    for i:=1;i<tail;i++{
        fmt.Println(que[i])
    }
}

非递归方式宽搜

package main

import "fmt"

const MAX = 100

var vertex = 5
var edge = 5
var que [MAX]int
var book [MAX]bool
var arr [MAX][MAX]int
var head = 1  // 队列头部
var tail = 1  // 队列尾部

func bfs() {
    for head < tail {
        for i := 1; i <= vertex; i++ {
            if arr[que[head]][i] == 1 && !book[i] {
                book[i] = true
                que[tail] = i
                tail++
            }
        }
        head++
    }
}

func main() {
    var x, y int
    
    // 初始化二维数组
    for i := 1; i <= vertex; i++ {
        for j := 1; j <= vertex; j++ {
            if i == j {
                arr[i][j] = 0
            } else {
                arr[i][j] = 9
            }
        }
    }
    
    // 读入边
    fmt.Println("请输入", edge, "条边：")
    for i := 1; i <= edge; i++ {
        fmt.Scan(&x, &y)
        arr[x][y] = 1
        arr[y][x] = 1
    }
    
    // 从节点1开始遍历
    que[tail] = 1  // que[1] = 1
    tail++         // tail = 2
    book[1] = true
    
    bfs()
    
    // 输出结果
    for i := 1; i < tail; i++ {
        fmt.Print(que[i], " ")
    }
    fmt.Println()
}