-
-
图用邻接表存储
-
测试
package mm
import "testing"
func TestAdjacencyLists_Adjacent(t *testing.T) {
l := NewAdjacencyLists(10)
l.InsertEdge(&Vertex{index: 0},&Vertex{index: 1})
l.InsertEdge(&Vertex{index: 0},&Vertex{index: 2})
l.InsertEdge(&Vertex{index: 1},&Vertex{index: 3})
l.InsertEdge(&Vertex{index: 1},&Vertex{index: 4})
l.InsertEdge(&Vertex{index: 2},&Vertex{index: 5})
l.InsertEdge(&Vertex{index: 2},&Vertex{index: 6})
l.InsertEdge(&Vertex{index: 3},&Vertex{index: 7})
l.InsertEdge(&Vertex{index: 4},&Vertex{index: 7})
l.InsertEdge(&Vertex{index: 5},&Vertex{index: 7})
l.InsertEdge(&Vertex{index: 6},&Vertex{index: 7})
l.InsertEdge(&Vertex{index: 6},&Vertex{index: 7})
l.InsertEdge(&Vertex{index: 0},&Vertex{index: 8})
l.InsertEdge(&Vertex{index: 0},&Vertex{index: 9})
l.Print()
t.Log(l.dfs())
t.Log(l.dfsRecursion())
t.Log(l.bfs())
}
- 深度优先算法递归实现
- 从顶点v开始，依次对顶点v的邻接链表顶点做深度优先搜索
- [0 1 3 7 4 5 2 6 8 9]
func dfsRecursion(l *AdjacencyLists) []int {
var fRecv func(v *Vertex)
visited := make([]bool, len(l.vertexes))
var res []int
fRecv = func(v *Vertex) {
if !visited[v.index] {
res = append(res, v.index)
visited[v.index] = true
}
for v.next != nil {
if !visited[v.next.index] {
fRecv(l.vertexes[v.next.index])
}
v = v.next
}
}
fRecv(l.vertexes[0])
return res
}
- 深度优先算法非递归实现
- 1.随便把一个顶点推入栈中
- 2.从栈中弹出一个顶点或链表v，如果未访问，加入访问数组
- 3.从顶点v当前的邻接表（头结点不一定是v）依次选取一个未访问的顶点w1、w2，
对w1进行深度优先搜索，如果w2存在，先把w2入栈，再把以w1为头结点的顶点入栈。 - 4.当最终搜索到一个顶点u，且u的邻接表中的顶点全部被访问过，就从栈中取出一个链表继续上述步骤2，直到栈为空，搜索结束
- [0 1 3 7 4 5 2 6 8 9]
func dfs(l *AdjacencyLists) []int {
var result []int
var fStack func(index int)
s := stack()
fStack = func(index int) {
visited := make([]bool, len(l.vertexes))
s.stackPush(l.vertexes[index])
for !s.stackEmpty() {
temp, _ := s.stackPop()
if !visited[temp.index] {
result = append(result, temp.index)
visited[temp.index] = true
}
temp1 := temp.next
for temp1 != nil {
if !visited[temp1.index] {
if temp1.next != nil {
s.stackPush(temp1.next) // 链表先入栈
}
s.stackPush(l.vertexes[temp1.index]) // 头结点入栈
break
}
temp1 = temp1.next
}
}
}
fStack(0)
return result
}
- 栈
type stackArr struct {
stackArr []*Vertex
}
func stack() *stackArr {
return &stackArr{}
}
func (l *stackArr) stackEmpty() bool {
return len(l.stackArr) == 0
}
func (l *stackArr) stackClear() {
l.stackArr = nil
}
func (l *stackArr) stackPush(v *Vertex) {
l.stackArr = append(l.stackArr, v)
}
func (l *stackArr) stackPop() (v *Vertex, ok bool) {
if l.stackEmpty() {
return
}
v = l.stackArr[len(l.stackArr)-1]
l.stackArr = l.stackArr[:len(l.stackArr)-1]
return v, true
}
- 广度优先算法
- 顶点v入队列
- 2.从队列弹出一个顶点w。依次访问w的所有节点wt，如果wt未访问，将其加入访问数组result，将其头结点链加入队列
- 3.重复2
- [0 1 2 8 9 3 4 5 6 7]
func bfs(l *AdjacencyLists) []int {
var result []int
var fQueue func(index int)
q := queue()
fQueue = func(index int) {
visited := make([]bool, len(l.vertexes))
q.addq(l.vertexes[index])
for !q.emptyq() {
temp, _ := q.deleteq()
for temp != nil {
if !visited[temp.index] {
result = append(result, temp.index)
visited[temp.index] = true
q.addq(l.vertexes[temp.index])
}
temp = temp.next
}
}
}
fQueue(0)
return result
}
- 队列
type queueArr struct {
queueArr []*Vertex
}
func queue() *queueArr {
return &queueArr{}
}
func (l *queueArr) deleteq() (v *Vertex, ok bool) {
if l.emptyq() {
return
}
v = l.queueArr[0]
l.queueArr = l.queueArr[1:]
return v, true
}
func (l *queueArr) addq(v *Vertex) {
l.queueArr = append(l.queueArr, v)
}
func (l *queueArr) emptyq() bool {
return len(l.queueArr) == 0
}
func (l *queueArr) clearq() {
l.queueArr = nil
}
- 图的基本操作
package mm
import "fmt"
type Vertex struct {
index int
next *Vertex
}
type AdjacencyLists struct {
vertexes []*Vertex
}
func NewAdjacencyLists(size int) *AdjacencyLists {
return &AdjacencyLists{
vertexes: make([]*Vertex, size),
}
}
// InsertVertex 向图中插入没有关联边的新顶点v
func (l *AdjacencyLists) InsertVertex(v *Vertex) {
l.vertexes[v.index] = v
}
// DeleteVertex 删除图中的顶点v及其关联的所有边
func (l *AdjacencyLists) DeleteVertex(v *Vertex) {
list := l.vertexes[v.index]
for list.next != nil {
temp := l.vertexes[list.next.index]
for temp.next != nil {
if temp.next.index == v.index {
temp.next = temp.next.next
} else {
temp = temp.next
}
}
list = list.next
}
l.vertexes[v.index] = nil
}
// DeleteEdge 删除图中边(v1,v2),顶点v1，v2不删除
func (l *AdjacencyLists) DeleteEdge(v1, v2 *Vertex) {
temp1 := l.vertexes[v1.index]
for temp1.next != nil {
if temp1.next.index == v2.index {
temp1.next = temp1.next.next
} else {
temp1 = temp1.next
}
}
temp2 := l.vertexes[v2.index]
for temp2.next != nil {
if temp2.next.index == v1.index {
temp2.next = temp2.next.next
} else {
temp2 = temp2.next
}
}
}
func (l *AdjacencyLists) IsEmpty() bool {
result := true
for _, v := range l.vertexes {
if v != nil {
result = false
break
}
}
return result
}
// Adjacent 顶点v的所有邻接节点
func (l *AdjacencyLists) Adjacent(v *Vertex) []*Vertex {
return l.vertexes
}
func (l *AdjacencyLists) Print() {
fmt.Println("--------------------------------")
for k, v := range l.vertexes {
fmt.Printf("%d: ", k)
for v != nil {
if v.next != nil {
fmt.Printf("%d=>", v.index)
} else {
fmt.Printf("%d", v.index)
}
v = v.next
}
fmt.Println()
}
fmt.Println("--------------------------------")
}
// InsertEdge 向图的顶点v1和v2之间插入一条边
func (l *AdjacencyLists) InsertEdge(v1, v2 *Vertex) {
temp1 := l.vertexes[v1.index]
if temp1 == nil {
l.vertexes[v1.index] = &Vertex{index: v1.index}
temp1 = l.vertexes[v1.index]
}
for temp1.next != nil {
if temp1.next.index == v2.index { // 不添加重复节点
return
}
temp1 = temp1.next
}
temp1.next = v2
temp2 := l.vertexes[v2.index]
if temp2 == nil {
l.vertexes[v2.index] = &Vertex{index: v2.index}
temp2 = l.vertexes[v2.index]
}
for temp2.next != nil {
if temp2.next.index == v1.index { // 不添加重复节点
return
}
temp2 = temp2.next
}
temp2.next = v1
}
概念
-
图G由2个集合组成：一个顶点（vertex）构成的有穷非空集合和一个由边（edge）构成的有穷允空集合。V(G)和E(G)分别表示图G的顶点集和边集，有时也用G=(V,E)表示图。
-
无向图：是表示边的两个顶点之间没有次序关系的图。
-
无向图顶点对(v0,v1)和(v1,v0)表示同一条边。
-
有向图：表示边的顶点对有方向的图。
-
有向图顶点对<v0,v1>表示以顶点 v0 为尾(tail)，而以顶点 v1 为头(head) 的边。
-
完全图：是具有最多边数的图。有向图边数为 n*(n-1)；无向图边为 n*(n-1)/2 -
图的限制：
- 图中不能出现从顶点i到自身的边。
- 同一条边在图中不能出现两次或两次以上，不满足这个限制的图称为多重图(multigraph)
-
如果 (v0,v1) 是无向图的一条边，则称顶点v0和v1是相邻的,并称边(v0,v1)与顶点v0和v1关联
-
如果 <v0,v1> 是有向图的一条边，则称顶点 v0 邻接到顶点 v1，而 v1 邻接于 v0，并称边 <v0,v1>与顶点v0和v1关联。 -
路径（path）从顶点vp到顶点vq的一条路径是一个顶点序列vp，vi，…,Vq。路径的长度是路径上边的条数 -
一条
简单路径是指路径上除了起点和终点可能相同外，其余顶点都互不相同的路径 -
图上的
回路又称为环路是一条简单路径，且其起点和终点相同。 -
在无向图G中，如果从顶点v0到v1存在一条路径，则称
顶点v0和v1是连通的(connected)。如果无向图G中每对顶点vi和vj，都存在一条从vi到vj的路径，则称无向图G是连通的。 -
无向图的连通分支，简称分支，是无向图中的极大连通子图。
-
在有向图G中，如果每对不同的顶点vi和vi，都存在 vi到vj 和 vj到vi 的有向路径，则称有向图G是强连通的。
-
顶点的度（degree）是关联于该顶点的边的条数。在有向图中，把顶点v的入度（in-degree）定义为以v为头（箭头指向v）的边的条数，而其出度（out-degree）定义以v为尾的边的条数。
-
无向图graph，有向图digraph
-
通常，把边很少的图称为稀疏图
-
图的存储：邻接矩阵（adjacency matrices），邻接表（adjacency lists）和邻接多重表（adjacency multilists）
-
邻接表：对于v0为头结点的链表，存储的是
邻接于v0的节点，即v0的出度节点。如<v0,v1>,<v0,v2>中的v1,v2 -
逆邻接表：对于v0为头结点的链表，存储的是
邻接到v0的节点，即v0的入度节点。如<v1,v0>,<v2,v0>中的v1,v2