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

Question

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

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

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

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

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

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

Answer 1

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

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

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

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

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"));