Graph representation 隣接リストでのグラフ表現

Topic

グラフ表現の復習

※自分用のまとめノートなので、誤った認識で書かれてる可能性あり

Graph representation

今回は基本の隣接リストでのグラフ表現の実装の復習。

ちなみに、グラフ表現では大きく4種類の方法があるらしい。*1

やりたいこと

こんなグラフや、あんなグラフをコード上で表現して、BFS,DFSなどで走査（検索）したい

• 左図はソーシャルネットワーク
• 右図はページ内リンク

Adjacency lists

• array Adj of $|V|$
• each element in the array is a pointer to a linked list
• for each vertex $v \in V$, Adj[v] stores $v$'s neighbors
• ${ v \in V | (u,v) \in E }$ directed
• ${ v \in V | {u,v} \in E }$ undirected

Adjacency listの例

• $|V| = 3$
• $|E| = 4$
• Space complexity : $\Theta(|V|+|E|)$
  • Undirectedの時はEdgeが2倍だが $\Theta(|V|+|E|)$

Adjacency listの実装

• 一番単純なのはArray (ArrayList)で実装する方法。あとは Dictionary (HashTable)など
• 各要素の入れ物（隣接するノードをいれる）を何にするかも実装者による
  • ArrayList
  • ArrayStack
  • LinkedList
  • HashSet

• 今回は以下のように実装した

  • Adjacency list自体はDictionay (HashMap)
  • 各要素はSet (HashSet)

  • メリットは、同じ辺を追加してしまった時に重複してAdjacency listに登録されることがない

    java private HashMap<Integer, HashSet<Integer>> adjacencyList;

• Adjacency listのインターフェース

  • インターフェースを用意してみた
  • 実際は配列orハッシュテーブルに↑の図のように頂点を追加できればいいだけなので、object oriented likeにやる必要はない
  • 辺の追加（ addDirectedEdge addUnDirectedEdge）、指定した頂点に隣接する頂点を返す（ neighbors ）メソッドはBFS, DFSを実行する上で必要
  • 最後にデバッグ用に printGraphも定義した

public interface Graph {

    public void addDirectedEdge(int i, int j);
    public void addUnDirectedEdge(int i, int j);
    public HashSet<Integer> neighbors(int i);
    public void removeEdge(int i, int j);
    public boolean hasEdge(int i, int j);
    public List<Integer> inEdge(int i);
    
    public void printGraph();
}

• 実装クラス

  • GraphAsAdjList.java

    https://github.com/Sho372/algds/blob/main/algds-libs/src/main/java/com/sho372/algds/graph/GraphAsAdjList.java

  • 確認

    ↑の図のグラフのAdjacency listを作成

public static void main(String[] args) {

        // #1 Directed
        // Create the graph
        int V = 3;
        GraphAsAdjList graph = new GraphAsAdjList(V);

        graph.addDirectedEdge(0,2); // a -> c
        graph.addDirectedEdge(1,0); // b -> a
        graph.addDirectedEdge(1,2); // b -> c
        graph.addDirectedEdge(2,1); // c -> b

        graph.printGraph();
}

vertex 0|-> 2
vertex 1|-> 0-> 2
vertex 2|-> 1

参考にしたもの

• https://github.com/jwasham/coding-interview-university#graphs

• 13 Breadth-First Search (BFS) https://www.youtube.com/watch?v=s-CYnVz-uh4&t=2006s

• https://github.com/DCtheTall/mit6.006/blob/master/lecture13/bfs.py
• これが意外とよかった https://www.youtube.com/watch?v=zVrPdF7f4-I
• Open data structuresのリポジトリ https://github.com/spinute/ods

*1:https://github.com/jwasham/coding-interview-university#graphs のREADME.mdより