数据结构-图形结构-图的遍历

朱雀 2023-10-04 14:56 8阅读 0赞

1.  #### **图的遍历** ####
    
    树的遍历目的是访问树的每一个节点一次，可用的方法有中序法、前序法、后序法三种。至于图的遍历，可以定义如下：
    
    一个图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]
    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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210530192541461.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA==,size_16,color_FFFFFF,t_70