1 图

图由顶点（vertex）和边（edge）组成，通常表示为 G = (V, E)。
G表示一个图，V是顶点集，E是边集，顶点集V有穷且非空，任意两个顶点之间都可以用边来表示它们之间的关系，边集E可以是空的。

1.1 有向图

有向图的边是有明确方向的。

有向无环图（Directed Acyclic Graph，简称 DAG），如果一个有向图，从任意顶点出发无法经过若干条边回到该顶点，那么它就是一个有向无环图。

1.2 完全图

无向完全图的任意两个顶点之间都存在边，n 个顶点的无向完全图有 n(n − 1)/2 条边 n − 1 + n − 2 + n − 3 + ⋯ + 3 + 2 + 1。

1.3 稀疏、稠密图

稠密图（Dense Graph）：边数接近于或等于完全图。
稀疏图（Sparse Graph）：边数远远少于完全图。

1.4 连通图

如果顶点 x 和 y 之间存在可相互抵达的路径（直接或间接的路径），则称 x 和 y 是连通的，如果无向图 G 中任意2个顶点都是连通的，则称G为连通图。

1.5 图的实现方案

1.5.1 邻接矩阵（Adjacency Matrix）

邻接矩阵的存储方式：一维数组存放顶点信息，二维数组存放边信息。
邻接矩阵比较适合稠密图，不然会比较浪费内存。

1.5.2 邻接表（Adjacency List）

在该代码中采用的邻接表实现图。

1.5.3 十字链表

左侧表示进入的节点，右侧为出去的节点。

1.6 代码实现

1.6.1 图的基础接口

class Graph():
    def __init__(self):
        return

    def verticesSize(self):
        return

    def edgesSize(self):
        return

    def addVertex(self,v):
        """
        :param v:velue
        :return:
        """
        return

    def removeVertex(self,v):
        return

    def addEdge(self,fro,to,weight=None):
        return

    def removeEdge(self,fro,to):
        return

1.6.2 顶点定义

class Vertex():#节点
     def __init__(self,value):
         self.value=value
         self.inEdges=set()#入边
         self.outEdges=set()#出边

     def __hash__(self):
         return 0 if self.value==None else self.value.__hash__()

     def __eq__(self, other):#value相同则认为是同一个,value允许为空
         return other.value==None if self.value==None else self.value.__eq__(other.value)

     def __str__(self):
         return 'None' if self.value==None else str(self.value)

1.6.3 边的定义

@total_ordering
 class Edge():#边
     def __init__(self,fro,to,weight=1):
         self.fro=fro
         self.to=to
         self.weight=weight

     def __hash__(self):
         return 31*self.fro.__hash__()+self.to.__hash__()

     def __eq__(self, other):#two edges which have the same from and to node is considered same
         return self.fro.__eq__(other.fro) and self.to.__eq__(other.to)

     def __str__(self):
         return "Edge [from=" + str(self.fro) + ", to=" + str(self.to) + ", weight=" + str(self.weight) + "]"

     def __le__(self, other):  # 小于等于
         return self.weight <= other.weight

1.6.4 整体代码

'''
基类 Graph
'''
from typing import Set


class Graph():
    def __init__(self):
        return

    def verticesSize(self):
        return

    def edgesSize(self):
        return

    def addVertex(self,v):
        """
        :param v:velue
        :return:
        """
        return

    def removeVertex(self,v):
        return

    def addEdge(self,fro,to,weight=None):
        print('2')
        return

    def removeEdge(self,fro,to):
        return

    class EdgeInfo():
        def __init__(self,fro,to,weight):
            self.fro=fro
            self.to=to
            self.weight=weight

        def __str__(self):
            return '[fro:'+str(self.fro)+' to:'+str(self.to)+' weight:'+str(self.weight)+']'

    def mst(self)-> Set[EdgeInfo]:#minimum spanning tree 最小生成树
        return set()

'''
List Graph 采用邻接表实现的图，实际上是邻接表和逆邻接表的组合十字链表
'''
import heapq
from typing import Set
from queue import Queue,LifoQueue
from Graph import Graph
from functools import total_ordering

class ListGraph(Graph):
    def __init__(self):
        self.vertices={}#采用哈希表map存储所有节点
        self.edges=set()#采用集合set存储所有边

    def verticesSize(self):
        return len(self.vertices)

    def edgesSize(self):
        return len(self.edges)

    def addVertex(self,v=None):
        """
        :param v:velue
        """
        if v in self.vertices.keys():return
        self.vertices[v]=ListGraph.Vertex(v)

    def removeVertex(self,v):
        # the vertext to be removed doesn't exist
        if v not in self.vertices.keys():return
        vertex_delete=self.vertices.get(v)
        for edge in vertex_delete.outEdges:
            self.edge.to.inEdges.remove(edge)
            self.edges.remove(edge)
        for edge in vertex_delete.inEdges:
            self.edge.fro.outEdges.remove(edge)
            self.edges.remove(edge)
        del(self.vertices[v])


    def addEdge(self,fro,to,weight=None):
        """
        :param fro:value of start node
        :param to: value of end node
        :param weight: edge weight
        """
        from_vertex=self.vertices.get(fro)
        #if the nodes in the edge don't exit, create them at first
        if not from_vertex:
            from_vertex=ListGraph.Vertex(fro)
            self.vertices[fro]=from_vertex
        to_vertex=self.vertices.get(to)
        if not to_vertex:
            to_vertex=ListGraph.Vertex(to)
            self.vertices[to]=to_vertex
        # now from and to is absolutely exist
        edge=ListGraph.Edge(from_vertex,to_vertex,weight)
        # if the edge is already exist, delete the original edge
        if edge in self.edges:
            from_vertex.outEdges.remove(edge)
            to_vertex.inEdges.remove(edge)
            self.edges.remove(edge)
        # add the edge with new weight
        from_vertex.outEdges.add(edge)
        to_vertex.inEdges.add(edge)
        self.edges.add(edge)

    def removeEdge(self,fro,to):
        out_vertex = self.vertices.get(fro)
        if out_vertex==None:return
        in_vertex = self.vertices.get(to)
        if in_vertex==None:return
        edge=ListGraph.Edge(fro,to)
        if edge not in self.edges:return
        out_vertex.outEdges.remove(edge)
        in_vertex.inEdges.remove(edge)
        self.edges.remove(edge)

    def showGraph(self):
        for vertex in self.vertices.values():
            print(vertex)
            print('out--------------')
            str_out=""
            for i in vertex.outEdges:
                str_out+=str(i)+' '
            print('None' if len(str_out)==0 else str_out)
            print('in--------------')
            str_in=""
            for i in vertex.inEdges:
                str_in+=str(i)+' '
            print('None' if len(str_in)==0 else str_in)
        print('tatol edges : ')
        for edge in self.edges:
            print(edge)
        print()

    class Vertex():#节点
        def __init__(self,value):
            self.value=value
            self.inEdges=set()#入边
            self.outEdges=set()#出边

        def __hash__(self):
            return 0 if self.value==None else self.value.__hash__()

        def __eq__(self, other):#value相同则认为是同一个,value允许为空
            return other.value==None if self.value==None else self.value.__eq__(other.value)

        def __str__(self):
            return 'None' if self.value==None else str(self.value)

    @total_ordering
    class Edge():#边
        def __init__(self,fro,to,weight=1):
            self.fro=fro
            self.to=to
            self.weight=weight

        def __hash__(self):
            return 31*self.fro.__hash__()+self.to.__hash__()

        def __eq__(self, other):#two edges which have the same from and to node is considered same
            return self.fro.__eq__(other.fro) and self.to.__eq__(other.to)

        def __str__(self):
            return "Edge [from=" + str(self.fro) + ", to=" + str(self.to) + ", weight=" + str(self.weight) + "]"

        def __le__(self, other):  # 小于等于
            return self.weight <= other.weight

def graph_one():
    graph = ListGraph()
    # generate edges
    graph.addEdge(0, 4, 6)
    graph.addEdge(1, 0, 9)
    graph.addEdge(1, 2, 3)
    graph.addEdge(2, 0, 2)
    graph.addEdge(2, 3, 5)
    graph.addEdge(3, 4, 1)
    graph.showGraph()
    # graph.removeEdge(0,4)
    # graph.removeVertex(3)
    # graph.showGraph()
    # graph.bfs(2)
    # graph.bfs(1)
    # graph.bfs(3)
    graph.dfs(1)
    # graph.dfs(2)
    graph.dfs_nonrecursion(1)
    
if __name__=='__main__':
    graph_one()

代码中的图。

1.6.5 图的广搜

def bfs(self,v):#广度优先搜索
     print('breadth first search----------------')
     vertex=self.vertices.get(v)
     if vertex==None:return
     q=Queue()
     visited_v_set=set()
     q.put(vertex)
     visited_v_set.add(vertex)
     while not q.empty():
         vertex=q.get()
         print(vertex)
         for edge in vertex.outEdges:
             to_v=self.vertices.get(edge.to)
             if to_v in visited_v_set:
                 continue
             else:
                 q.put(to_v)
                 visited_v_set.add(to_v)  

`

1.6.6 图的深搜

def dfs_inner(self, vertex, set_v):
       if vertex==None:return
       print(vertex.value)
       set_v.add(vertex)
       for edge in vertex.outEdges:
           if edge.to in set_v:
               continue
           else:
               self.dfs_inner(edge.to,set_v)
                
def dfs(self,v):
     print('depth first search----------------')
     vertex=self.vertices.get(v)
     if vertex==None:return
     self.dfs_inner(vertex,set())