数据结构基础 入门——图

用 Go 来实现链表、栈、队列、散列表、树、二叉树、堆、图

图的认识

图是一种较线性表和树更加复杂的数据结构，由顶点和连接每对顶点的边所构成的图形就是图。图由两个元素组成：节点 和 关系 。
在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相连。
图(Graph)是由顶点的有穷非空集合和顶点之间的集合组成，通常表示为G[V, E]，其中G表示一个图，V是图G的顶点集合，E是图G中边的集合。

应用场景

图数据库：
Neo4J是由Java实现的开源图数据库
JanusGraph是一个Linux基金会下的开源分布式图数据库

图

package main

import (
    "fmt"
)

type VertexType string //定义顶点的数据类型
type EdgeType int      //边的类型
const MAXVEX = 100     //最大的顶点数
const MAXVALUE = 65535 //无效数 （无穷大，也就是说此边不通）

type MGraph struct {
    vexs           [MAXVEX]VertexType  //定义一个数组，保存对应的顶点，可以保存65535个顶点
    arc            [MAXVEX][MAXVEX]int //定义一个二维数组，保存顶点对应的边，二维数组可以保存[65535][65535]
    numVer, numEdg int                 //边的数量，顶点的数量
    isTrav         [MAXVEX] bool       //设定某个节点是否遍历过，主要用于节点的遍历
    GType          byte                //定义图的类型，0:无向图  1：有向图
}

/*
    创建图：
*/
func createMGraph(mg *MGraph) {

    fmt.Println("请输入顶点数：")
    fmt.Scan(&mg.numVer)
    for i := 0; i < mg.numVer; i++ {
        fmt.Printf("请输入第%d个顶点：\n", i+1)
        var tempChar VertexType
        fmt.Scan(&tempChar)
        mg.vexs[i] = tempChar
        //fmt.Print("\n输入的内容为：", mg.vexs[i])

    }
    //顶点组成边，初始化
    for i := 0; i < mg.numVer; i++ {
        for j := 0; j < mg.numVer; j++ {
            mg.arc[i][j] = MAXVALUE

        }

    }
    fmt.Println("请输入边数：")
    fmt.Scan(&mg.numEdg)
    for i := 0; i < mg.numEdg; i++ {
        //fmt.Println("请分别输入坐标E（i,j）以及权重")
        fmt.Printf("请输入第%d条边的坐标E（i,j）以及权重\n", i+1)
        var i, j, weight int
        fmt.Scan(&i)
        fmt.Scan(&j)
        fmt.Scan(&weight)
        mg.arc[i][j] = weight
        if mg.GType == 0 {
            mg.arc[j][i] = weight //无向图：数据依据对角线对称
        }

        //fmt.Printf("输入的权重为：%d", mg.arc[i][j])
    }

    /*for i := 0; i < mg.numVer; i++ {
        for j := i; j < mg.numVer; j++ {
            fmt.Println("----------")
            fmt.Println(mg.arc[i][j])
            //fmt.Println(mg.arc[j][i])
        }
    }
    for i := 0; i < mg.numEdg; i++ {
        fmt.Println(mg.vexs[i])
    }*/
}

/*
    清空图：1）清空边对应的权重   2）清空顶点组成的数组
*/
func ClearGraph(mg *MGraph) {
    for i := 0; i < mg.numVer; i++ {
        for j := 0; j < i; j++ {
            mg.arc[i][j] = MAXVALUE
        }
    }
    for i := 0; i < mg.numVer; i++ {
        mg.vexs[i] = ""
    }
}
func ShowGraph(mg *MGraph) {
    fmt.Println()
    for i := 0; i < mg.numVer; i++ {
        fmt.Printf("\t\t%s", mg.vexs[i])
    }
    fmt.Println()
    for i := 0; i < mg.numVer; i++ {
        fmt.Printf("%s\t\t", mg.vexs[i])
        for j := 0; j < mg.numVer; j++ {
            if mg.arc[i][j] == MAXVALUE {
                fmt.Printf("%s\t\t", "Z")
            } else {
                fmt.Printf("%d\t\t", mg.arc[i][j])
            }
        }
        fmt.Println()
    }

}

/*
图的遍历：遍历图就是逐个访问图中的所有节点
深度优先遍历算法思想：
1）从数组isTrav中选择一个未被遍历的顶点V（Vi），将其标记为true，表示已经访问过。
2）从Vi的一个未被访问的邻接点出发进行深度优先遍历；
3）重复 2），直至图中的所用和Vi有路径相通的顶点都被访问过。
4）重复1）-3）的操作，直到图中所用节点都被访问过
*/

/*
    fun：从第 n个节点开始，深度遍历图
*/
func DeepTraOne(mg *MGraph, n int) {
    mg.isTrav[n] = true
    fmt.Print("---->", mg.vexs[n])
    for i := 0; i < mg.numVer; i++ {
        if mg.arc[n][i] != MAXVALUE && mg.isTrav[n] != true {
            DeepTraOne(mg, i)
        }
    }
}

/*
    fun:通过 DeepTraOne（）函数，遍历所有的节点
*/
func DeepTraGraph(mg *MGraph) {
    //清除遍历标志位
    for i := 0; i < mg.numVer; i++ {
        mg.isTrav[i] = false
    }

    for i := 0; i < mg.numVer; i++ {
        if mg.isTrav[i] == false {
            DeepTraOne(mg, i)
        }
    }
    fmt.Println()

}
func main() {

    mg := MGraph{}
    createMGraph(&mg)
    ShowGraph(&mg)
    fmt.Println("遍历图：")
    DeepTraGraph(&mg)

}

go run xxx.go

请输入顶点数：
10
请输入第1个顶点：
1
请输入第2个顶点：
2
请输入第3个顶点：
3
请输入第4个顶点：
4
请输入第5个顶点：
5
请输入第6个顶点：
6
请输入第7个顶点：
7
请输入第8个顶点：
8
请输入第9个顶点：
9
请输入第10个顶点：
10
请输入边数：
5
请输入第1条边的坐标E（i,j）以及权重
1 2 3
请输入第2条边的坐标E（i,j）以及权重
1 2 4
请输入第3条边的坐标E（i,j）以及权重
2 1 5
请输入第4条边的坐标E（i,j）以及权重
4 1 4
请输入第5条边的坐标E（i,j）以及权重
5 5 5

                1               2               3               4               5               6               7               8               9               10
1               Z               Z               Z               Z               Z               Z               Z               Z               Z               Z

2               Z               Z               5               Z               4               Z               Z               Z               Z               Z

3               Z               5               Z               Z               Z               Z               Z               Z               Z               Z

4               Z               Z               Z               Z               Z               Z               Z               Z               Z               Z

5               Z               4               Z               Z               Z               Z               Z               Z               Z               Z

6               Z               Z               Z               Z               Z               5               Z               Z               Z               Z

7               Z               Z               Z               Z               Z               Z               Z               Z               Z               Z

8               Z               Z               Z               Z               Z               Z               Z               Z               Z               Z

9               Z               Z               Z               Z               Z               Z               Z               Z               Z               Z

10              Z               Z               Z               Z               Z               Z               Z               Z               Z               Z

遍历图：
---->1---->2---->3---->4---->5---->6---->7---->8---->9---->10

挺懵的 不知道 你们感觉如何？

参考资料
www.cnblogs.com/Christbao/p/132089...
blog.csdn.net/qq_22211217/article/...
blog.csdn.net/weixin_42117918/arti...

本作品采用《CC 协议》，转载必须注明作者和本文链接