Help us understand the problem. What is going on with this article?

Neo4jでグラフアルゴリズム:深さ優先探索

この記事について

Neo4jを使ったグラフアルゴリズムの実装を紹介してみようという計画「グラフアルゴリズム入門 - javaとNeo4jで学ぶ -」の一部です(どこまで続くか・・・)

サンプルコードはこちらにおいた。

深さ優先探索

グラフの探索と幅優先探索については、こちら。次に深さ優先探索のサンプルプログラムを示す。これは、Neo4jのプロシージャとして書かれている。プロシージャの作り方については、この記事に解説した。入力としてはノードのidをもらい、出力には、到達したノードと、そのノードに至るパスを入れている。到達したノードは探索で訪れた順番ですべて出力される。パスを得る関数と出力のクラスについては幅優先探索の記事にある。

深さ優先探索には、スタックを使うとシンプルに書くことができる。下のプログラムは、幅優先探索でキューを使ったところをスタックに書き換えただけである。Javaのスタックは、ArrayDequeクラスを使えば良い。これはキューにもスタックにも使える双方向に出し入れできる配列である。

深さ優先探索のサンプル
    // sample6_2: DFS
    @Procedure(value = "example.sample6_2")
    @Description("sample6_2: DFS")
    public Stream<Output> sample6_2( @Name("id") Long id )
    {
        // start node
        Node start_nd = db.getNodeById(id);
        // map for keeping Node id and parent relationship
        Map<Node, Relationship> parent = new HashMap<>();
        // to avoid coming back to start node
        parent.put(start_nd, null);
        // array for checking whether the node was visited 
        List<Node> visited = new ArrayList<>(); 
        // queue
        Deque<Node> queue = new ArrayDeque<>();
        // current node
        Node c_nd = start_nd;
        // list for result
        List<Output> o_l = new ArrayList<>();
        // end if queue is empty
        while(c_nd != null) {
            Iterable<Relationship> rels = c_nd.getRelationships();
            if(!(visited.contains(c_nd))) {
                for(Relationship rel: rels){
                    // if not visited add next node
                    Node n_nd = rel.getOtherNode(c_nd);
                    if(!parent.containsKey(n_nd)) {
                        queue.push(n_nd);
                        parent.put(n_nd, rel);
                    }
                }           
                visited.add(c_nd);
            }
            Output o = new Output();
            o.node = c_nd;
            // get path from start_nd to c_nd
            o.path = getPath(start_nd, c_nd, parent);
            o_l.add(o);
            // get next node from queue
            c_nd = queue.poll();
        }
        return o_l.stream();
    }

幅優先探索のときと同じサンプルでこのプログラムを実行してみよう。以下のサンプルである。
スクリーンショット 2019-09-14 21.16.44.png
A(idが0)からスタートした実行結果は、
スクリーンショット 2019-09-14 21.17.27.png
となる。確かに深さ優先でノードが得られている。この結果を表すツリー(木)は、幅優先のときと同様に深さ優先探索木と呼ばれるものである(この表示を得るためには、Neo4j BrowserのオプションをOFFにする必要がある。説明は幅優先の記事を参照)。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした