数据结构-图形结构

àì夳堔傛蜴生んèń 2023-10-04 14:57 4阅读 0赞

#### 数据结构-图形结构 ####

树形结构的最大不同就是描述节点与节点直接“层次”的关系，但是图形结构却是讨论两个顶点之间“连通与否”的关系，如果为图形中连接两顶点的边填上加权值，这类图形就称为“网络”

1.  #### **图形简介** ####
    
    图形理论时欧拉为了解决“哥白尼堡”问题所想出来的一种数据结构理论，这就是著名的“七桥问题”
    
    1.  **欧拉环与欧拉链**
        
        欧拉当时使用的方法就是以图形结构来进行分析的。他以顶点表示城市，以边表示桥梁，并定义了连接每个顶点的边数，称为该顶点的度数。
        
        欧拉最后得出一个结论：当所有顶点的度数都为偶数时，才能从某顶点出发，经过每条边一次，再回到起点。这个理论就是有名的欧拉环理论
        
        但是，如果条件改成从某顶点出发，经过每条边一次，不一定要回到起点，即只允许其中两个顶点的度数时奇数，其余则必须全部为偶数，符合这样结果的就称为时欧拉链
    2.  **图形的定义**
        
        图是由“顶点”和“边”所组成的集合，通常用G=(V,E)来表示，其中V是所有顶点所组成的集合，而E代表所有边所组成的集合。图的种类有两种：一种是无向图，另一种是有向图，无向图(V1,V2)表示其边，而有向图则以<V1,V2>表示其边
    3.  **无向图**
        
        无向图就是一种边没有方向的图，即同边的两个顶点没有次序关系
        
        V=\{A,B,C,D,E\}
        
        E=\{(A,B),(A,E),(B,C),(C,D),(C,E),(D,E)\}
        
        无向图中的重要术语：
        
         *  完全图：N个顶点正好有N(N-1)/2条边，这就是完全图
         *  路径：对于从顶点Vi到顶点Vj的一条路径，是由所经过顶点组成的连续数列
         *  简单路径：除了起点和中点可能相同外，其他经过的顶点都不相同
         *  路径长度：指路径上所包含边的数目
         *  回路：起始顶点和终止顶点为同一个点的简单路径称为回路
         *  关联：如果Vi和Vj相邻，就称(Vi,Vj)这个边关联于顶点Vi及顶点Vj
         *  子图：当我们称G`为G的子图时，必定存在V(G`)属于V(G)与E(G\`)属于E(G)
         *  相邻：如果(Vi,Vj)是E(G)的一条边，就成Vi与Vj相邻
         *  联通分支：在无向图中，相连在一起的最大子图
         *  度数：在无向图中，一个顶点所拥有边的总数为度数
    4.  **有向图**
        
        有向图时一种每一条边都可使用有序对<V1,V2>来表示的图，并且<V1,V2>与<V2,V1>用于表示两个方向不同的边，而<V1,V2>是指V1为尾端，指向头部的V2
        
        V=\{A,B,C,D,E\}
        
        E=\{<A,B>,<B,C>,<C,D>,<C,E>,<E,D>,<D,B>\}
        
        有向图的相关定义
        
         *  完全图：具有n个顶点且恰好有n\*(n-1)个边的有向图
         *  路径：有向图中从顶点Vp到顶点Vq的路径是指向一串由顶点所组成的连续有向序列
         *  强连通：有向图中，如果每个成对顶点Vi、Vj有直接路径，同时有另一条路径从Vj到Vi，就称此图为强连通
         *  强连通分支：有向图中构成强连通的最大子图
         *  出度数：是指有向子图中以顶点V为箭尾的边数
         *  入度数：是指有向图中以顶点V为箭头的边数
2.  #### **图的数据表示法** ####
    
    1.  **邻接矩阵法**
        
        图A有n个顶点，以n\*n的二维矩阵来表示。此矩阵的定义如下：
        
        对于一个图G=(V,E),假设有n个顶点，n>=1,则可以将n个顶点的图使用一个n\*n的二维矩阵表示，其中假设A(i,j)=1,则表示图中有一条边(Vi,Vj)存在，反之，A(i,j)=0，则不存在边(Vi,Vj)
        
         *  对于无向图，邻接矩阵一定时对称的，而且对角线一定为0，有向图则不一定
         *  无向图这种，任一节点i的度数为第i行所有元素的和。在有向图中，节点i的出度数就是第i行所有元素的和，而入度数就是第j列所有元素的和
         *  用邻接矩阵法表示图共需要n\*n个单位空间，由于无向图的邻接矩阵一定是具有对称关系的，扣除对角线全部为零外，仅需要存储上三角或者下三角的数据即可，因此仅需要n(n-1)/2的单位空间
            
            <table> 
             <thead> 
              <tr> 
               <th>0</th> 
               <th>1</th> 
               <th>0</th> 
               <th>1</th> 
               <th>0</th> 
              </tr> 
             </thead> 
             <tbody> 
              <tr> 
               <td>1</td> 
               <td>0</td> 
               <td>1</td> 
               <td>0</td> 
               <td>1</td> 
              </tr> 
              <tr> 
               <td>0</td> 
               <td>1</td> 
               <td>0</td> 
               <td>1</td> 
               <td>0</td> 
              </tr> 
              <tr> 
               <td>1</td> 
               <td>0</td> 
               <td>1</td> 
               <td>0</td> 
               <td>0</td> 
              </tr> 
              <tr> 
               <td>0</td> 
               <td>1</td> 
               <td>0</td> 
               <td>0</td> 
               <td>0</td> 
              </tr> 
             </tbody> 
            </table>
        
        上面这个5\*5的二维数组就是一个具有五个顶点的图形，V(2,1)=1代表顶点2和顶点1之间存在一条边，一次类推，可以得出图的结构
        
        对于有向图，邻接矩阵则不一定是对称矩阵。其中节点i的出度数就是第i行的所有元素1的和，而入度数就是j列所有元素1的和
        
        用python描述无向图或者有向图的6\*6邻接矩阵的算法:
        
            for i in range(10):		#读取图的数据
                for k in range(6):		#赋值矩阵
                    tmpi = data[i][0]		#tmpi为起始顶点
                    tmpj = data[i][1]		#tmpj为终止顶点
                    arr[tmpi][tmpj] = 1		#有边的点填入1
        
        例子：设计一个无向图，数据如下所示
        
            data = [[1,2],[2,1],[2,3],[3,2],[2,5],[5,2],[3,4],[4,3],[1,4],[4,1]]
        
            data = [[1,2],[2,1],[2,3],[3,2],[2,5],[5,2],[3,4],[4,3],[1,4],[4,1]]
            arr = [[0] * 6 for row in range(6)]
            for i in range(10):
                for k in range(6):
                    tempi = data[i][0]
                    tempj = data[i][1]
                    arr[tempi][tempj] = 1
            
            print("无向图矩阵")
            for i in range(1,6):
                for j in range(1,6):
                    print('[%d]'%arr[i][j],end='')
                print('')
        
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA_size_16_color_FFFFFF_t_70]
        
        例子：设计一个有向图，数据如下
        
            data = [[1,2],[2,1],[2,3],[4,3],[4,1]]
        
        和有向图的算法设计相似
        
            data = [[1,2],[2,1],[2,3],[4,3],[4,1]]
            arr = [[0] * 6 for row in range(6)]
            for i in range(len(data)):
                # for j in range(2):
                for k in range(6):
                    tempi = data[i][0]
                    tempj = data[i][1]
                    arr[tempi][tempj] = 1
            
            print("无向图矩阵")
            for i in range(1,6):
                for j in range(1,6):
                    print('[%d]'%arr[i][j],end='')
                print('')
        
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA_size_16_color_FFFFFF_t_70 1]
    2.  **邻接表法**
        
        邻接矩阵法，优点就是借着矩阵的运算有许多特别的应用。要在图中加入新边时，这个表示法的插入与删除操作相当容易。不过要考虑到稀疏矩阵空间浪费的问题，另外，如果要计算所有顶点的度数，其实践复杂度为O(n^2)
        
        因此可以考虑更有效的方法，就是邻接表法。这种表示法就是将一个n行的邻接矩阵表示成n个链表，这种做法和邻接矩阵相比较节省空间，如果计算所有顶点的度数时，其实践复杂度为O(n+e)，缺点是：例如有新边加入图中或从图中删除边时，就要修改相关的链接，较为麻烦费时
        
            class list_node:
                def __init__(self):
                    self.val = 0
                    self.next = None
        
        简单来说，有几个顶点就会有多少个链表头，只要和该顶点相连接的顶点，都将其与链表头连接
        
        例子：使用数组存储图的边并建立邻接表
        
            class list_node:
                def __init__(self):
                    self.val = 0
                    self.next = None
            
            head = [list_node] * 6      #声明一个节点类型的链表
            newnode = list_node()
            #图的数组声明
            data = [[1,2],[2,1],[2,5],[5,2],[2,3],[3,2],[2,4],[4,2],\
                    [3,4],[4,3],[3,5],[5,3],[4,5],[5,4]]
            print('图的邻接表内容：')
            print('-----------------------')
            for i in range(1,6):
                head[i].val = i     #链表头的head值
                head[i].next = None     #链表头的next为0
                print("顶点%d => "%i,end='')
                ptr = head[i]
                for j in range(len(data)):
                    if data[j][0] == i:     #顶点i相同那个
                        newnode.val = data[j][1]    #连接的数值
                        newnode.next = None
                        while ptr != None:
                            ptr = ptr.next
                        ptr = newnode   #相当于head.next = newnode,head.next.next = newnode .....
                        print('[%d] '%newnode.val,end='')
                print('')
        
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA_size_16_color_FFFFFF_t_70 2]
    3.  **邻接符合链表法**
        
        上面的两种方法都是从图的顶点出发，但是如果要处理的是边，就必须使用邻接符合链表。临街符合链表是处理无向图的另一种方法。邻接复合链表的节点用于存储边的数据，结构如下：
        
        <table> 
         <thead> 
          <tr> 
           <th>M</th> 
           <th>V1</th> 
           <th>V2</th> 
           <th>LINK1</th> 
           <th>LINK2</th> 
          </tr> 
         </thead> 
         <tbody> 
          <tr> 
           <td>记录单元</td> 
           <td>边起点</td> 
           <td>边中点</td> 
           <td>起点指针</td> 
           <td>终点指针</td> 
          </tr> 
         </tbody> 
        </table>
        
        其中，相关特性说明
        
         *  M：用于记录该边是否是被找过的字段，此字段为一个位(比特)
         *  V1和V2：是所记录的边的起点和终点
         *  LINK1：在尚有其他顶点与V1相连的情况下，此字段会指向下一个与V1相连的边节点，如果已经没有任何顶点与V1相连，就指向None
         *  LINK2：在尚有其他顶点与V2相连的情况下，此字段会指向下一个与V2相连的边节点，如果已经没有任何顶点与V2相连，就指向None
        
        例如有三条边(1,2),(1,3),(2,4),边(1,2)的复合链表表示法可以是：
        
        <table> 
         <thead> 
          <tr> 
           <th>M1</th> 
           <th>1</th> 
           <th>2</th> 
           <th>M2</th> 
           <th>M3</th> 
          </tr> 
         </thead> 
         <tbody> 
          <tr> 
           <td>M2</td> 
           <td>1</td> 
           <td>3</td> 
           <td></td> 
           <td></td> 
          </tr> 
          <tr> 
           <td>M3</td> 
           <td>2</td> 
           <td>4</td> 
           <td></td> 
           <td></td> 
          </tr> 
         </tbody> 
        </table>
    4.  **索引表格法**
        
        索引表格表示法是一种用一维数组来按序存储与各顶点相邻的所有顶点，并建立索引表格来记录个顶点在此一维数组中第一个与该顶点相邻的位置
        
        比如一个A,B,C,D相互连接的图，使用索引表格法表示
        
        <table> 
         <thead> 
          <tr> 
           <th>A</th> 
           <th>B</th> 
           <th>C</th> 
           <th>D</th> 
          </tr> 
         </thead> 
         <tbody> 
          <tr> 
           <td>1</td> 
           <td>4</td> 
           <td>7</td> 
           <td>10</td> 
          </tr> 
         </tbody> 
        </table>
        
        <table> 
         <thead> 
          <tr> 
           <th>B</th> 
           <th>C</th> 
           <th>D</th> 
           <th>A</th> 
           <th>C</th> 
           <th>D</th> 
           <th>A</th> 
           <th>B</th> 
           <th>D</th> 
           <th>A</th> 
           <th>B</th> 
           <th>C</th> 
          </tr> 
         </thead> 
         <tbody></tbody> 
        </table>
        
         *  邻接矩阵
            
            图G=(V,E)共有n个顶点，我们以n\*n的二维矩阵来表示点与点之间是否邻接，
            
            aij = 0 表示顶点i和顶点j没有相邻的边
            
            aij = 1 表示顶点i和顶点j有相邻的边
         *  邻接表法
            
            就是链表头表示的，其相邻的点放在链表头之后
            
            可以看作是索引表格中运用邻接表法
         *  索引表格法
            
            用一个二维数组来按序存储与各顶点的所有顶点，并建立索引表格来记录各顶点在此一维数组中的第一个与该顶点相邻的位置
            
            <table> 
             <thead> 
              <tr> 
               <th>A</th> 
               <th>B</th> 
               <th>C</th> 
               <th>D</th> 
              </tr> 
             </thead> 
             <tbody> 
              <tr> 
               <td>1</td> 
               <td>4</td> 
               <td>6</td> 
               <td>8</td> 
              </tr> 
             </tbody> 
            </table>
            
            <table> 
             <thead> 
              <tr> 
               <th>A</th> 
               <th>B</th> 
               <th>C</th> 
              </tr> 
             </thead> 
             <tbody> 
              <tr> 
               <td>11</td> 
               <td>13</td> 
               <td>14</td> 
              </tr> 
             </tbody> 
            </table>
            
            <table> 
             <thead> 
              <tr> 
               <th>1</th> 
               <th>2</th> 
               <th>3</th> 
               <th>4</th> 
               <th>5</th> 
               <th>6</th> 
               <th>7</th> 
               <th>8</th> 
               <th>9</th> 
               <th>10</th> 
               <th>11</th> 
               <th>12</th> 
               <th>13</th> 
               <th>14</th> 
              </tr> 
             </thead> 
             <tbody> 
              <tr> 
               <td>B</td> 
               <td>C</td> 
               <td>D</td> 
               <td>A</td> 
               <td>D</td> 
               <td>A</td> 
               <td>D</td> 
               <td>A</td> 
               <td>B</td> 
               <td>C</td> 
               <td>B</td> 
               <td>C</td> 
               <td>A</td> 
               <td>A</td> 
              </tr> 
             </tbody> 
            </table>
3.  #### **图的遍历** ####
    
    树的遍历目的是访问树的每一个节点一次，可用的方法有中序法、前序法、后序法三种。至于图的遍历，可以定义如下：
    
    一个图G=(V,E)，存在某一定点v属于V，我们希望从v开始，通过此节点相邻的节点而去访问图G中的其他节点，这就被称为“图的遍历”。
    
    就是从某一个顶点V1开始，遍历可以经过V1到达的顶点，接着遍历下一个顶点直到全部的顶点遍历完毕为止。在遍历的过程中可能会重复经过某些顶点和边。通过图的遍历可以判断该图是否连通，并找出连通分支和路径。图遍历的方法有两种：深度优先遍历和广度优先遍历。
    
    1.  **深度优先遍历**
        
        深度优先遍历的方法有些类似于前序遍历。是从图的某一顶点开始遍历，被访问过的顶点就做上已经访问的记号，接着遍历此顶点的所有相邻且未曾访问过的顶点中任意一个顶点，并做上已经访问的记号，再以该节点为新的起点继续进行深度优先的搜索
        
        这种图的遍历方法结合了递归和堆栈两种数据结构的技巧，由于此方法会造成无限循环，因此必须加入一个变量，判断该点是否已经遍历完成。
        
        举例：
        
        比如有五个顶点1、2、3、4、5，相互直接连接方法全靠想象，使用深度优先遍历法遍历的过程
        
        以顶点1为起点，将相邻的顶点2和顶点5压入堆栈
        
        <table> 
         <thead> 
          <tr> 
           <th>5</th> 
           <th>2</th> 
           <th></th> 
           <th></th> 
           <th></th> 
          </tr> 
         </thead> 
         <tbody></tbody> 
        </table>
        
        弹出顶点2，将与顶点2相邻且未曾访问的顶点3和顶点4压入堆栈
        
        <table> 
         <thead> 
          <tr> 
           <th>5</th> 
           <th>4</th> 
           <th>3</th> 
           <th></th> 
           <th></th> 
          </tr> 
         </thead> 
         <tbody></tbody> 
        </table>
        
        弹出顶点3，将与顶点3相邻的顶点4和顶点5压入堆栈
        
        <table> 
         <thead> 
          <tr> 
           <th>5</th> 
           <th>4</th> 
           <th>5</th> 
           <th>4</th> 
           <th></th> 
          </tr> 
         </thead> 
         <tbody></tbody> 
        </table>
        
        弹出顶点4，将与顶点4相邻且未被访问过的顶点5压入堆栈
        
        <table> 
         <thead> 
          <tr> 
           <th>5</th> 
           <th>4</th> 
           <th>5</th> 
           <th>5</th> 
           <th></th> 
          </tr> 
         </thead> 
         <tbody></tbody> 
        </table>
        
        弹出顶点5，将与顶点5相邻且未被访问过的顶点5压入堆栈
        
        <table> 
         <thead> 
          <tr> 
           <th>5</th> 
           <th>4</th> 
           <th>5</th> 
           <th></th> 
           <th></th> 
          </tr> 
         </thead> 
         <tbody></tbody> 
        </table>
        
        将堆栈中的值弹出并判断是否已经遍历过了，直到堆栈中无节点可遍历为止
        
        <table> 
         <thead> 
          <tr> 
           <th></th> 
           <th></th> 
           <th></th> 
           <th></th> 
           <th></th> 
          </tr> 
         </thead> 
         <tbody></tbody> 
        </table>
        
        所以，深度优先的遍历顺序为：顶点1、顶点2、顶点3、顶点4、顶点5
        
        深度优先遍历算法：
        
            def dfs(current):
            	run[current] = 1
            	print('[%d]'%current,end='')
                ptr = head[current].next
                while ptr != None:
                    if run[ptr.val] == 0:		#如果顶点尚未遍历
                        dfs(ptr.val)		#进行dfs的递归调用
                    ptr = ptr.next
        
        例子：将深度优先遍历方法用python实现，数据如下
        
            data = [[1,2],[2,1],[1,3],[3,1],\
                   		  	[2,4],[4,2],[2,5],[5,2],\
                   			[3,6],[6,3],[5,8],[8,5],\
                   			[4,8],[8,4],[5,8],[8,5],\
                   			[6,8],[8,6],[8,7],[7,8]]
        
            class list_node:
                def __init__(self):
                    self.val = 0
                    self.next = None
            
            head = [list_node()] * 9    #声明一个链表头数组
            run = [0] * 9      #用来记录是否被遍历过的节点
            
            def dfs(current):
                run[current] = 1
                print('[%d] '%current,end='')
                ptr = head[current].next
                while ptr != None:
                    if run[ptr.val] == 0:
                        dfs(ptr.val)
                    ptr = ptr.next
            
            data = [[1,2],[2,1],[1,3],[3,1], \
                    [2,4],[4,2],[2,5],[5,2], \
                    [3,6],[6,3],[5,8],[8,5], \
                    [4,8],[8,4],[5,8],[8,5], \
                    [6,8],[8,6],[8,7],[7,8]]
            for i in range(1,9):    #共有八个顶点，1-8
                run[i] = 0
                head[i] = list_node()
                head[i].val = i     #给各个链表头设置初值
                head[i].next = None
                ptr = head[i]   #设置指针指向链表头
                for j in range(20):     #20条边
                    if data[j][0] == i:     #如果起点和链表头相等，就把顶点加入链表
                        newnode = list_node()
                        newnode.val = data[j][1]
                        newnode.next = None
                        while True:
                            ptr.next = newnode
                            ptr = ptr.next
                            if ptr.next == None:
                                break
            
            print('图的邻接表内容')
            for i in range(1,9):
                ptr = head[i]
                print('顶点%d=>'%i,end='')
                ptr = ptr.next
                while ptr != None:
                    print('[%d]'%ptr.val,end='')
                    ptr = ptr.next
                print()
            print('深度优先遍历的顶点：')
            dfs(1)
            print()
        
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA_size_16_color_FFFFFF_t_70 3]
    2.  **广度优先遍历**
        
        深度优先遍历是利用堆栈和递归的技巧来遍历图，而广度优先遍历法则是使用队列和递归技巧来遍历，也是从图的某一定点开始遍历，被访问过的顶点就做上已访问的记号
        
        接着遍历此顶点的所有相邻且未访问过的顶点中的任意一个顶点，并做上已访问的记号，再以该点为新的起点继续进行广度优先的遍历。
        
        比如有五个顶点1、2、3、4、5，相互直接连接方法全靠想象，使用深度优先遍历法遍历的过程
        
        以顶点1为起点，将相邻的顶点2和顶点5压入堆栈
        
        <table> 
         <thead> 
          <tr> 
           <th>2</th> 
           <th>5</th> 
           <th></th> 
           <th></th> 
           <th></th> 
          </tr> 
         </thead> 
         <tbody></tbody> 
        </table>
        
        弹出顶点2，将与顶点2相邻且未曾访问的顶点3和顶点4压入堆栈
        
        <table> 
         <thead> 
          <tr> 
           <th>5</th> 
           <th>3</th> 
           <th>4</th> 
           <th></th> 
           <th></th> 
          </tr> 
         </thead> 
         <tbody></tbody> 
        </table>
        
        弹出顶点3，将与顶点3相邻的顶点4和顶点5压入堆栈
        
        <table> 
         <thead> 
          <tr> 
           <th>3</th> 
           <th>4</th> 
           <th>3</th> 
           <th>4</th> 
           <th></th> 
          </tr> 
         </thead> 
         <tbody></tbody> 
        </table>
        
        弹出顶点4，将与顶点4相邻且未被访问过的顶点5压入堆栈
        
        <table> 
         <thead> 
          <tr> 
           <th>4</th> 
           <th>3</th> 
           <th>3</th> 
           <th>4</th> 
           <th></th> 
          </tr> 
         </thead> 
         <tbody></tbody> 
        </table>
        
        弹出顶点5，将与顶点5相邻且未被访问过的顶点5压入堆栈
        
        <table> 
         <thead> 
          <tr> 
           <th>3</th> 
           <th>4</th> 
           <th>2</th> 
           <th>4</th> 
           <th></th> 
          </tr> 
         </thead> 
         <tbody></tbody> 
        </table>
        
        将堆栈中的值弹出并判断是否已经遍历过了，直到堆栈中无节点可遍历为止
        
        <table> 
         <thead> 
          <tr> 
           <th></th> 
           <th></th> 
           <th></th> 
           <th></th> 
           <th></th> 
          </tr> 
         </thead> 
         <tbody></tbody> 
        </table>
        
        所以，广度优先的遍历顺序为：顶点1，顶点2，顶点5，顶点3，顶点4
        
        广度优先遍历的python算法：
        
            def bfs(current):
                global front
                global near
                global Head
                global run
                enqueue(current)        #将第一个顶点存入队列
                run[current] = 1        #将遍历
            print('[%d]'%current,end='')
            while front != rear:
                current = dequeue()     #将顶点从队列中取出
                tempnode = Head[current].first      #先记录当前顶点的位置
                while tempnode != None:
                    if run[tempnode.x] == 0:
                        enqueue(tempnode.x)
                        run[tempnode.x] = 1     #记录已遍历过
                        print('[%d]'%tempnode.x,end='')
                    tempnode = tempnode.next
4.  #### **生成树** ####
    
    生成树又称“花费树”“成本树”或者“值树”，一个图的生成树就是以最少的边来连通图中所有的顶点，且不造成回路的属性结构。更清楚的说，当一个图连通时，使用深度优先遍历(DFS)或广度优先遍历(BFS)必能访问图中所有的顶点，且G=(V,E)的所有边可以分为两个集合：T和B（T为搜索时经过的所有边，而B为其余未被经过的边）。if S = (V,T)为G中的生成树，具有以下3项性质：
    
    1.  E = T + B
    2.  如果加入B中的任一边到S中，就会产生回路
    3.  V中的任何2个顶点Vi、Vj在S中存在唯一的一条简单路径
    4.  **DFS生成树和BFS生成树**
        
        一棵生成树也可以利用深度优先搜索法（DFS）与广度优先搜索法（BFS）来产生，所得到的生成树则称为深度优先生成树或广度优先生成树
        
        比如一个12345节点的图，可以有不止一棵生成树，深度优先生成树就是1、2、3、4、5，广度优先生成树就是1，2，5，3，4
    5.  **最小生成树**
        
        假设为树的边上加一个权重值，这种图就成为“加权图”，如果这个权重值代表两个顶点间的距离或成本，这类图就称为网络
        
        假如想知道从某个点到另一个点的路径成本，例如从顶点1到顶点5有（1+2+3）、（1+6+4）、5这三条路径成本，而“最小生成树”则是路径成本为5的生成树
    6.  **Kruskal算法**
        
        Kruskal算法时将各边按权值大小从小到大排列，接着从权重最低的边开始建立最小成本生成树，如果加入的边会造成回路，就舍弃不用，直到加入n-1个边为止
        
        比如有A、B、C、D、E、F六个顶点，看看如何实现以K氏法最小成本生成树
        
        1.  步骤1：把所有的边的成本列出并按照从小到大排序
            
            <table> 
             <thead> 
              <tr> 
               <th>起始顶点</th> 
               <th>终止顶点</th> 
               <th>成本</th> 
              </tr> 
             </thead> 
             <tbody> 
              <tr> 
               <td>B</td> 
               <td>C</td> 
               <td>3</td> 
              </tr> 
              <tr> 
               <td>B</td> 
               <td>D</td> 
               <td>5</td> 
              </tr> 
              <tr> 
               <td>A</td> 
               <td>B</td> 
               <td>6</td> 
              </tr> 
              <tr> 
               <td>C</td> 
               <td>D</td> 
               <td>7</td> 
              </tr> 
              <tr> 
               <td>B</td> 
               <td>F</td> 
               <td>8</td> 
              </tr> 
              <tr> 
               <td>D</td> 
               <td>E</td> 
               <td>9</td> 
              </tr> 
              <tr> 
               <td>A</td> 
               <td>E</td> 
               <td>10</td> 
              </tr> 
              <tr> 
               <td>D</td> 
               <td>F</td> 
               <td>11</td> 
              </tr> 
              <tr> 
               <td>A</td> 
               <td>F</td> 
               <td>12</td> 
              </tr> 
              <tr> 
               <td>E</td> 
               <td>F</td> 
               <td>16</td> 
              </tr> 
             </tbody> 
            </table>
        2.  步骤2：选择成本最低的一条边作为建立最小成本生成树的起点
        3.  步骤3：按步骤1建立的表格，按序加入边
        4.  C-D会形成回路，所以直接跳过
        
        python实现Kruskal算法：
        
            VERTS = 6   #顶点数
            class edge():
                def __init__(self):
                    self.start = 0
                    self.to = 0
                    self.find = 0
                    self.val = 0
                    self.next = None
            
            v = [0] * (VERTS+1)
            
            def findmincost(head):      #搜索成本最小的边
                minval = 100
                ptr = head
                while ptr != None:
                    if ptr.val < minval and ptr.find == 0:      #假如ptr.val的值小于minval
                        minval = ptr.val        #就把ptr.val的值赋给minval
                        retptr = ptr        # 并且把ptr记录下来
                    ptr = ptr.next
                retptr.find = 1     #将retptr设置为已经找到的边
                return retptr       #返回retptr
            
            def mintree(head):      #最小成本生成树函数
                global VERTS
                result = 0
                ptr = head
                for i in range(VERTS):
                    v[i] = 0
                while ptr != None:
                    mceptr = findmincost(head)
                    v[mceptr.start] = v[mceptr.start] + 1
                    v[mceptr.to] = v[mceptr.to] + 1
                    if v[mceptr.start] > 1 and v[mceptr.to] >1:
                        v[mceptr.start] = v[mceptr.start] - 1
                        v[mceptr.to] = v[mceptr.to] - 1
                        result = 1
                    else:
                        result = 0
                    if result == 0:
                        print('起始顶点[%d] -> 终止顶点[%d] -> 路径长度[%d]' %(mceptr.start,mceptr.to,mceptr.val))
                    ptr = ptr.next
        
        例子：将一个二维数组存储在K氏法的成本表进行排序，设计一个程序来取最小成本生成树，数据如下：
        
            data = [[1,2,6],[1,6,12],[1,5,10],[2,3,3],[2,4,5],[2,6,8],[3,4,7],\
                    [4,6,11],[4,5,9],[5,6,16]]
        
            VERTS = 6   #顶点数
            class edge():
                def __init__(self):
                    self.start = 0
                    self.to = 0
                    self.find = 0
                    self.val = 0
                    self.next = None
            
            v = [0] * (VERTS+1)
            
            def findmincost(head):      #搜索成本最小的边
                minval = 100
                ptr = head
                while ptr != None:
                    if ptr.val < minval and ptr.find == 0:      #假如ptr.val的值小于minval
                        minval = ptr.val        #就把ptr.val的值赋给minval
                        retptr = ptr        # 并且把ptr记录下来
                    ptr = ptr.next
                retptr.find = 1     #将retptr设置为已经找到的边
                return retptr       #返回retptr
            
            def mintree(head):      #最小成本生成树函数
                global VERTS
                result = 0
                ptr = head
                for i in range(VERTS):
                    v[i] = 0
                while ptr != None:
                    mceptr = findmincost(head)
                    v[mceptr.start] = v[mceptr.start] + 1
                    v[mceptr.to] = v[mceptr.to] + 1
                    if v[mceptr.start] > 1 and v[mceptr.to] >1:
                        v[mceptr.start] = v[mceptr.start] - 1
                        v[mceptr.to] = v[mceptr.to] - 1
                        result = 1
                    else:
                        result = 0
                    if result == 0:
                        print('起始顶点[%d] -> 终止顶点[%d] -> 路径长度[%d]' %(mceptr.start,mceptr.to,mceptr.val))
                    ptr = ptr.next
            
            #成本表数组
            data = [[1,2,6],[1,6,12],[1,5,10],[2,3,3],[2,4,5],[2,6,8],[3,4,7],\
                    [4,6,11],[4,5,9],[5,6,16]]
            head = None
            #建立图的链表
            for i in range(10):
                for j in range(1,VERTS + 1):
                    if data[i][0] == j:
                        newnode = edge()
                        newnode.start = data[i][0]
                        newnode.to = data[i][1]
                        newnode.val = data[i][2]
                        newnode.find = 0
                        newnode.next = None
                        if head == None:
                            head = newnode
                            head.next = None
                            ptr = head
                        else:
                            ptr.next = newnode
                            ptr = ptr.next
            
            print('--------------------------------------')
            print('建立最小成本生成树')
            print('--------------------------------------')
            mintree(head)
        
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA_size_16_color_FFFFFF_t_70 4]
5.  #### **图的最短路径** ####
    
    在一个有向图G=(V,E)中，G中每一条边都有一个比例常数W(Weight)与之对应，如果想求G图中某一个顶点V0到其他顶点的最小W总和的值，这类问题就称为最短路径问题。由于交通运输工具和通信工具的便利和通信工具的便利与普及，因此两地之间发生货物运送或者信息传递时，最短路径的问题随时都可能因应需求而产生，简单地说，就是找出两个端点之间可以通行的快捷方式。
    
    最短路径问题一般讨论的方向有两种：
    
     *  单点对全部顶点
     *  所有顶点对两两之间的最短距离
    
    1.  **单点对全部顶点**
        
        一个顶点到多个顶点的最短路径通常使用Dijkstra算法求得，Dijkstra算法如下：
        
        假设S=\{Vi | Vi∈V\}，且Vi在已发现的最短路径中，其中V0∈S是起点
        
        假设w∉S，定义Dist(w)是从V0到w的最短路径，这条路径除了w外必属于S。且有一下几点特性：
        
         *  如果u是当前所找到最短路径的下一个节点，那么u必属于V-S集合中最小成本的边。
         *  若u被选中，将u加入S集合中，则会产生当前的从V0到u的最短路径，对于w∉S，DIST(w)被改变成DIST(w)<----Min\{DIST(w),DIST(u) + COST(u,w)\}
        
        从上述算法中， 我们可以推出：
        
        1.  G=(V,E)
            
            D\[k\] = A\[F,K\],其中k从1到N
            
            S = \{F\}
            
            V = \{1,2,…,N\}
            
            D为一个N维数组，用来存放某一定点到其他顶点的最短距离
            
            F表示起始顶点
            
            A\[F,I\]为顶点F到I的距离
            
            V是网络中所有边的组合
            
            E是网络中所有边的组合
            
            S也是顶点的集合，其初始值是S = \{F\}
        2.  从V-S集合中找到一个顶点x，使得D(x)的值为最小值，并把x放入S集合中
        3.  按公式计算：D\[I\] = min(D\[I\],D\[x\] + A\[x,I\]),其中(x,I)∈E用来调整D数组的值，其中I是指x的相邻各项点
        4.  重复执行步骤2，一直到V-S是空集合为止
        
        比如有0-5的六个顶点，执行上述步骤也很简单
        
        首先从顶点5开始，找到顶点5到各项顶点间最小的距离，到达不了的以∞表示
        
        1.  步骤1：D\[0\] = ∞，D\[1\] = 12,D\[2\] = ∞,D\[3\] = 20,D\[4\] = 14。在其中找出最小的顶点并加入集合S中：D\[1\]
        2.  步骤2：D\[0\] = ∞，D\[1\] = 12,D\[2\] = 18,D\[3\] = 20,D\[4\] = 14。在其中找出最小的顶点并加入集合S中：D\[4\]
        3.  步骤3：D\[0\] = 26，D\[1\] = 12,D\[2\] = 18,D\[3\] = 20,D\[4\] = 14。在其中找出最小的顶点并加入集合S中：D\[2\]
        4.  步骤4：D\[0\] = 26，D\[1\] = 12,D\[2\] = 18,D\[3\] = 20,D\[4\] = 14。在其中找出最小的顶点并加入集合S中：D\[3\]
        5.  加入在最后一个顶点即可
        
        步骤1-5的运算结果
        
        <table> 
         <thead> 
          <tr> 
           <th>步骤</th> 
           <th>S</th> 
           <th>0</th> 
           <th>1</th> 
           <th>2</th> 
           <th>3</th> 
           <th>4</th> 
           <th>5</th> 
           <th>选择</th> 
          </tr> 
         </thead> 
         <tbody> 
          <tr> 
           <td>1</td> 
           <td>5</td> 
           <td>∞</td> 
           <td>12</td> 
           <td>∞</td> 
           <td>20</td> 
           <td>14</td> 
           <td>0</td> 
           <td>1</td> 
          </tr> 
          <tr> 
           <td>2</td> 
           <td>5，1</td> 
           <td>∞</td> 
           <td>12</td> 
           <td>18</td> 
           <td>20</td> 
           <td>14</td> 
           <td>0</td> 
           <td>4</td> 
          </tr> 
          <tr> 
           <td>3</td> 
           <td>5，1，4</td> 
           <td>26</td> 
           <td>12</td> 
           <td>18</td> 
           <td>20</td> 
           <td>14</td> 
           <td>0</td> 
           <td>2</td> 
          </tr> 
          <tr> 
           <td>4</td> 
           <td>5，1，4，2</td> 
           <td>26</td> 
           <td>12</td> 
           <td>18</td> 
           <td>20</td> 
           <td>14</td> 
           <td>0</td> 
           <td>3</td> 
          </tr> 
          <tr> 
           <td>5</td> 
           <td>5，1，4，2，3</td> 
           <td>26</td> 
           <td>12</td> 
           <td>18</td> 
           <td>20</td> 
           <td>14</td> 
           <td>0</td> 
           <td>0</td> 
          </tr> 
         </tbody> 
        </table>
        
        从顶点5到其他各顶点的最短距离：
        
        从点5到顶点0：26
        
        从点5到顶点1：12
        
        从点5到顶点2：18
        
        从点5到顶点3：20
        
        从点5到顶点4：14
        
        例子：设计一个程序，以Dijkstra算法求取图中顶点1对全部图的顶点间的最短路径
        
            Path_Cost = [[1,2,29],[2,3,30],[2,4,35],[3,5,28],[3,6,87],[4,5,42],[4,6,75],[5,6,97]]
        
            SIZE = 7
            NUMBER = 6
            INFINITE = 99999    #无穷大
            
            Graph_Matrix = [[0] * SIZE for row in range(SIZE)]      #图的数组
            distance = [0]*SIZE     #路径长度数组
            
            def BuildGraph_Matrix(Path_Cost):
                for i in range(1,SIZE):
                    for j in range(1,SIZE):
                        if i == j:
                            Graph_Matrix[i][j] = 0      #对角线设为0
                        else:
                            Graph_Matrix[i][j] = INFINITE
                #存入图的边
                i = 0
                while i < SIZE:
                    Start_Point = Path_Cost[i][0]
                    End_Point = Path_Cost[i][1]
                    Graph_Matrix[Start_Point][End_Point] = Path_Cost[i][2]
                    i += 1
            
            #单点对全部顶点的最短距离
            def shortestPath(vertex1,vertex_total):
                shortest_vertex = 1     #记录最短距离的顶点
                goal = [0]*SIZE     #用来记录该顶点是否被选取
                for i in range(1,vertex_total + 1):
                    goal[i] = 0
                    distance[i] = Graph_Matrix[vertex1][i]
                goal[vertex1] = 1
                distance[vertex1] = 0
                print()
            
                for i in range(1,vertex_total):
                    shortest_distance = INFINITE
                    for j in range(1,vertex_total + 1):
                        if goal[j] == 0 and shortest_distance > distance[j]:
                            shortest_distance = distance[j]
                            shortest_vertex = j
            
                    goal[shortest_vertex] = 1
                    #计算开始顶点到各顶点的最短距离
                    for j in range(vertex_total + 1):
                        if goal[j] == 0 and distance[shortest_vertex] + Graph_Matrix[shortest_vertex][j] \
                            < distance[j]:
                            distance[j] = distance[shortest_vertex] + Graph_Matrix[shortest_vertex][j]
            
            #主程序
            global Path_Cost
            Path_Cost = [[1,2,29],[2,3,30],[2,4,35],[3,5,28],[3,6,87],[4,5,42],[4,6,75],[5,6,97]]
            BuildGraph_Matrix((Path_Cost))
            shortestPath(1,NUMBER)        #搜索最短路径
            print("-----------------------------")
            print('顶点1到各顶点最短距离的最终结果')
            print("-----------------------------")
            for j in range(1,SIZE):
                print('顶点1到各顶点%2d的最短距离=%3d'%(j,distance[j]))
            print("-----------------------------")
            print()
        
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA_size_16_color_FFFFFF_t_70 5]
    2.  **两两顶点间的最短距离**
        
        Dijkstra的方法只能求出某一点到其他点的最短距离，如果要求出图中任意两点甚至所有顶点间最短的距离，就必须使用Floyd算法
        
        Floyd算法的定义：
        
        1.  A^ k \[i\] \[j\] = min \{ A^(k-1) \[i\] \[k\] + A^(k-1) \[j\] \[k\]\},k>=1
            
            k表示经过的顶点，A^ k \[i\] \[j\]为从顶点i到j的经由k顶点的最短路径
        2.  A^ 0 \[i\] \[j\] = COST\[i\] \[j\]（即A^0等于COST）
        3.  A^0为顶点i到j间的直通距离
        4.  A^ n \[i\] \[j\] 代表i到j的最短距离，即A^n便是我们所要求出的最短路径成本矩阵
        
        例子：设计一个python程序，以Floyd算法来取两两之间的最短路径
        
            Path_Cost = [[1,2,20],[2,3,30],[2,4,25],[3,5,28],[4,5,32],[4,6,95],[5,6,67]]
        
            SIZE = 7
            NUMBER = 6
            INFINITE = 99999    #无穷大
            
            Graph_Matrix = [[0] * SIZE for row in range(SIZE)]      #图的数组
            distance = [[0]*SIZE for row in range(SIZE)]    #路径长度数组
            
            def BuildGraph_Matrix(Path_Cost):
                for i in range(1,SIZE):
                    for j in range(1,SIZE):
                        if i == j:
                            Graph_Matrix[i][j] = 0      #对角线设为0
                        else:
                            Graph_Matrix[i][j] = INFINITE
                #存入图的边
                i = 0
                while i < SIZE:
                    Start_Point = Path_Cost[i][0]
                    End_Point = Path_Cost[i][1]
                    Graph_Matrix[Start_Point][End_Point] = Path_Cost[i][2]
                    i += 1
            
            #打印出图
            def shortestPath(vertex_total):
                #初始化图的长度数组
                for i in range(1,vertex_total + 1):
                    for j in range(1,vertex_total + 1):
                        distance[i][j] = Graph_Matrix[i][j]
                        distance[j][i] = Graph_Matrix[i][j]
            
                #使用Floyd算法找出所有顶点两两之间的最短距离
                for k in range(1,vertex_total + 1):
                    for i in range(1,vertex_total + 1):
                        for j in range(1,vertex_total + 1):
                            if distance[i][k] + distance[k][j] < distance[i][j]:
                                distance[i][j] = distance[i][k] + distance[k][j]
            
            Path_Cost = [[1,2,20],[2,3,30],[2,4,25],[3,5,28],[4,5,32],[4,6,95],[5,6,67]]
            BuildGraph_Matrix(Path_Cost)
            print('-------------------------------')
            print('所有顶点两两之间的最短距离：')
            print('-------------------------------')
            shortestPath(NUMBER)        #计算所有顶点间的最短距离
            #求得两两顶点间的最短距离长度数组后，将其打印出来
            print('顶点1  顶点2 顶点3 顶点4 顶点5 顶点6')
            for i in range(1,NUMBER + 1):
                print('顶点%d' %i,end='')
                for j in range(1,NUMBER + 1):
                    print('%6d'%distance[i][j],end='')
                print('')
            print('-------------------------------')
            print()
6.  #### **AOV网络与拓扑排序** ####
    
    网络图主要用来协助规划大型项目，首先将复杂的大型项目细分成许多工作项，而每一个工作项代表网络的一个顶点，由于每一项工作可能有完成的先后顺序，有些可以同时进行，有些则不行，因此可以用网络图来表示其先后的顺序，这种以顶点来代表工作项的网络称为顶点活动网络
    
    更清楚的说，AOV网络就是在一个有向图G中，每一个顶点代表一项工作或者行为，边则代表工作之间存在的优先关系，即<Vi,Vj>表示Vi→Vj的工作，其中顶点Vi的工作必须先完成后，才能进行Vj顶点的工作，称为Vi为Vj的先行者，而Vj为Vi的后继者
    
    **拓扑排列简介**
    
    如果AOV网络中具有部分次序的关系（即有某几个顶点为先行者），拓扑顺序的功能就是将这些部分次序的关系转换为线性次序的关系。例如i是j的先行者，在线性次序中，i仍然排在j的前面，具有这种特性的线性次序就称为拓扑排序。排序的步骤：
    
    1.  步骤1：寻找图中任何一个没有先行者的顶点
    2.  步骤2：输入此顶点，并将此顶点的所有边全部删除
    3.  步骤3：重复以上两个步骤处理所有的顶点
7.  #### **AOE网络** ####
    
    AOV网络是指在有向图中的顶点表示一项工作，而边表示顶点之间先后关系。而AOE则是指事件的行动在边上的有向图
    
    其中的顶点作为各“进入边事件”的汇集点，当所有“进入边事件”的行动全部完成后，才可以开始“外出边事件”的行动。在AOE网络中会有一个源头顶点和目的顶点。从源头顶点开始计时执行各边上事件的行动，到目的顶点完成为止所需要的事件为所有事件完成的时间总花费

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210530193039734.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210530193111107.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210530193140825.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20210530193216276.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20210530193252913.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20210530193331971.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA==,size_16,color_FFFFFF,t_70