4.1 无向图

文章目录
  1. 1. 术语表
  2. 2. 表示无向图的数据类型
  3. 3. 深度优先搜索
  4. 4. 寻找路径
  5. 5. 广度优先搜索
  6. 6. 连通分量

图: 由一组顶点和一组能够将两个顶点相连的边组成的

术语表

当两个顶点通过一条边相连时,我们称这两个顶点是相邻的 并称该连接依附于这两个顶点。某个顶点的度数即为依附于他的边的总数。

路径: 在图中,路径是由边顺序连接的一系列顶点。路径或环的长度为其中包含的边数

连通: 当两个顶点之间存在一条连接双方的路径时,我们称一个顶点和另一个顶点是连通的。

连通图: 如果顶点是物理存在的对象,如绳节,边是绳子, 任意顶点提起,连通图是一个整体。

树: 无环连通图

生成树: 连通图的生成树是它的一副子图,包含图中所有顶点,且是一颗树

V个顶点图的树的条件:

  1. G有V-1条边且不含有环
  2. G有V-1条边,且是连通
  3. G是连通的,但删除任何一条边,会使它不再连通
  4. G是无环图,但添加任何一条边,都会产生一个环
  5. G中任意一对顶点之间仅存在一条简单路径

密度: 连接顶点对占所有可能别连接的顶点对的比例。 (稀疏图、稠密图)

二分图: 每条边连接的两个顶点都分别属于不同部分,

二分图

表示无向图的数据类型

接口 说明
V()->Int 顶点数
E()->Int 边数
addEdge(v: Int, w: Int) 向图中添加一个边v-w
adj(v: Int)->[Int] 和v相邻的所有顶点

图的表示方法:

  1. 邻接矩阵 :V*V的矩阵,当顶点V和W之间有相邻的边时,V行和W列的元素值未true
  2. 邻接表数组

下图是邻接表内存图:

邻接表内存图

图的定义:

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Graph {
var vertex: Int
var adj: [[Int]]
var edge: Int = 0

init(vertex: Int) {
self.vertex = vertex
adj = [[Int]](repeating: [Int](), count: vertex)
}

convenience init?(inStream: ReadFile) {
let v = inStream.readInt()
if v != nil {
self.init(vertex: v!)
} else {
return nil
}
let edge = inStream.readInt()
if edge != nil {
for _ in 0..<edge! {
let v = inStream.readInt()
let w = inStream.readInt()
self.addEdge(v!, w!)
}
} else {
return nil
}
}

func addEdge(_ v: Int, _ w: Int) {
self.adj[v].append(w)
self.adj[w].append(v)
self.edge += 1
}

func V() -> Int {
return vertex
}

func E() -> Int {
return edge
}
func toString() -> String {
var result: String =
"""
\(V) vertixes \(E) edges \n
"""
for i in 0..<vertex {
result += "\(i) :"
for w in adj[i] {
result += "\(w) "
}
result +=
"""
\n
"""
}
return result
}
}

深度优先搜索

图处理的一般策略:从一个顶点移动到另一个顶点

深度优先搜索轨迹图

  1. 因为顶点2是0的邻接表的第一个元素,且没有标记过,dfs()递归调用自己来标记并访问顶点2
  2. 现在,顶点0是2的邻接表的第一个元素,且已经被标记了,因此,dfs跳过了他,接下来,顶点1是2的邻接表的第二个元素,且没有标记过,dfs递归调用自己,来标记并访问顶点1
  3. 对顶点1的访问和前面有所不同:因为它的邻接表中的所有顶点(0,2)都已经被标记过了,因此,不需要再递归,方法从dfs(1)返回,下一条被检查的边是2-3,因此dfs递归调用自己,来标记并访问顶点3
  4. 顶点5是3的邻接表的第一个元素且没有被标记,因此dfs递归调用自己来标记并访问顶点5
  5. 顶点5邻接表中的所有顶点(3,0)都已经被标记过了,因此不需要再递归
  6. 顶点4是3的邻接表的下一个元素,且没有被标记过,因此dfs递归调用自己,来标记并访问顶点4,这是最后一个需要被标记的顶点

深度优先能解决的问题: 单点路径,给定一个一副图和一个起点,回答“从s到给定目的顶点v是否存在一条路径?如果有,找出这条路径”等类似问题。

下面是深度优先搜索的代码:

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
class DepthFirstSearch {
private var _marked: [Bool] //描述标记过的顶点
private var _count: Int = 0 //描述标记过的顶点个数

init(G: Graph, s: Int ) {
_marked = [Bool](repeating: false, count: G.V() )
dfs(G, s)
}

func dfs(_ G: Graph, _ v: Int) {
_marked[v] = true
_count += 1
for w in G.adj(v) {
if _marked[w] == false {
dfs(G, w)
}
}
}

func marked(_ v: Int) -> Bool {
return _marked[v]
}

func count() -> Int {
return _count
}
}

寻找路径

在由v-w第一次访问任意w时,将edgeTo[w]设为v来记住这条路径 。所以edgeTo的理解如下:

  1. 索引是当前节点,终止节点
  2. 值是上一个节点 ,起始节点

edgeTo巧妙的用途-路径树

树的特定: 以起点为根节点的树。

下面是实现代码:

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
class DepthFirstPaths {
var _marked: [Bool] // 标记这个顶点调用过dfs了吗?
var _edgeTo: [Int] //从起点到一个顶点的已知路径上的最后一个顶点
let _s: Int // 起点
init(G: Graph, s: Int) {
let count = G.V()
self._marked = [Bool](repeating: false, count: count)
self._edgeTo = [Int](repeating: 0, count: count)
self._s = s
dfs(G, v: s)
}

func dfs(_ G: Graph, v: Int) {
_marked[v] = true
for w in G.adj(v) {
if self._marked[w] == false {
self._edgeTo[w] = v
dfs(G, v: w)
}
}
}

func hasPathTo(_ v: Int) -> Bool {
return self._marked[v]
}

func pathTo(_ v: Int) -> [Int]? {
if !hasPathTo(v) {
return nil
}
var path = [Int]()
var x = v
repeat {
path.insert(x, at: 0)
x = self._edgeTo[x]
} while x != self._s

path.insert(self._s, at: 0)
return path
}
}

命题A(续):使用深度优先搜索得到从给定起点到任何标记顶点的路径所需的时间与路径的长度成正比。

广度优先搜索

广度优先搜索能解决单点最短路径问题。

要找从s到v的最短路径,从s开始,在所有由一条边就可以到达的点多中寻找v,如果找不到,我们就继续在于s距离两条边的所有顶点中寻找v,如此一直继续。

思路,将起点假如队列中,然后重复下面的步骤:

  1. 取出队列中的下一个顶点v,并标记它
  2. 将与v相邻的所有未被标记的顶点加入队列中

bfs的轨迹图

轨迹说明:

  1. 从队列中删除顶点0, 并标记相邻的顶点2,1,5,并加入队列中。并把他们的edgeTo[]设为0
  2. 从队列中删去顶点2,并检查它的相邻顶点0,1,发现两者都已经标记,将相邻的顶点3,4加入队列,标记他们,并将edgeTo[]设为2
  3. 从队列中删去顶点1,并检查他的相邻顶点0,2,发现他们都已经被标记了
  4. 从队列中删去顶点5,并检查他的相邻顶点3,0,发现他们都已经被标记了
  5. 从队列中删去顶点3,并检查他的相邻顶点5,4,2,发现他们都已经被标记了
  6. 从队列中删去顶点4,并检查他的相邻顶点3,2,发现他们都已经被标记了

下面是广度优先级查找最短路径的代码:

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
45
46
47
class BreadthFirstPaths {
var _marked: [Bool] // 标记这个顶点调用过dfs了吗?
var _edgeTo: [Int] //从起点到一个顶点的已知路径上的最后一个顶点
let _s: Int // 起点
init(G: Graph, s: Int) {
let count = G.V()
self._marked = [Bool](repeating: false, count: count)
self._edgeTo = [Int](repeating: 0, count: count)
self._s = s
bfs(G,s)
}

func bfs(_ G: Graph, _ s: Int) {
var queue = [Int]()
_marked[s] = true
queue.append(s)
while !queue.isEmpty {
let v = queue.removeFirst() //取出一个顶点处理
for w in G.adj(v) {
if !self._marked[w] { //邻接顶点没有被标记过
self._marked[w] = true
self._edgeTo[w] = v
queue.append(w)
}
}
}
}

func hasPathTo(_ v: Int) -> Bool {
return self._marked[v]
}

func pathTo(_ v: Int) -> [Int]? {
if !hasPathTo(v) {
return nil
}
var path = [Int]()
var x = v
repeat {
path.insert(x, at: 0)
x = self._edgeTo[x]
} while x != self._s

path.insert(self._s, at: 0)
return path
}
}

命题B: 从s可达的任意顶点v,广度优先搜索都能找到一条从s到v的最短路径。

深度和广度的相同点:

  1. 都是取出下一个顶点,并标记它
  2. 将v的所有相邻而又未被标记的顶点加入数据结构

不同之处,在于从数据结构中读取下一个顶点的规则:

  1. 对于广度优先级,是最早加入的节点(队列)
  2. 深度优先级搜索,最晚加入的节点(栈)

连通分量

id数组的理解:

  1. 索引,顶点
  2. 值: 所在的连通分量标识
  3. 连通分量标识的范围为0..count-1
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
class CC {
var _marked: [Bool]
var _id: [Int]
var _count = 0
init(G: Graph) {
let vertexCount = G.V()
self._marked = [Bool](repeating: false, count: vertexCount)
self._id = [Int](repeating: 0, count: vertexCount)
for s in 0..<vertexCount {
if !_marked[s] {
dfs(G, s)
self._count += 1
}
}
}

func dfs(_ G: Graph, _ v: Int) {
self._marked[v] = true
self._id[v] = self._count
for w in G.adj(v) {
if !self._marked[w] {
dfs(G, w)
}
}
}

func connected(_ v: Int, _ w: Int) -> Bool { //判断两个顶点是否连通
return self._id[v] == self._id[w]
}

func id(_ v: Int) -> Int { //返回顶点属于的连通分量
return self._id[v]
}

func count() -> Int { //返回连通分量的个数
return self._count
}
}

注意:图是否有环还没有理解

连通分量轨迹图

算法4 官网地址