DFS на отключенных графиках

Question

Как DFS(G,v) ведет себя для несвязных графов?

Предположим, что граф имеет 3 связанных компонента, и DFS применяется к одному из этих 3 связанных компонентов, а затем мы посещаем каждый компонент или только тот, к которому применяется вершина DFS.

Значит ли это правильно сказать, что

DFS на графе, имеющем много компонентов, охватывает только 1 компонент.

Я также попробовал онлайн-инструменты визуализации DFS для отключенных графиков, и они также поддерживают, что он охватывает только 1 компонент. Но все же я хочу подтвердить

• https://www.cs.usfca.edu/~galles/visualization/DFS.html
• https://visualgo.net/dfsbfs

Answer 1

При запуске поиска по одному компоненту отключенного графа будет выполняться поиск только этого компонента; Как могло быть иначе? Там нет информации, чтобы принять решение о том, когда, как или где переместить поиск в другой компонент.

Если вы хотите выполнить полный поиск по отключенному графику, у вас есть два варианта высокого уровня:

• Ускорьте отдельный поиск по каждому компоненту, затем добавьте логику, чтобы сделать выбор из нескольких результатов (при необходимости). Это имеет преимущество простой логики разделения для параллельного выполнения поиска.
• Добавьте логику, чтобы указать, как объединить компоненты в "один" график. Две идеи для этого:
  • Добавьте фиктивный корневой узел, и компоненты должны быть его дочерними. Это был бы хороший обходной путь для инструментов, которые охватывают только один компонент, но вы хотите работать со всеми тремя одновременно. Это также означает, что если вы ищете один лучший результат, вы гарантированно получите лучший в мире без каких-либо дополнительных проверок.
  • Поместите свои компоненты в список и добавьте логику, которая переходит к следующему, когда поиск по текущему завершается. При необходимости добавьте дополнительную логику для сравнения нескольких потенциальных результатов поиска.

Обратите внимание, что те же рассуждения применимы и к поиску в ширину.

Answer 2

Я придумал способ, которым de 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"));