继续我们的总结回顾，图的算法难度较大，理论知识也非常多，倘若是考研党的话，应掌握图的基本概念及相关性质等。我本人翻看了下教材，考虑到文字信息实在太多，所以我打算以模拟大纲形式跟大家梳理下内容，细化知识点就需要大家自行掌握记忆了。
知识框架
图的基本概念
1图的定义
01 - 有向图
02 - 无向图
03 - 简单图
04 - 多重图
05 - 完全图
06 - 子图
07 - 连通、连通图和连通分量
08 - 强连通图、强连通分量
09 - 生成图、生成森林
10 - 顶点的图、入度和出度
11 - 边的权和网
12 - 稠密图、稀疏图
13 - 路径、路径长度和回路
14 - 简单路径、简单回路
15 - 距离
16 - 有向树
图的存储及基本操作
1邻接矩阵法
2邻接表法
3十字链表法
4邻接多重表
5图的基本操作
图的基本操作是独立于图的存储结构的。而对于不同的存储方式，操作算法的具体实现会有着不同的性能。在设计具体算法的实现时，应考虑采用何种存储方式的算法效率会更高。
//此程序用来建立图，输出图golang实现
package main
import (
"fmt"
"github.com/cheekybits/genny/generic" //导入第三方包定义一个新的类型
)
type Item generic.Type
//Node struct define
//结点定义
type Node struct {
Value Item
}
//Graph define
//图的定义
type Graph struct {
nodes []*Node //结点集合,是一个切片类型,为指向Node结构体的指针
edges map[Node][]*Node //邻接表表示的无向图
}
//
func (n *Node) String() string {
return fmt.Sprintf("%v", n.Value)
}
//AddNode method
//添加结点
//append用来将元素添加到切片末尾并返回结果,append(切片类型,其他的元素)
func (g *Graph) AddNode(n *Node) {
g.nodes = append(g.nodes, n)
}
//AddEdge method
//增加边信息
func (g *Graph) AddEdge(u, v *Node) {
//不存在图时,创建一个图
if g.edges == nil {
g.edges = make(map[Node][]*Node)
}
g.edges[*u] = append(g.edges[*u], v) //创建u->v的边
g.edges[*v] = append(g.edges[*v], u) //无向图,也存在v->u的边
}
//格式化输出图
func (g *Graph) String() {
str := ""
for _, node := range g.nodes {
str += node.String() + "->"
nexts := g.edges[*node]
for _, next := range nexts {
str += next.String() + " "
}
str += "\n"
}
fmt.Println(str)
}
func main() {
g := Graph{}
n1, n2, n3, n4, n5 := Node{Value:1}, Node{Value:2}, Node{Value:3}, Node{Value:4}, Node{Value:5}
g.AddNode(&n1)
g.AddNode(&n2)
g.AddNode(&n3)
g.AddNode(&n4)
g.AddNode(&n5)
g.AddEdge(&n1, &n2)
g.AddEdge(&n1, &n5)
g.AddEdge(&n2, &n3)
g.AddEdge(&n2, &n4)
g.AddEdge(&n2, &n5)
g.AddEdge(&n3, &n4)
g.AddEdge(&n4, &n5)
g.String()
}
图的遍历
1广度优先遍历(BFS)
01 - 算法原理
广度优先搜索（Breadth-First-Search BFS）类似于二叉树的层序遍历算法。基本思想是：首先请问起始顶点v，接着由v出发，依次访问v的各个未访问过的邻接顶点W1,W2,W3........Wi然后依次访问W1W2,W3........Wi的所有未被访问过的邻接顶点；再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直至图中所有顶点都被访问过为止。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为始点，重复上述过程，直至图中所有顶点都被访问到为止。
换句话说，广度优先搜索遍历图的过程是以v为起始点，由近至远依次访问和ν有路径相通且路径长度为1,2，...的顶点。广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况，因此它不是一个递归的算法。为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。
02 - 代码实现(golang)
//此程序是BFS算法的golang实现，所实现的图是上一节生成的图
package graph
import (
"github.com/cheekybits/genny/generic"
)
type Item generic.Type
//Node struct define
//结点定义
type Node struct {
Value Item
}
//Graph define
//图的定义
type Graph struct {
nodes []*Node //结点集合,是一个切片类型,为指向Node结构体的指针
edges map[Node][]*Node //邻接表表示的无向图
}
//结点定义
type NodeQueue struct {
nodes []Node
}
// 实现 BFS 遍历
func (g *Graph) BFS(f func(node *Node)) {
// 初始化队列
q := NewNodeQueue()
// 取图的第一个节点入队列
head := g.nodes[0]
q.Enqueue(*head)
// 标识节点是否已经被访问过
visited := make(map[*Node]bool)
visited[head] = true
// 遍历所有节点直到队列为空
for {
if q.IsEmpty() { //队列为空直接退出
break
}
node := q.Dequeue() //结点出队列
visited[node] = true //将该出队列结点标记为已访问true
nexts := g.edges[*node]
// 将所有未访问过的邻接节点入队列
for _, next := range nexts {
// 如果节点已被访问过
if visited[next] {
continue
}
q.Enqueue(*next)
visited[next] = true
}
// 对每个正在遍历的节点执行回调
if f != nil {
f(node)
}
}
}
// 生成节点队列
func NewNodeQueue() *NodeQueue {
q := NodeQueue{}
q.nodes = []Node{}
return &q
}
// 入队列
func (q *NodeQueue) Enqueue(n Node) {
q.nodes = append(q.nodes, n)
}
// 出队列
func (q *NodeQueue) Dequeue() *Node {
node := q.nodes[0]
q.nodes = q.nodes[1:]
return &node
}
// 判空
func (q *NodeQueue) IsEmpty() bool {
return len(q.nodes) == 0
} 不难看出，图的广度优先搜索的过程与二叉树的层序遍历是完全一致的，这也说明了图的广度优先搜索遍历算法是二叉树的层次遍历算法的扩展。
03 - 算法分析
2深度优先遍历(DFS)
01 - 算法原理
与广度优先搜索不同，深度优先搜索（Depth-First-Search,DFS）类似于树的先序遍历。如其名称中所暗含的意思一样，这种搜索算法所遵循的搜索策略是尽可能“深”地搜索一个图。
它的基本思想如下：首先访问图中某一起始顶点ν，然后由v出发，访问与v邻接且未被访问的任一顶点W1再访问与W1邻接且未被访问的任一顶点W2......重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。
02 - 算法实现
03 - 算法分析
有疑问加站长微信联系（非本文作者）
