数据结构：图

Posted on In

这篇文文章主要介绍一种比较复杂的数据结构–图。主要内容：

  • 图的概念及术语
  • 图的结构
  • 图的遍历
    • 深度优先遍历
    • 广度优先遍历

图的概念及术语

定义

定义：由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V, E)。其中 G 表示图，V 是图中顶点的集合，E 是图 G 中边的集合。

一些术语

图的术语非常多，其它的术语当用到的时候再去了解。这里介绍几个比较常见的术语：

顶点：表示图中的一个结点。

边：顶点和顶点之间的连线。若连线无方向则为无向边，反之则为有向边，也称为弧。

权：边有与之相关的数值，这个数值称为权。

相邻顶点：由一条边连接在一起的顶点。

度：相邻顶点的数量。指向其它顶点的数量称为出度, 其它顶点指向自己的数量称为入度。

无向图：图中任意两个顶点之间的边都是无向边。

有向图：图中任意两个顶点之间的边都是有向边。

无权图：图中的边是没有任何意义，无权重。

带权图：图中的边有一定的权重。

连通图：图中任意两个顶点都是连通的。

结构

散列表

散列表的具体概念这里就不多介绍了，大部分的语言中都提供了散列表的实现。在 Swift 中，散列表的实现就是字典。

我们可以用散列表来实现一个图结构。

邻接矩阵

两个数组来表示图结构。一个一维数组存储图中顶点信息，一个二维数组（邻接矩阵）存出图中的边或弧的信息。

图中展示了三种图的邻接矩阵表示方式。其中：

数字为 0 或者 ∞ 的代表两个顶点之间没有连线，其它数字都代表有连线。在有向图中，数字 1 代表纵向对应顶点指向横向对应顶点。在带权图中，数字的数值大小则代表这条边的权。

图的定义：

1
2
3
4
5
6
7
8
class Graph {
    var vertexs: [Vertex] = []
    
    var edges: [[Int]] = []
    
    // 这个属性表示带权图中无限大
    let Not_Link = INT_MAX
}

邻接表

数组和链表结合来表示图结构。一个一维数组存储图中顶点信息，链表则用来表示与某个顶点相邻的顶点。

图中展示了三种图的邻接矩阵表示方式。其中：

链表结点的 index 指向数组中与自己相邻顶点的下标，next 指向下一个与自己相邻的顶点，最后一个顶点 next 置为 nil。在带权图中，对链表结点的定义扩充了一个 Weight 控件，表示这条边的权重。

图的定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 图顶点
class Vertex {
    var data: String?
    
    var link: LinkNode?
}

// 链表的结点
class LinkNode {
    var data: Int?
    
    var next: LinkNode?
    
    // 带权图使用此属性
    var weight: Float?
}

// 图
class Graph {
    var vertexs: [Vertex] = []
    
    var adjList: [Int: LinkNode] = [:]
}

边集数组

边集数组是由两个一维数组构成。一个是存储顶点信息的，另一个存储边的信息。边数组中每个数据元素都由 begin(起点下标)，end(终点下标)，weight(权) 组成。

边集数组因为其存储形式，比较适合存储有向图及带权图。若存储无向图，则对同一条边需要两个数据元素来存储，对空间会造成比较大的浪费。

图的定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Edge {
    var begin: Int
    var end: Int
    
    var weight: Float?
    
    init(begin: Int, end: Int) {
        self.begin = begin
        self.end = end
    }
}

class G {
    var vertexs: [Vertex] = []
    
    var edges: [Edge]?
}

遍历

准备工作

这里我们是利用前面散列表来表示图。

1
2
3
4
5
6
7
var graph = [String: [String]]()
graph["A"] = ["B", "C"]
graph["B"] = ["D"]
graph["C"] = ["D", "E"]
graph["D"] = ["G"]
graph["E"] = ["F"]
graph["F"] = ["G"]

上面的代码创建了一个下图中的图结构。

广度优先遍历

广度优先遍历类似于树的层序遍历。

从 A 开始，找到所有自己一步能到达的顶点（B，C）加入队列，查找是否是自己需要的（G），如果不是，再将这些顶点（B，C）一步能到达的顶点（D，E），加入到队列中。如果找到，直接返回结果，否则就这样一层一层的找下去，直至队列为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// 存储已访问的顶点
var visited: [String] = []

func visit(_ v: String) {
    print(v)
}

// 广度优先遍历
func breadthFirstSearch(_ value: String?) {
    // 利用数组表示队列
    var queue = [String]()
    
    if let vertex = value {
        queue.insert(vertex, at: 0)
    }
    
    while queue.count != 0 {
        let current = queue.popLast()!
        
        if !visited.contains(current) {
            visit(current)
            visited.append(current)
        }
        
        guard let neighbors = graph[current] else {
            continue
        }
        
        for data in neighbors {
            if !visited.contains(data) {
                queue.insert(data, at: 0)
            }
        }
    }
}

----输出结果：----
A
B
C
D
E
G
F

深度优先遍历

  1. 从某个顶点（A）出发，访问顶点并标记为已访问。
  2. 访问 A 的其中一个邻接点（假设为 B），如果没有访问过，访问该顶点并标记为已访问。
  3. 然后再访问该顶点（B）的邻接点（D），重复上述步骤。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 深度优先遍历
func depthFirstSearch(_ value: String?) {
    guard let vertex = value else {
        return
    }
    
    visit(vertex)
    visited.append(vertex)
    
    guard let neighbors = graph[vertex] else {
        return
    }
    
    for data in neighbors {
        if !visited.contains(data) {
            depthFirstSearch(data)
        }
    }
}

----输出结果：----
A
B
D
G
C
E
F

结论

Depth_First_Search的实现用递归，Breadth_First_Search的实现用循环（配合队列）。