深さ優先アルゴリズムdfs

転載するhttps://blog.csdn.net/u014394715/article/details/51192293
 
 
深さ優先アルゴリズム
定義
深さ優先検索アルゴリズム(英語:Depth-First-Serch、略してDFS)は、ツリーまたは図を巡回または検索するためのアルゴリズムである.ツリーの深さに沿って、ツリーのノードを巡回して、できるだけ深い枝を検索します.ノードvのあるところは全部自分で探されました.検索はノードvを発見する側の起点ノードに遡ります.このプロセスは、ソースノードから到達可能なすべてのノードが発見されるまで進行する.まだ発見されていないノードがある場合、ソースノードとして選択し、上記のプロセスを繰り返し、プロセス全体は、すべてのノードがアクセスされるまで繰り返される.盲目的な捜索に属する.
简単にDFSの思想は一つの顶点V 0から始まり、一つの道に沿ってまっすぐ行って、もし目的解に辿り着けないと発见したら、前のノードに戻り、もう一つの道から最后まで歩く. 
 
深さと広さの比較
カラム:図を検索すると、ツリーの階層によって検索されます.
私たちは、ノードから派生した隣接ノードの平均個数がN個であると仮定して、スタート地点から検索を開始すると、キューにノードがあり、出発点を取り出した後、隣のノードを中に入れると、列にN個のノードがあり、次の階層の検索で要素を列に追加すると、ノード数がN 2に達し、考えられます.いったんNが大きな数になると、この木の層はもっと深いので、この列はメモリ空間が必要になります.
広さ優先検索

欠点:ツリーの階層が深く、サブノードの数が多い場合、メモリの消費が非常に深刻である.

利点:最短経路

を見つけることができます.

適用範囲:ノードに適用されるサブノードの数が多くなく、ツリーの階層があまり深くない場合.

深さ優先検索
利点:メモリ消費が小さく、広さ優先検索の欠点を克服する.毎回検索する過程のため、各階層は一つのノードを維持するだけです.
短所:最適解を探しにくいですが、解があることだけを探しています.
 
コード

package Test;

import java.util.Stack;

public class DFSTest {

        //       
        private char[] vertices;

        //      （    ）
        private  int[][] arcs;

        //      
        private int vexnum;

        //           
        private boolean[] visited;

        //    
        public DFSTest(int[][] arcs,char[] vertices) {
        	//     
              vexnum = arcs.length;
          	//      
              this.vertices = vertices;
              //          ,  false,          
              visited = new boolean[vexnum];
            //     （    ） 
             this.arcs = arcs;
        }

        //       
        public void visit(int i){
            System.out.print(vertices[i] + " ");
        }

        //   i           ,          ,       
        public void traverse(int i){
            //    i      
            visited[i] = true;
            //          
            visit(i);
            //         i          ,          
            for(int j=0;j s = new Stack();
            
            for(int i=0;i=0 ; j-- ){
                            	//         ，       d
                                if(arcs[curr][j]==1 && visited[j]==false){
                                    s.add(j);
                                }
                            }
                        }
                    }while(!s.isEmpty());
                }
            }
        }

        public static void main(String[] args) {
            
            char[] vertices = {'A','B','C','D','E','F','G','H','I'};
            
            int[][] arcs ={ 
            		{0,1,0,0,0,1,0,0,0}, //A         1
            		{1,0,1,0,0,0,1,0,1},  //B         1
            		{0,1,0,1,0,0,0,0,1},  //C         1
            		{0,0,1,0,1,0,1,1,1}, //D         1
            		{0,0,0,1,0,1,0,1,0},  //E         1
            		{1,0,0,0,1,0,1,0,0},  //F         1
            		{0,1,0,1,0,1,0,1,0},  //G         1
            		{0,0,0,1,1,0,1,0,0},  //H         1
            		{0,1,1,1,0,0,0,0,0},  //I         1
                };
            DFSTest g = new DFSTest(arcs,vertices);
            
           
          

            System.out.print("      （  ）：");
            g.DFSTraverse();

            System.out.println();

            System.out.print("      （   ）：");
            g.DFSTraverse2();
        }

}

 

 
 テスト結果:
深さ優先巡回(再帰):A B C D E F G＿H I  深さ優先巡回(再帰的でない):A B C D E F G＿H I