断开连接的图形上的 DFS

Question

对于断开连接的图，DFS(G,v) 的行为如何？

假设一个图有 3 个连通分量，并且 DFS 应用于这 3 个连通分量之一，那么我们是访问每个分量还是只访问应用 DFS 的顶点。

意思是

这样说对吗

DFS on a graph having many components covers only 1 component.

我也尝试过在线 DFS 可视化工具来处理断开连接的图形，它们也支持只覆盖 1 个组件。但我还是想确认一下

Answer 1

在断开连接的图形的单个组件上开始搜索将仅搜索该组件；否则怎么可能呢？没有信息可以决定何时、如何或在何处将搜索移动到不同的组件。

如果您想对断开连接的图执行完整搜索，您有两个高级选项：

启动对每个组件的单独搜索，然后添加一些逻辑以在多个结果中做出选择（如有必要）。这具有用于运行并行搜索的简单分区逻辑的优点。
添加逻辑以指示如何将组件组合成 "single" 图形。两个想法：
- 添加一个虚拟根节点，并将组件作为其子节点。对于只涵盖一个组件但您想同时使用所有三个组件的工具，这将是一个巧妙的解决方法。这也意味着，如果您正在搜索单个最佳结果，则可以保证您获得全局最佳结果而无需任何额外检查。
- 将您的组件放在一个列表中，并添加在当前搜索完成时跳转到下一个组件的逻辑。如有必要，添加额外的逻辑来比较多个潜在的搜索结果。

请注意，同样的推理也适用于广度优先搜索。

Answer 2

我想出了一种 DFS 可以搜索图中断开连接的部分的方法，我不知道这是否是最好的，但下面是。

    function Node(id, val){
        this.id = id;
        this.val = val;
        this.nodeChildren = {};
    }
    Node.prototype.addAssociation = function(node){
        this.nodeChildren[node.val] = node;
    }

    function Graph(){
        this.nodes = [];
        this.countNodes = 0;
    }
    Graph.prototype.addNode = function(val){
        var n = new Node(this.countNodes, val);
        this.nodes.push(n);
        this.countNodes++;
        return n;
    }

    Graph.prototype.search = function(val){
        var nodeIndex = 0;
        var visited = {}; //Hashmap
        var found = null;

        //Loop within the nodes and check if we didn't found a result yet
        while(nodeIndex < this.nodes.length && found ==null ){

            if(nodeIndex == this.nodes.length) return null;
            var currentNode = this.nodes[nodeIndex];
            nodeIndex++;

            console.log("searching from", currentNode.val, visited);
            found = this.searchDFS(val, visited, currentNode);
        }
        return  found;
    }
    Graph.prototype.searchDFS = function(val, visited, currentNode){

        //Node already visited skip
        if(visited[currentNode.id] ==1 ) {
            console.log("already visited, skipping");
            return null; 
        }

        //Found the node return it
        if(currentNode.val == val){
            return currentNode;
        } 

        visited[currentNode.id] = 1;

        var keys = Object.keys(currentNode.nodeChildren);
        for(var i=0; i<keys.length; i++){
            var childNode = currentNode.nodeChildren[keys[i]];
            if(visited != 1){
                return this.searchDFS(val, visited, childNode);
            }
        }
    }


    var g = new Graph();
    var n1 = g.addNode("a");
    var n2 = g.addNode("b");
    var n3 = g.addNode("c");
    g.addNode("c1").addAssociation(n3);
    g.addNode("c2").addAssociation(n2);
    var n4 = g.addNode("d");
    var n5 = g.addNode("e");
    n1.addAssociation(n2);
    n1.addAssociation(n3);
    n2.addAssociation(n3);
    n3.addAssociation(n4);

    console.log("found", g.search("e"));

断开连接的图形上的 DFS

DFS on disconnected Graphs

algorithm

graph

depth-first-search

graph-algorithm