深さ優先検索を変更する

（送信元、送信先）、そのタイプ（ツリー、バック、フォワード、クロス）ですか？深さ優先検索を変更する

2017-11-05 user3460123

あなたが試したことがある場合は、まずあなたのコードを入れて試してみてください –

どこから来たのかを覚えています。あなたの質問にDepth First Searchのコードを追加してください。そこから取得します。 –

あなたの編集した質問はオリジナルよりも理解しづらいものです。あなたがしようとしていることを言葉で説明してください。また、コードを変更する方法を尋ねる場合は、変更しようとしているコードを表示してください。 –

良い質問。

これはthe source you posted as commentに基づく解決策です。重要：開始/終了テーブルに誤りがあり、第三の行3列目は "[U] <端を終了[V]" でなければならない代わりに "終了[U]>終わり[V]"

void main(G, s){ 
     for each node v in G{ 
      explored[v]=false 
      parent[v]=null 
      start[v]=end[v]=null 
     } 
     Global clock = 0 
     DFS(G, s, s) 
    } 

    void DFS(G, s, parent){ 
     explored[s] = true; 
     parent[s] = parent 

     start[s]=clock 
     clock++ 

     for each u=(s,v){ 
      if(explored[v] == false){ 
       DFS(G, v) 
      } 
      print (s + "-->" + v +"type: " + getType(s,v)) 
     } 

     end[s]=clock 
     clock++ 
    } 

    String getType(s, v){ 
     if(start[s]<start[v]){ 
      if(end[s]>end[v]) return "Tree edge" 
      else return "Forward edge" 
     else{ 
      if(end[s]<end[v]) return "Back edge" 
      else return "Cross edge" 
     } 
    }

出典

2017-11-05 10:11:19

これは正しいように見えます。しかし、重要な部分は、O（1）で 'isOneOfParents'（先祖は私が推測する）を実装できることです。各頂点に入力時刻と終了時刻を格納することは可能です（http://www.cs.yale.edu/homes/aspnes/pinewiki/DepthFirstSearch.html）。 – Gassa

私はisOneOfParents（はい、祖先）について考えた最初の実装はO（ツリーの最大深さ）でした。あなたのソースを使って私はそれをO（1）にしようとします –

Ok。 [あなたのソース]（http://www.cs.yale.edu/homes/aspnes/pinewiki/DepthFirstSearch.html）に感謝します。私はタイマーの使用に気が付きませんでした。私はそれを追加する答えを編集しています。 –

ここに行きます。コードJavaの

import java.util.ArrayList; 
import java.util.List; 

class Node { 
    public String name; 
    public List<Node> connections = new ArrayList<>(); 
    boolean visited = false; 

    Node(String name) { 
     this.name = name; 
    } 
} 

class DFS { 
    // Main part. 
    public static void search(Node root) { 
     if (root == null) { 
      return; 
     } 
     root.visited = true; 
     for (Node node : root.connections) { 
      if (!node.visited) { 
       // Print result. 
       System.out.println(root.name + "->" + node.name); 
       search(node); 
      } 
     } 
    } 
} 

public class App { 

    public static void main(String[] args) { 
     Node a = new Node("a"); 
     Node b = new Node("b"); 
     Node c = new Node("c"); 
     Node d = new Node("d"); 
     Node e = new Node("e"); 

     a.connections.add(b); 

     b.connections.add(a); 
     b.connections.add(c); 
     b.connections.add(d); 

     c.connections.add(b); 
     c.connections.add(d); 

     d.connections.add(b); 
     d.connections.add(c); 
     d.connections.add(e); 

     DFS.search(d); 
    } 
}

出典

2017-11-05 10:18:32

深さ優先検索を変更する

答えて

関連する問題