数据结构-图形结构-图的数据表示

深碍√TFBOYSˉ_ 2023-10-04 14:54 57阅读 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>

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210530192208315.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/20210530192301620.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/20210530192333312.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA==,size_16,color_FFFFFF,t_70