图论与图算法

part 1 图论基础&BFS

part1.1 图论基础

part1.2 BFS

# 广度优先搜索
import numpy as np  
import sympy as sp

class quene:
    '''
    实现一个队列，先入先出(FIFO)
    '''
    def __init__(self):
        self.quene = []
    def isEmpty(self): 
        return self.quene == []
    def push(self,element):
        self.quene.append(element)
    def pop(self):
        if self.isEmpty():
            print("quene is empty")
        else:
            self.quene.pop(0)
    def get_size(self):
        return len(self.quene)
    def disp(self):
        print(self.quene)


def search(G_matrix,single_source=0) -> np.ndarray:
    '''
    输入一个邻接矩阵和起点，输出一个无权图的最短路径
    '''

    vertex_q = quene()
    
    vertex_num = len(G_matrix) #获取节点数
    vertex_q.push(single_source) #将源节点加入队列
    visited = [0]*vertex_num #初始化访问数组
    distance = [0]*vertex_num #初始化距离数组
    path = [0]*vertex_num #初始化路径数组
    #处理源节点
    visited[single_source] = 1 #标记源节点已经访问
    path[single_source] = "start"
    #开始遍历
    while vertex_q.isEmpty() == False:
        current_vertex = vertex_q.quene[0]
        vertex_q.pop()
        for i in range(vertex_num):
            if G_matrix[current_vertex][i] == 1 and visited[i] == 0:
                vertex_q.push(i)
                visited[i] = 1
                distance[i] = distance[current_vertex] + 1
                path[i] = current_vertex
              
    vertex_number = np.arange(vertex_num)
    result_array_raw = np.array([vertex_number,visited,distance,path])
    result_array = result_array_raw.T
    name = np.array(["vertex","visited","distance","path"])
    
    r =  np.row_stack((name,result_array)) 
    return r
#---------------------------------测试---------------------------------
graph_matrix = np.array([
              [0,1,0,1,0,0,0],
              [0,0,0,1,1,0,0],
              [1,0,0,0,0,0,0],
              [0,0,1,0,1,1,1],
              [0,0,0,0,0,0,0],
              [0,0,1,0,0,0,0],
              [0,0,0,0,0,1,0]])


r = search(graph_matrix,3)
t = sp.Matrix(r)
t

$\displaystyle \left[\begin{matrix}vertex & visited & distance & path\\0 & 1 & 2 & 2\\1 & 1 & 3 & 0\\2 & 1 & 1 & 3\\3 & 1 & 0 & start\\4 & 1 & 1 & 3\\5 & 1 & 1 & 3\\6 & 1 & 1 & 3\end{matrix}\right]$

part 2 Dijkstra算法

#dijkstra算法
import numpy as np
import sympy as sp
import heapq 

class priority_queue:
    def __init__(self):
        self._queue = []
        self._index = 0
    def push(self,element,prior_value):
        heapq.heappush(self._queue,(prior_value,self._index, element))
        self._index += 1
    def pop(self):  
        return heapq.heappop(self._queue)[-1]
    def empty(self):
        return len(self._queue) == 0
    def __str__(self):
        return str(self._queue)
    

def search(Gmatrix, single_source=0) -> np.ndarray:
    '''
    采用Dijkstra算法，计算单源最短路径
    '''
    vertex_q = priority_queue()
    
    n = len(Gmatrix)
    
    #初始化距离和路径数组
    distance = [float('inf')]*n
    distance[single_source] = 0
    path = [-1]*n    
    
    #对节点进行遍历
    vertex_q.push(single_source,0)
    while not vertex_q.empty():
        current_vertex = vertex_q.pop()
        for i in range(n):
   
            temp_distance = Gmatrix[current_vertex][i] + distance[current_vertex]
            if Gmatrix[current_vertex][i] != 0 and temp_distance < distance[i]: #如果有路径且新的路径更短
                distance[i] = temp_distance #更新距离
                path[i] = current_vertex
                vertex_q.push(i,temp_distance)
    

    vertex_number = np.arange(n)
    result_array_raw = np.array([vertex_number,distance,path])
    result_array = result_array_raw.T
    name = np.array(["vertex","distance","path"])
    
    r =  np.row_stack((name,result_array))  
    return r

#-----------------test-----------------
graph_matrix = np.array([
              [0,2,0,1,0,0,0],
              [0,0,0,3,10,0,0],
              [4,0,0,0,0,5,0],
              [0,0,2,0,2,8,7],
              [0,0,0,0,0,0,1],
              [0,0,0,0,0,0,0],
              [0,0,0,0,0,1,0]])

r = search(graph_matrix,0)

t = sp.Matrix(r)
t

$\displaystyle \left[\begin{matrix}vertex & distance & path\\0 & 0 & -1\\1 & 2 & 0\\2 & 3 & 3\\3 & 1 & 0\\4 & 3 & 3\\5 & 5 & 6\\6 & 4 & 4\end{matrix}\right]$

part 3 最小生成树

part 3.1 Prim算法

#Prim算法求解最小生成树
import numpy as np
import sympy as sp
import random as rd
class prior_queue:
    '''
    用字典实现的优先队列
    '''
    def __init__(self):
        self.dict = {}
        
    def pop_min(self):
        min_key = min(self.dict, key=self.dict.get)
        self.dict.pop(min_key)
        return min_key
    
    def pop_max(self): 
        max_key = max(self.dict, key=self.dict.get)
        self.dict.pop(max_key)
        return max_key
        
    def push(self, key, priority):
        self.dict[key] = priority 
    
    def isEmpty(self):
        return len(self.dict) == 0
        
    def __str__(self):
        return str(self.dict)

def pr_search(Gmatrix) -> np.ndarray:
    '''
    用Prim算法生成最小生成树
    '''
    vertex_num = len(Gmatrix)
    vertex_set = set(range(vertex_num))
    exe_set = set()
    adjacent_matrix = np.zeros((vertex_num, vertex_num))
    start = rd.randint(0, vertex_num-1)
    exe_set.add(start)
    
    while exe_set != vertex_set:
        Bejudged_q = prior_queue()
        for i in exe_set:
            for j in range(vertex_num):
                if j not in exe_set and Gmatrix[i][j] != 0:
                    Bejudged_q.push((i, j), Gmatrix[i][j])
        (i, j) = Bejudged_q.pop_min()
        adjacent_matrix[i][j] = Gmatrix[i][j] #权重直接从Gmatrix读取
        exe_set.add(j)
    
    return adjacent_matrix
    
#--------------------test------------------------

graph_matrix = np.array([
              [0,2,4,1,0,0,0],
              [2,0,0,3,10,0,0],
              [4,0,0,2,0,5,0],
              [1,3,2,0,7,8,4],
              [0,10,0,7,0,0,6],
              [0,0,5,8,0,0,1],
              [0,0,0,4,6,1,0]])

r = pr_search(graph_matrix)
weight_sum = np.sum(r)
print('最小生成树的权重和为：', weight_sum)
t = sp.Matrix(r)
t

最小生成树的权重和为： 16.0

$\displaystyle \left[\begin{matrix}0 & 2.0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0\\1.0 & 0 & 2.0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 6.0\\0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 4.0 & 0 & 1.0 & 0\end{matrix}\right]$

part 3.2 Kruskal算法

#Kruskal算法求解最小生成树
import numpy as np
import sympy as sp
from DataFrame import priority_queue

class Dsu:
    '''
    并查集
    '''
    def __init__(self, size):
        self.size = size
        self.parent = np.arange(size) #存储父节点
        self.rank = np.zeros(size) #存储树的深度

    def find(self, x):
        '''
        查找节点
        '''  
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def is_same(self, x, y):
        return self.find(x) == self.find(y)
  
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            x, y = y, x
        self.parent[y] = x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    def __str__(self):
        return str(self.parent)

def k_search(Gmatrix) -> np.ndarray:
    
    vertex_num = len(Gmatrix)
    vertex = np.arange(vertex_num)
    dsu = Dsu(vertex_num)
    
    #将所有的边添加进优先队列中
    edge_q = priority_queue()
    for i in range(vertex_num):
        for j in range(i+1,vertex_num):
            if Gmatrix[i][j] != 0:
                edge_q.push((i,j),Gmatrix[i][j])
    
    selected_edge = set()
    while len(selected_edge) < vertex_num-1:
        if not edge_q.empty(): 
            temp = edge_q.pop_min()
            _edge = (temp[0],temp[1])
            if not dsu.is_same(_edge[0],_edge[1]):
                selected_edge.add(_edge)
                dsu.union(_edge[0],_edge[1])        
    
    tree_info = list(selected_edge)
    tree_matrix = np.zeros((vertex_num,vertex_num))
    for i in tree_info:
        tree_matrix[i[0]][i[1]] = Gmatrix[i[0]][i[1]]
    
    return tree_matrix
#----------------test-------------------------------
graph_matrix = np.array([
              [0,2,4,1,0,0,0],
              [2,0,0,3,10,0,0],
              [4,0,0,2,0,5,0],
              [1,3,2,0,7,8,4],
              [0,10,0,7,0,0,6],
              [0,0,5,8,0,0,1],
              [0,0,0,4,6,1,0]])

r = k_search(graph_matrix)
weight_sum = np.sum(r)
print('最小生成树的权重和为：', weight_sum)
t = sp.Matrix(r)
t

最小生成树的权重和为： 16.0

$\displaystyle \left[\begin{matrix}0 & 2.0 & 0 & 1.0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 2.0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 4.0\\0 & 0 & 0 & 0 & 0 & 0 & 6.0\\0 & 0 & 0 & 0 & 0 & 0 & 1.0\\0 & 0 & 0 & 0 & 0 & 0 & 0\end{matrix}\right]$