数据结构：图和堆

记录图和堆有关的基础概念及相关算法

图

图的基本概念

数据结构-图

无向完全图中，n 个点则有 n(n-1)/2 条边。 有向完全图中，n 个点则有 n(n-1) 条边。

图的遍历

v2-ee45526da273f5c0fde827480913e29e_720w 
1
2
3
4
5
6
7
8
graph = {
        'a' : ['b', 'c'],
        'b' : ['a', 'c', 'd'],
        'c' : ['a','b', 'd','e'],
        'd' : ['b' , 'c', 'e', 'f'],
        'e' : ['c', 'd'],
        'f' : ['d']
        }

DFS

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
# 循环
def DFS(graph, s):
    stack = []
    stack.append(s)
    seen = set()
    seen.add(s)
    while len(stack) > 0:
        vertex = stack.pop()
        nodes  = graph[vertex]
        for node in nodes:
            if node not in seen:
                stack.append(node)
                seen.add(node)
        print(vertex)

DFS(graph, 'a')


# 递归
def DFS1(graph, s, queue=[]):
    queue.append(s)
    for i in graph[s]:
        if i not in queue:
            DFS1(graph, i, queue)
    return queue

DFS1(graph, 'a')

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
![v2-94d2ac8ba296ef97477b0001a996104a_720w](C:\Users\Tommy\3D Objects\v2-94d2ac8ba296ef97477b0001a996104a_720w.jpgdef BFS(graph, s):
    queue = []
    queue.append(s)
    seen = set()
    seen.add(s)
    while len(queue) > 0:
        vertex = queue.pop(0)
        nodes = graph[vertex]
        for node in nodes:
            if node not in seen:
                queue.append(node)
                seen.add(node)
        print(vertex)
        
BFS(graph, 'a')

有权图中最短路径问题

v2-94d2ac8ba296ef97477b0001a996104a_720w 
1
2
3
4
5
6
7
inf = float('inf')
matrix_distance = [[0,1,12,inf,inf,inf],
                   [inf,0,9,3,inf,inf],
                   [inf,inf,0,inf,5,inf],
                   [inf,inf,4,0,13,15],
                   [inf,inf,inf,inf,0,4],
                   [inf,inf,inf,inf,inf,0]]

Dijkstra算法

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

这里我们需要用到三个辅助数组：

  • dist[vi]，从 v0 到每个顶点 vi 的最短路径长度。
  • path[vi]，保存从 v0 到 vi 最短路径上的前一个顶点。
  • set[]，标记点是否被并入最短路径。

执行过程：

  • 初始化：
    • 选定源点 v0。
    • dist[vi]：若 v0 到 vi 之间若存在边，则为边上的权值，否则为∞。
    • path[vi]：若 v0 到 vi 之间存在边，则 path[vi]=v0，否则为-1。
    • set[v0]=TRUE，其余为 FALSE。
  • 执行：
    1. 从当前的 dist[]数组中选出最小值 dist[vu]。
    2. 将 set[vu] 置为TRUE。
    3. 检测所有 set[vi]==FALSE 的点。
    4. 比较 dist[vi] 和 dist[vu]+w 的大小，w 为 <vu,vi>的权值。
    5. 如果 dist[vu]+w<dist[vi]
    6. 更新 path[] 并将 vu 加入路径中
    7. 直到遍历完所有的顶点(n-1次)

结合图来理解就是：

1139760-20181025102953586-1615580793
1139760-20181025103032940-108172764 
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
def dijkstra(matrix_distance, source_node):
    inf = float('inf')
    # init the source node distance to others
    dis = matrix_distance[source_node]
    node_nums = len(dis)
    
    flag = [0 for i in range(node_nums)]
    flag[source_node] = 1
    
    for i in range(node_nums-1):
        min = inf
        #find the min node from the source node
        for j in range(node_nums):
            if flag[j] == 0 and dis[j] < min:
                min = dis[j]
                u = j
        flag[u] = 1
        #update the dis 
        for v in range(node_nums):
            if flag[v] == 0 and matrix_distance[u][v] < inf:
                if dis[v] > dis[u] + matrix_distance[u][v]:
                    dis[v] = dis[u] + matrix_distance[u][v]                    
    
    return dis

dijkstra(matrix_distance, 0)

Floyd算法

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

  • 初始化一个矩阵 \(A\)，\((A^{(-1)})[i][j]=G.edges[i][j]\)。
  • 迭代n轮：\((A^{(k)})=Min{(A^{(k-1)})[i][j], (A^{(k-1)})[i][k]+(A^{(k-1)})[k][j]}\)

\((A^{(k)})\)矩阵存储了前K个节点之间的最短路径，基于最短路径的性质，第K轮迭代的时候会求出第K个节点到其他K-1个节点的最短路径。

1139760-20181025134249477-410650124 
1
2
3
4
5
6
7
8
9
10
def Floyd(dis):
    # min (Dis(i,j) , Dis(i,k) + Dis(k,j) )
    nums_vertex = len(dis[0])
    for k in range(nums_vertex):
        for i in range(nums_vertex):
            for j in range(nums_vertex):
                if dis[i][j] > dis[i][k] + dis[k][j]:
                    dis[i][j] = dis[i][k] + dis[k][j]
    return dis
print(Floyd(matrix_distance))

最小生成树问题

假设以下情景，有一块木板，板上钉上了一些钉子，这些钉子可以由一些细绳连接起来。假设每个钉子可以通过一根或者多根细绳连接起来，那么一定存在这样的情况，即用最少的细绳把所有钉子连接起来。 更为实际的情景是这样的情况，在某地分布着N个村庄，现在需要在N个村庄之间修路，每个村庄之前的距离不同，问怎么修最短的路，将各个村庄连接起来。 以上这些问题都可以归纳为最小生成树问题，用正式的表述方法描述为：给定一个无方向的带权图G=(V, E)，最小生成树为集合T, T是以最小代价连接V中所有顶点所用边E的最小集合。 集合T中的边能够形成一颗树，这是因为每个节点（除了根节点）都能向上找到它的一个父节点。

解决最小生成树问题已经有前人开道，Prime算法和Kruskal算法，分别从点和边下手解决了该问题。

Prim算法

Prim算法是一种产生最小生成树的算法。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（英语：Robert C. Prim）独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。

Prim算法从任意一个顶点开始，每次选择一个与当前顶点集最近的一个顶点，并将两顶点之间的边加入到树中。Prim算法在找当前最近顶点时使用到了贪婪算法。适合于边稠密的图。

算法描述

  1. 在一个加权连通图中，顶点集合V，边集合为E
  2. 任意选出一个点作为初始顶点,标记为visit,计算所有与之相连接的点的距离，选择距离最短的，标记visit.
  3. 重复以下操作，直到所有点都被标记为visit： 在剩下的点钟，计算与已标记visit点距离最小的点，标记visit,证明加入了最小生成树。
1139760-20181009152355508-535468775

代码

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
from collections import defaultdict
from heapq import *
    
def Prim(vertexs, edges, start_node):
    adjacent_vertex = defaultdict(list)
    for v1, v2, length in edges:
        adjacent_vertex[v1].append((length, v1, v2))
        adjacent_vertex[v2].append((length, v2, v1))
        
    mst = []
    closed = set(start_node)
    
    adjacent_vertexs_edges = adjacent_vertex[start_node]
    heapify(adjacent_vertexs_edges)

    while adjacent_vertexs_edges:
        w, v1, v2 = heappop(adjacent_vertexs_edges)
        if v2 not in closed:
            closed.add(v2)
            mst.append((v1, v2, w))
            
            for next_vertex in adjacent_vertex[v2]:
                if next_vertex[2] not in closed:
                    heappush(adjacent_vertexs_edges, next_vertex)
                    
    return mst
    
    
vertexs = list("ABCDEFG")
edges = [ ("A", "B", 7), ("A", "D", 5),
          ("B", "C", 8), ("B", "D", 9), 
          ("B", "E", 7), ("C", "E", 5),
          ("D", "E", 15), ("D", "F", 6),
          ("E", "F", 8), ("E", "G", 9),
          ("F", "G", 11)]

print('prim:', Prim(vertexs, edges, 'A'))

Kruskal算法

Kruskal是另一个计算最小生成树的算法，其算法原理如下。首先，将每个顶点放入其自身的数据集合中。然后，按照权值的升序来选择边。当选择每条边时，判断定义边的顶点是否在不同的数据集中。如果是，将此边插入最小生成树的集合中，同时，将集合中包含每个顶点的联合体取出，如果不是，就移动到下一条边。重复这个过程直到所有的边都探查过。适合边少点多的图。

1139760-20181009152448537-1374278496

代码

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
node = dict()  # 保存节点
rank = dict()

# 创建集合
def make_set(point):
    node[point] = point
    rank[point] = 0
    
# 标记已经处理了的节点
def find(point):
    if node[point] != point:
        node[point] = find(node[point])
    return node[point]

# 合并两个节点
def merge(point1, point2):
    root1 = find(point1)
    root2 = find(point2)
    if root1 != root2:
        if rank[root1] > rank[root2]:
            node[root2] = root1
        else:
            node[root1] = root2
            if rank[root1] == rank[root2]: 
                rank[root2] += 1
            
# 主函数    
def Kruskal(graph):
    for vertice in graph['vertices']:
        make_set(vertice)
    
    mst = set()
    
    edges = list(graph['edges'])
    edges.sort()
    for edge in edges:
        weight, v1, v2 = edge
        if find(v1) != find(v2):
            merge(v1 , v2)
            mst.add(edge)
    return mst

graph = {
    'vertices': ['A', 'B', 'C', 'D'],
    'edges': set([
        (1, 'A', 'B'),
        (5, 'A', 'C'),
        (3, 'A', 'D'),
        (4, 'B', 'C'),
        (2, 'B', 'D'),
        (1, 'C', 'D'),
        ])
    }

print(Kruskal(graph))

一张图看懂数据结构——图

20200508105556140

参考连接

Python实现图的经典DFS、BFS、Dijkstra、Floyd、Prim、Kruskal算法 关于最小生成树算法，推荐这个博客，讲的很清楚！ 作者：卡巴拉的树 链接：https://www.jianshu.com/p/efcd21494dff 来源：简书 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 一张图看懂数据结构 —— k图

堆

最大堆（大根堆）的定义：

  • 最大堆中的最大元素值出现在根结点（堆顶）
  • 堆中每个父节点的元素值都大于等于其孩子结点

最小堆（小根堆）的定义：

  • 最大堆中的最小元素值出现在根结点（堆顶）
  • 堆中每个父节点的元素值都小于等于其孩子结点
650075-91f1549ff0c87c15.png

时间复杂度：

  • 大根堆获取最大值的操作，时间复杂度为 \(O(1)\)。
  • 堆的插入和删除操作，时间复杂度为 \(O(logN)\) ，\(N\) 是节点个数。

堆的基础操作

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
class heap(object):
    def __init__(self):
        '''
        初始化一个空堆，使用数组来在存放堆元素，节省存储
        '''
        self.data_list = []

    def get_parent_index(self, index):
        '''
        返回父节点的下标
        '''
        if index == 0 or index > len(self.data_list) - 1:
            return None
        else:
            return (index - 1) >> 1 

    def swap(self,index_a, index_b):
        '''
        交换数组中的两个元素
        '''
        self.data_list[index_a],self.data_list[index_b] = self.data_list[index_b],self.data_list[index_a] 


    def insert(self, data):
        '''
        先把元素放在最后，然后从后往前依次堆化
        这里以大顶堆为例，如果插入元素比父节点大，则交换，直到最后
        '''
        self.data_list.append(data)
        index = len(self.data_list) - 1 
        parent = self.get_parent_index(index)
        # 循环，直到该元素成为堆顶，或小于父节点（对于大顶堆) 
        while parent is not None and self.data_list[parent] < self.data_list[index]:
            # 交换操作
            self.swap(parent,index)
            index = parent
            parent = self.get_parent_index(parent)

    def removeMax(self):
        '''
        删除堆顶元素，然后将最后一个元素放在堆顶，再从上往下依次堆化
        '''
        if len(self.data_list) > 0:
            remove_data = self.data_list[0]
            self.data_list[0] = self.data_list[-1]
            del self.data_list[-1]
            #堆化
            self.heapify(0)
            return remove_data
        else:
            print('堆空')
            return None


    def heapify(self, index):
        '''
        从上往下堆化，从index 开始堆化操作 (大顶堆)
        '''
        total_index = len(self.data_list) - 1
        while True:
            maxvalue_index = index
            if 2*index + 1 <=  total_index and self.data_list[2*index + 1] > self.data_list[maxvalue_index]:
                maxvalue_index = 2*index + 1
            if 2*index + 2 <=  total_index and self.data_list[2*index + 2] > self.data_list[maxvalue_index]:
                maxvalue_index = 2*index + 2
            if maxvalue_index == index:
                break
            self.swap(index,maxvalue_index)
            index = maxvalue_index
    
    def getMax(self):
        """
        获取堆顶元素
        """
        if len(self.data_list) > 0:
            return self.data_list[0]
        else:
            print('堆空')
            return None

if __name__ == "__main__":
    myheap = heap()
    # nums = [6, 4, 5, 1, 9, 2, 7, 3, 8]
    nums = [6]
    print("输入数据：{}".format(nums))
    print("开始建堆")
    for num in nums:
        myheap.insert(num)
    print("建堆完成:", myheap.data_list)
    print("获得堆顶元素：", myheap.getMax())
    print("当前的堆:", myheap.data_list)
    print("删除堆顶元素：", myheap.removeMax())
    print("删除之后的堆:", myheap.data_list)
    print("删除堆顶元素：", myheap.removeMax())
    print("删除之后的堆:", myheap.data_list)

Python内建的Heap

Python 中 heapq 模块是小顶堆。实现 大顶堆 方法： 小顶堆的插入和弹出操作均将元素 取反 即可。通过把元素取反再放入堆，出堆时再取反，把问题转换为最小堆问题也能间接实现最大堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from heapq import *

minHeap = []
maxHeap = []

# 插入小顶堆
num = 100
heappush(minHeap, num)
# 弹出小顶堆
heappop(minHeap)

num = 150
# 插入大顶堆
heappush(maxHeap, -num)
# 弹出大顶堆
-heappop(maxHeap)

常用函数

函 数 描 述
heappush(heap, x) 将x压入堆中
heappop(heap) 从堆中弹出最小的元素
heapify(heap)  让列表具备堆特征
heapreplace(heap, x)  弹出最小的元素，并将x压入堆中
nlargest(n, iter)  返回iter中n个最大的元素
nsmallest(n, iter)  返回iter中n个最小的元素

堆排序

堆排序是一种基于二叉堆（Binary Heap）结构的排序算法，所谓二叉堆，就是一种特殊的完全二叉树，只不过相比较完全二叉树而言，二叉堆的所有父节点的值都大于（或者小于）它的孩子节点，像这样：

v2-5d6119c9801eadb83402ef68f6d4b689_720w.jpg

堆排序算法的内容就很简单了，最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。

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
# 堆排序
 def heapSort(self, nums):
     # 交换list中的两个元素
     def swap(nums, i, j):
         tmp = nums[i]
         nums[i] = nums[j]
         nums[j] = tmp

     # 调整堆
     def heapify(nums, n, i):  # nums是数组、n是要调整的区间长度，i是要调整的根节点下标。
         largest = i
         l = 2 * i + 1  # 左节点
         r = 2 * i + 2  # 右节点
         if l < n and nums[l] > nums[largest]:  # 如果 left 比 root 大的话，l<n用于控制调整区间。
             largest = l
         if r < n and nums[r] > nums[largest]:  # 如果 right 比 root 大的话，r<n用于控制调整区间。
             largest = r
         if largest != i:  # 说明进行了调整，将堆顶和调整目标进行交换
             swap(nums, i, largest)
             # 递归调整子节点，此时largest是left或者right的节点的下标。
             heapify(nums, n, largest)

     _len = len(nums)

     # 建立堆
     #  range(n//2-1, -1, -1)是所有非叶子节点。从最后一个非叶子节点开始，使用heapify函数调整，保证根节点数值大于叶子节点数值。
     for i in range(_len // 2 - 1, -1, -1):  # i就是一个非叶子节点
         heapify(nums, _len, i)

     # 调整完之后，就建立了一个大根堆，从堆顶（nums[0]）取出元素。
     for i in range(_len - 1, -1, -1):  # i用于标记有序区，nums[>i]的部分都是有序区。
         # 一个一个的从堆顶（nums[0]）取出元素，和list无序区最后的元素nums[i]交换。
         swap(nums, i, 0)
         # 交换完成之后，从堆顶往下调整，使用i控制调整不会影响有序区。
         heapify(nums, i, 0)

     return nums

参考链接

堆的实现及工程应用(Python) https://www.jb51.net/article/87552.htm

算法与数据结构

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！