图（四）：图的二维矩阵的深度优先搜索和广度优先搜索

超、凢脫俗 2023-05-31 02:48 3阅读 0赞

一、深度优先搜索![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70]  
按照上面的思路我们进行深度优先搜索的代码实现：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 1]  
递归版：

'''
    深度优先遍历：dfs
    先进入图的一个节点,并标记已访问,然后选择该节点一个节点继续访问,
    直到进入的节点中所有相邻节点全被访问过,进入回溯操作,
    直到将所有节点访问结束
    '''
    matrix=[[-1,5,-1,-1,-1,2],
            [-1,-1,4,-1,-1,-1],
            [-1,-1,-1,9,-1,-1],
            [-1,-1,-1,-1,7,3],
            [1,-1,-1,-1,-1,-1],
            [-1,-1,1,-1,8,-1]]
    n=len(matrix[0])
    i=0
    def DFS_arr(matrix,i):
        visited=[]
        arr=[]
        def dfs(matrix,visited,n,arr,i=0):
            #visited=[] 记录已经访问过的节点
            #arr=[] 记录深度优先搜索的轨迹
            #print(visited)
            if i not in visited:
                visited.append(i)
                arr.append(i)
                for j in range(n): #搜索相邻节点
                    if matrix[i][j]!=-1 and j not in visited: #如果相邻节点没有被访问过,进行深度优先搜索
                        #arr.append([i])#,j,matrix[i][j]])
                        dfs(matrix,visited,n,arr,j)
            return arr
        return dfs(matrix,visited,n,arr,i=i)
    DFS_arr(matrix,i=0)
    DFS_arr(matrix,i=1)

结果：  
\[0, 1, 2, 3, 4, 5\]  
\[1, 2, 3, 4, 0, 5\]  
非递归版本：

'''
    非递归版本可以用栈来实现深度优先搜索，
    （1）利用一个数组来记录哪些顶点被访问过
    （2）利用栈这个辅助数组来实现深度优先遍历，每次向栈中加入一个元素，元素弹出后加入与这个顶点相连的所有顶点
    ，继续从中弹出一个（相当于从中选择了一个未知顶点),继续弹出直到栈为空为止，因为每一次元素弹出都要比较以下这个
        元素是否已经被访问过,所以相当于进行了回溯的操作）
    '''
    matrix=[[-1,5,-1,-1,-1,2],
            [-1,-1,4,-1,-1,-1],
            [-1,-1,-1,9,-1,-1],
            [-1,-1,-1,-1,7,3],
            [1,-1,-1,-1,-1,-1],
            [-1,-1,1,-1,8,-1]]
    def dfs_arr(matrix,i):
        n=len(matrix[0])
        visited=[]
        #i=0
        def dfs(matrix,n,i,visited):
            #n 顶点个数
            #i 最开始要遍历的顶点起始位置
            arr=[] #进行深度优先遍历
            path=[] #记录深度优先按遍历的结果
            arr.append(i)
            while arr:
                #print(arr)
                vertix=arr.pop()
                if vertix not in visited:
                    visited.append(vertix)
                    path.append(vertix)
                    set1=matrix[vertix]
                    for j in range(n-1,-1,-1):#让元素能够按照原本的逆序入栈，顺序出栈             
                        if set1[j]!=-1: #找到其相邻的顶点
                             arr.append(j)
            return path
        return dfs(matrix,n,i,visited) 
    dfs_arr(matrix,i=0)               
    dfs_arr(matrix,i=1)

\[0, 1, 2, 3, 4, 5\]  
\[1, 2, 3, 4, 0, 5\]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70]: /images/20230531/4e2ba19f632342bca0ee8d8358920f95.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 1]: /images/20230531/ea66c55674fc4a60918734ed79adbc58.png