图

1 图的邻接矩阵表示

inf = float("inf")
class Graph:
    def __init__(self, mat, unconn=0):
        vnum = len(mat)
        for x in mat:
            if len(x) != vnum:
                raise ValueError("Argument for 'Graph'.")
        self._mat = [mat[i][:] for i in range(vnum)]
        self._unconn = unconn
        self._vnum = vnum
        
    def vertex_num(self):
        return self._vnum
    
    def _invalid(self, v):
        return 0 > v or v >= self._vnum
    
    def add_vertex(self):
        raise GraphError("Adj-Matrix does not support 'add_vertex'.")
        
    def add_edge(self, vi, vj, val = 1):
        if self._invalid(vi) or self._invalid(vj):
            raise GraphError(str(vi) + 'or'+ str(vj) + " is not a valid vertex.")
        self._mat[vi][vj] = val
        
    def get_edge(self, vi, vj):
        if self._invalid(vi) or self._invalid(vj):
            raise GraphError(str(vi) + 'or'+ str(vj) + " is not a valid vertex.")
        return self._mat[vi][vj]
    
    def out_edges(self, vi):
        if self._invalid(vi):
            raise GraphError(str(vi) + " is not a valid vertex.")
        return self._out_edges(self._mat[vi], self._unconn)
    
    @staticmethod
    def _out_edges(row, unconn):
        edges = []
        for i in range(len(row)):
            if row[i] != unconn:
                edges.append((i, row[i]))
        return edges

2 图的邻接表表示

class Graph2:
    def __init__(self):
        self.node_neighbors = {}
        self.nodes = []
        
        
    def nodes(self):
        return self.node_neighbors.keys()
        
    def add_nodes(self, nodelist):
        for node in nodelist:
            self.add_node(node)
            
    def add_node(self, node):
        if not node in self.nodes():
            self.node_neighbors[node] = []
            
    def add_edge(self, edge):
        u, v = edge
        if (v not in self.node_neighbors[u]):
            self.node_neighbors[u].append(v)
        
    def depth_search(self, root = None):
        order = []
        visited = {}
        
        def dfs(node):
            visited[node] = True
            order.append(node)
            for n in self.node_neighbors[node]:
                if not n in visited:
                    dfs(n)
        
        if root:
            dfs(root)
        for n in self.nodes():
            if not n in visited:
                dfs(n)
        print(order)
        
    def breadth_search(self, root = None):
        queue = []
        order = []
        visited = {}
        def bfs():
            while len(queue) > 0:
                node = queue.pop(0)
                visited[node] = True
                for n in self.node_neighbors[node]:
                    if (not n in visited) and (not n in queue):
                        queue.append(n)
                        order.append(n)
        if root:
            queue.append(root)
            order.append(root)
            bfs()
        for node in self.nodes():
            if not node in visited:
                queue.append(node)
                order.append(node)
        print(order)

3 生成树

def DFS_span_forest(graph):
    vnum = graph.vertex_num()
    span_forest = [None] * vnum
    
    def dfs(graph, v):
        nonlocal span_forest  #在函数或其他作用域中使用外层(非全局)变量
        for u, w in graph.out_edges(v):
            if span_forest[u] is None:
                span_forest[u] = (v, w)
                dfs(graph, u)
    for v in range(vnum):
        if span_forest[v] is None:
            span_forest[v] = (v, 0)
            dfs(graph, v)
    return span_forest

4 dijkstra

# 动规
def dijkstra(A,v0): # v0: [0 ,vnum-1]
    vnum = len(A[0])
    res = [float('inf')] * vnum
    book = [0] * vnum  # 记录是否访问
    start = v0
    res[start] = 0
    book[start] = 1
    for i in range(vnum):
        res[i] = min(res[i], A[start][i])
    for i in range(vnum-1):
        minn = float('inf')
        for j in range(vnum):
            if book[j] == 0 and minn > res[j]:
                minn = res[j]
                start = j
        book[start] = 1
        for j in range(vnum):
            res[j] = min(res[j], res[start] + A[start][j])
    return res

5 floyd

def floyd(A):
    vnum = len(A[0])
    nextvet = [[-1 if A[i][j] == inf else j
               for j in range(vnum)]
              for i in range(vnum)]
    for k in range(vnum):
        for i in range(vnum):
            for j in range(vnum):
                if A[i][j] > A[i][k] + A[k][j]:
                    A[i][j] = A[i][k] + A[k][j]
                    nextvet[i][j] = nextvet[i][k]
    return (A, nextvet)

inf = float('inf')
A = [[0,5,8,inf,inf],[5,0,1,3,2],[8,1,0,inf,inf],[inf,3,inf,0,7],[inf,2,inf,7,0]]
print(floyd(A)[0])

6 kruskal & 并查集

def find(x,parent):
    s = x
    while parent[s] >= 0:
        s = parent[s]
    while s != x:
        tmp = parent[x]
        parent[x] = s
        x = tmp
    return s

def union(R1, R2, parent):
    r1 = find(R1, parent)
    r2 = find(R2, parent)
    tmp = parent[r1] + parent[r2]
    if parent[r1] < parent[r2]:
        parent[r2] = r1
        parent[r1] = tmp
    else:
        parent[r1] = r2
        parent[r2] = tmp

def Kruskal(A): 
    vnum = len(A[0])
    edges = []
    for i in range(vnum-1):
        for j in range(i+1,vnum):
            if A[i][j] != float('inf'):
                edges.append((A[i][j], i, j))
    edges.sort()
    print(edges)
    parent = [-1] * vnum
    res = []
    sumweight = 0
    enum = 0
    for i in range(len(edges)):
        if find(edges[i][1], parent) != find(edges[i][2], parent):
            res.append((edges[i][1],edges[i][2]))
            sumweight += edges[i][0]
            union(edges[i][1],edges[i][2], parent)
            enum += 1
            print(parent)
            print((edges[i][1],edges[i][2]))
        if enum >= vnum - 1:
            break
    return res

inf = float('inf')
A = [[0,5,8,inf,inf],[5,0,1,3,2],[8,1,0,inf,inf],[inf,3,inf,0,7],[inf,2,inf,7,0]]
print(Kruskal(A))

[(1, 1, 2), (2, 1, 4), (3, 1, 3), (5, 0, 1), (7, 3, 4), (8, 0, 2)]
[-1, 2, -2, -1, -1]
(1, 2)
[-1, 2, -3, -1, 2]
(1, 4)
[-1, 2, -4, 2, 2]
(1, 3)
[2, 2, -5, 2, 2]
(0, 1)
[(1, 2), (1, 4), (1, 3), (0, 1)]