图算法

图(Graph)是由若干给定的顶点(vertex)(也可以成为节点(node)),及连接两顶点的边(edges)所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物,连接两顶点的边则用于表示两个事物间具有这种关系

图分为有向图、无向图、有权重图、无权重图

对于图 G = (V, E),V 为顶点集,E 为边集

稀疏图 - 边数量 E 远远小于 V^2 - 适合用邻接链表(Adjacency List)来表示

稠密图 - 边数量 E 接近于 V^2 -    适合用邻接矩阵(Adjacency Matrix)来表示


邻接矩阵(Adjacency Matrix)

邻接矩阵 adj[][] 在图里是一个二维数组 V x V,V 是图里的顶点数。

对于无向图,adj[i][j] = 1 表示 顶点i 到 顶点j 有边,并且总是对称的,即 adj[j][i] = 1

对于有向图,adj[i][j] = w 表示顶点i 到 顶点j 有边,并且权重为 w

邻接矩阵能快速判断一条边是否是图中的一条边,但是比较耗空间Θ(V^2),图规模较小时优先选择,对于无向图每个记录项只需要1位(0|1)



邻接链表(Adjacency List)

即数组里包含链表,数组的大小即为顶点数,arr[i]是一个链表,代表第 i 个顶点周围邻近的顶点

当然也可以用来表示有权重的图,通常需要一个权重函数来查询



广度优先搜索(Breadth First Search)(BFS)

也叫宽度优先搜索,或横向优先搜索,是一种图形搜索算法,简单的说就是沿着图的宽度遍历所有节点,注意,图不像树,需要注意回路


各顶点被访问的顺序

1.顶点 1
2.顶点 2 3 4
3.顶点 5 6
4.顶点 7 8
5.顶点 9 10
6.顶点 11 12

算法实现步骤

1.首先将根节点放入列表
2.从列表中取出一个节点
3.将所有所有与该节点直接相连的,未访问过的节点加入到链表中
4.如果链表为空,代表全部搜索过了,退出
5.重复2

模拟,需要一个先进后出队列L,需要一个标记访问的数组V

1. L={1]   V={1}
2. L={}    V={1}       取出顶点1
3. L={2 3 4} V={1}     将顶点1未访问过的,直接子节点加入到队列
4. L={3 4}    V={1 2}  取出顶点2
5. L={3 4 5 6} V={1 2} ....
6. L={4 5 6} V={1 2 3}
7. L={5 6}    V={1 2 3 4}
8. L={5 6 7 8} V={1 2 3 4}
9. L={6 7 8} V={1 2 3 4 5}
10 L={6 7 8 9 10} V={1 2 3 4 5}
11 L={7 8 9 10} V={1 2 3 4 5 6}
12 L={8 9 10} V={1 2 3 4 5 6 7}
13 L={8 9 10 11 12} V={1 2 3 4 5 6 7}
14 L={9 10 11 12} V={1 2 3 4 5 6 7 8}
15 L={10 11 12} V={1 2 3 4 5 6 7 8 9}
16 L={11 12} V={1 2 3 4 5 6 7 8 9 10}
17 L={12} V={1 2 3 4 5 6 7 8 9 10 11}
18 L={} V={1 2 3 4 5 6 7 8 9 10 11 12}



深度优先搜索(Depth First Search)(DFS)

沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。属于盲目搜索


各顶点被访问的顺序

1.顶点 1
2.顶点 2
3.顶点 5
4.顶点 9
5.顶点 10
6.顶点 6
7.顶点 3
8.顶点 4
9.顶点 7
10.顶点 11
11.顶点 12
12.顶点 8

算法实现步骤

1.将根节点压入stack中
2.从栈中取出第一个节点校验
3.校验成功退出,否则将其中一个未访问过的子节点压入stack中
4.重复2
5.如果不存在未检测的直接子节点,出栈一个,重复步骤2
6.重复5
6.若stack为空,代表全部搜索过了

模拟,需要一个先进先出的栈 S,需要一个标记访问的数组V

1. S=1   V=1
2. S=1 2   V=1 2
3. S=1 2 5   V=1 2 5
4. S=1 2 5 9  V=1 2 5 9
4. S=1 2 5   V=1 2 5 9
5. S=1 2 5 10  V=1 2 5 9 10
6. S=1 2 5  V=1 2 5 9 10
7. S=1 2  V=1 2 5 9 10
8. S=1 2 6  V=1 2 5 9 10 6
9. S=1 2   V=1 2 5 9 10 6
10 S=1  V=1 2 5 9 10 6
11 S=1 3  V=1 2 5 9 10 6 3
12 S=1  V=1 2 5 9 10 6 3
13 S=1 4   V=1 2 5 9 10 6 3 4
14 S=1 4 7  V=1 2 5 9 10 6 3 4 7
15 S=1 4 7 11  V=1 2 5 9 10 6 3 4 7 11
16 S=1 4 7  V=1 2 5 9 10 6 3 4 7 11
17 S=1 4 7 12  V=1 2 5 9 10 6 3 4 7 11 12
18 S=1 4 7  V=1 2 5 9 10 6 3 4 7 11 12
19 S=1 4  V=1 2 5 9 10 6 3 4 7 11 12
20 S=1 4 8  V=1 2 5 9 10 6 3 4 7 11 12 8
20 S=1 4  V=1 2 5 9 10 6 3 4 7 11 12 8
20 S=1  V=1 2 5 9 10 6 3 4 7 11 12 8
20 S=   V=1 2 5 9 10 6 3 4 7 11 12 8



上一篇: 平面最近点对
下一篇: 并查集-校验图是否有回路
作者邮箱: 203328517@qq.com