数据结构与算法-图的深度优先遍历【十六】

古城微笑少年丶 2022-11-27 12:21 151阅读 0赞

对于图的遍历，也分为[深度优先遍历][Link 1]与广度优先遍历。

深度优先遍历：找到它的邻接点，然后选择一条路走到黑，直到遇到已经遍历过的节点，那么回退，不然一直往下面走。

还是以之前的这个邻接矩阵为例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E1NTM0Nzg5_size_16_color_FFFFFF_t_70_pic_center]

以这个邻接矩阵为例：

图的定义：

function Graph(vexs = [], arcs = []) { 
          this.vexs = vexs
          this.arcs = arcs
      }

vexs 存储了4个顶点：

const vexs= [ 'A', 'B', 'C', 'D']

arcs是一个二维数组，长这样：

const arcs=
       [
         [0, 1, 1, 0],
         [1, 0, 1, 1],
         [1, 1, 0, 1],
         [0, 1, 1, 0]
       ]

初始化这个图：

var graph = new Graph(vexs, arcs);

深度优先遍历

需要一个辅助的数组 或者 map来记录这个节点是否被访问过。

/** graph 图 v 第v个节点 */
    // 辅助数组
    let visited = []
    function dfs(graph, v = 0) { 
    	
    	// 从节点A开始
    	console.log(`当前访问的是第${ v}个节点：`, graph.vexs[v])
    	visited[v] = true
        // 相当于按照行遍历这个矩阵
    	for (let i = 0; i < graph.vexs.length; i++) { 
    	    if (graph.arcs[v][i]!==0 && visited[i]!==true) { 
    	    	dfs(graph, i)
    	    }
    	}
    
    }

时间复杂度分析:

用`邻接矩阵`来表示图：  
如果n个顶点，实际上是遍历了整个矩阵，所以时间复杂度是`O(n^2)`

用`邻接表`来表示图：  
如果n个顶点，2e条边（表节点），但是可以改良为邻接多重表/十字链表，实际上遍历e个节点，也能完成，所以时间复杂度是`O(n+e)`

结论：

`稠密图`更适合在`邻接矩阵`上进行深度遍历。  
`稀疏图`更适合在`邻接表`上进行深度遍历。

[Link 1]: https://zh.wikipedia.org/wiki/%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2%E6%B3%95
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E1NTM0Nzg5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/edc9c04738344cc59cead106bf39dcd9.png