DFS深度优先遍历

基于之前的邻接表AdjGraph实现
- startVertex传入递归调用，统一作为v处理
  - 如果v已经被访问过，则达深度终止，直接返回
  - 否则，标记为访问过，并执行记录，然后对所有邻居依次递归

const depthFirstVisit = (v, adjList, visited, res) => {
    if (visited[v] === 1) return;
    visited[v] = 1;
    res.push(v);
    for (const neighbor of adjList.get(v)) {
        depthFirstVisit(neighbor, adjList, visited, res);
    }
}

const depthFirstSearch = (graph, startVertex) => {
    const vertices = graph.getVertices();
    const adjList = graph.getAdjList();

    const res = [];
    const visited = {};

    depthFirstVisit(startVertex, adjList, visited, res);

    return res;
}

(() => {
    const graph = new AdjGraph();
    initGraph(graph);
    console.log(graph.toString());
    console.log(depthFirstSearch(graph, "A"));
    console.log(depthFirstSearch(graph, "D"));
})()

Keyboard shortcuts

DFS深度优先遍历