邻接表-Golang

最简单直接的办法一般就是使用邻接矩阵的办法来表示图,但是对于稀疏图来说边的数目想对来说比较少的情况下,使用邻接矩阵的办法会比较浪费资源,所以这里采用邻接表

Github

https://github.com/mohuishou/algorithm/tree/master/Graph

代码实现

package Graph

import (
	"bufio"
	"io"
	"os"
	"strconv"
	"strings"
)

// EdgeType 边的权值类型
type EdgeType int

// VextexType 顶点类型定义
type VextexType int

// VextexDataType 顶点值类型定义
type VextexDataType int

//EdgeNode 边的节点
type EdgeNode struct {
	Weight EdgeType   //权值
	V      VextexType //指向储存该顶点的下标
	Next   *EdgeNode  //指向下一条边
}

//VextexNode 顶点节点定义
type VextexNode struct {
	data      VextexDataType //顶点的值
	FisrtEdge *EdgeNode      //该顶点指向的第一条边
}

//Graph 图
type Graph struct {
	VNum, ENum int          //顶点数目,边数目
	G          []VextexNode //邻接表
}

//CreateGraph 创建邻接表
func CreateGraph(VNum int) (graph Graph) {
	graph.VNum = VNum
	graph.G = make([]VextexNode, VNum)
	for i := 0; i < VNum; i++ {
		graph.G[i] = VextexNode{}
	}
	return graph
}

//AddEdge 添加边
func (graph Graph) AddEdge(s, t VextexType, weight EdgeType) {
	edge := &EdgeNode{V: t, Weight: weight}

	//添加边到头部
	edge.Next = graph.G[s].FisrtEdge
	graph.G[s].FisrtEdge = edge
}

//BuildGraph 通过读取文件建图
//文件格式要求:
//顶点个数 边数
//顶点v1 顶点V2 边的权重
//...
func BuildGraph(path string) (graph Graph) {
	f, err := os.Open(path)
	if err != nil {
		panic(err)
	}
	buf := bufio.NewReader(f)

	i := 0
	//边的数目
	for {
		line, err := buf.ReadString('\n')
		if err != nil {
			if err == io.EOF {
				return graph
			}
			panic(err)
		}
		line = strings.TrimSpace(line)
		data := strings.Split(line, " ")
		if i == 0 {
			n, err := strconv.Atoi(data[0])
			if err != nil {
				panic(err)
			}
			graph = CreateGraph(n)

			graph.ENum, err = strconv.Atoi(data[1])
			if err != nil {
				panic(err)
			}
		} else if i <= graph.ENum {
			s, err := strconv.Atoi(data[0])
			if err != nil {
				panic(err)
			}
			t, err := strconv.Atoi(data[1])
			if err != nil {
				panic(err)
			}
			weight, err := strconv.Atoi(data[2])
			if err != nil {
				panic(err)
			}
			graph.AddEdge(VextexType(s), VextexType(t), EdgeType(weight))
		}
		i++
	}

}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!