図の検索——BFSとDFS

図は1種の重要なデータ構造で、多くの図のアルゴリズムは最初から検索を通じて図の構造あるいは図の中のノードが保存した情報を取得して、図の検索技術は図の関連アルゴリズムの核心です.
図の探索アルゴリズムには、BFS(breadth first search)とDFS(depth first search)の2つの設計コアがあり、広さ優先探索と深さ優先探索を表す.
1.BFS探索アルゴリズム広さ優先アルゴリズムとは、図Gのエッジをノード単位で系統的に探索してソースノードから到達可能な他のすべてのノードを発見するものであり、広さ優先アルゴリズムの特徴は、探索位置が1つのポイントに到達するごとに、そのポイントを接続する他のすべてのポイントを1つずつ探索し続けるエッジ(前のポイントからこのポイントに到達するエッジを除く)であり、全体的に図の1つのソース点から,ある方向に上層層が進む探索方式である.BFSアルゴリズムの設計コアはキューというデータ構造の利用であり,我々がキューに格納しているのは検索順序であり,キューヘッダは現在の検索位置があるノードである.

class Solution {
        public void search(List<List<Integer>>map) {
            /*
            *       map   ，           ，         
            *         。
            
            *   BFS      。
            
            * searchPos            （      ），
            * false      ，true      。
            */
            Queue<Integer>BFS=new LinkedList<>();
            boolean[]searchPos=new boolean[map.size()];
           
            for(int i=0;i<map.size();i++){
                // BFS        
               if(searchPos[i]==false) {
                   BFS.add(i);
                   searchPos[i]=true;
               }
               //     ，       
               while(!BFS.isEmpty()){
                   int thisPos=BFS.poll();
                   //                     ，   ，      
                   for(int k=0;k<map.get(thisPos).size();k++){
                       if(searchPos[map.get(thisPos).get(k)]==false){
                           BFS.add(map.get(thisPos).get(k));
                           searchPos[map.get(thisPos).get(k)]=true;
                       }
                   }
               }
           }
        }
    }

2.DFS探索アルゴリズム深さ優先アルゴリズムは、図Gのある点をソース点とし、可能であれば図中にできるだけ深く入り込み、深く入り込めなければ前のノードに戻って別の道を探し、もし道がすべて選択されたら、前のノードに戻って別の道を探し、このように行い、図中のノードがすべて探索されたことを知るまで、全体的に見ると--深く->戻って、別の道を探して->深く->戻って、別の道を探して->深く......DFSアルゴリズムの設計の核心は関数の再帰の利用に対して、再帰関数を利用して遡及の目的を達成することです.

class Solution {
        boolean[] searchPos;
        public void search(List<List<Integer>>map) {
            /*
             *       map   ，           ，         
             *         。

             * searchPos            （      ），
             * false      ，true      。
             */
            searchPos = new boolean[map.size()];
            for(int i=0;i<map.size();i++){

                //i     ，DFS   ，            
                DFS(i,map);
            }
        }
        //          
        private void DFS(int thisPos,List<List<Integer>>map){
            for(int i=0;i<map.get(thisPos).size();i++){
                if(searchPos[map.get(thisPos).get(i)]==false) {
                    DFS(map.get(thisPos).get(i), map);
                    searchPos[map.get(thisPos).get(i)]=true;
                }
            }
        }
    }

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------スタックを利用すると二叉木のDFS遍歴しか実現できないと思っていたが,スタックを利用して図のDFSを実現することも可能であり,ハッシュテーブルを支援する必要があるにすぎない.
具体的な方法:スタックは現在の検索ノードの保存を行い、1つのノードを検索するたびに、そのノードがスタックに入るが、現在の検索ノードから次のノードに向かう場合、現在のノードには2つの処理方法がある:1.現在のノードが接続されている他のノード(複数ある可能性がある)は検索が完了せず、スタックをポップアップしません.2.現在のノードが接続されている他のノードが検索され、スタックがポップアップされます.では、現在のノードが接続されている他のノードが検索済みであることをどのように判断するかは、ハッシュテーブルを利用する必要があります.具体的には、ハッシュテーブルを利用して、各ノードが検索した接続されたノード数を格納し、そのノードのすべての接続されているノード数より大きい場合は、スタックをポップアップします.そうしないと、そのノードが行検索されたときにスタックをポップアップしません.
具体的なコードはアルゴリズムの問題で示されています.テーマ:連通図のノードへの参照がなく、図の深いコピー(クローン)に戻ってください.
解題の考え方:この問題は、元の図構造の記憶空間とは異なる図構造を完全にコピーする必要があります.この図をコピーするのは、実はこの図のすべてのノードを検索し、検索中にコピーすればいいのです.

class Node {
    public int val;
    //neighbors                
    public List<Node> neighbors;

    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }

    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }

    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

//DFS     
class Solution {
    
    public Node cloneGraph(Node node) {
        /*
        * DFS:DFS        
        * Search:       （      ）
        * Val_Node:  val     
        * Node_Neighbor：       neighbors
        */
        if(node==null)
            return null;
        Stack<Node>DFS=new Stack<>();
        HashSet<Node>Search=new HashSet<>();
        HashMap<Integer,Node>Val_Node=new HashMap<>();
        HashMap<Node,Integer>Node_Neighbor=new HashMap<>();

        DFS.push(node);
        Search.add(node);
        Val_Node.put(node.val,new Node(node.val));
        Node_Neighbor.put(Val_Node.get(node.val),0);
        while(!DFS.isEmpty()){
            Node peek= DFS.peek();
            Node newNode=Val_Node.get(peek.val);
            int neighbor=Node_Neighbor.get(newNode);
            Node_Neighbor.put(newNode,neighbor+1);
            if(neighbor>= peek.neighbors.size()){
                DFS.pop();
                continue;
            }
            if(!Val_Node.containsKey(peek.neighbors.get(neighbor).val)){
                int key=peek.neighbors.get(neighbor).val;
                Val_Node.put(key,new Node(key));
                Node_Neighbor.put(Val_Node.get(key),0);
            }
            if(!Search.contains(peek.neighbors.get(neighbor))){
                Search.add(peek.neighbors.get(neighbor));
                DFS.push(peek.neighbors.get(neighbor));
            }
            newNode.neighbors.add(Val_Node.get(peek.neighbors.get(neighbor).val));
        }
        return Val_Node.get(node.val);
    }

}