這章節要來點hardcore的，就是分析graph traversal的runtime。要做到這件事分3個步驟：

1.Graph API
2.Graph implementation data structure
3.DepthFirstPaths & BreadthFirstPaths implementation

1.Graph API：

public class Graph{
    public Graph(int V); // Create empty graph with v vertices.
    public void addEdge(int v, int w); // add an edge v-w.
    Iterable<Integer> adj(int v); // vertices adjacent to v.
    int V(); // number of vertices.
    int E(); // number of edges.
}

• Number of vertices must be specified in advance.
• Does not support weights(labels) on nodes or edges.
• Has no method for getting the number of edges for a vertex (i.e. its degree).

2.Graph implementation data structure

i. adjacency matrix

ii. edge sets

iii. adjacency lists

各個implementation的runtime比較：

以print()來說，目標是印出所有的連結關係，所以code會長這樣：

void print(Graph G){
    for(v = 0; v < G.V(); v++){
        for(int w : G.adj(v)){
            System.out.println(v + "-" + w);
        }
    }
}

所以若Graph的資料結構使用adjacency matrix的話，就會是Θ(V^2)；而若使用adjacency list就會是Θ(V+E)：

由此可知adjacency list的效能比較好，這也剛好是Graph最常見的實作資料結構。

Graph implementation in adjacency lists：

3.DepthFirstPaths & BreadthFirstPaths implementation

i. DepthFirstPaths

ii. BreadthFirstPaths

Runtime of different Graph implementation：

可以看到，Graph內部的實作細節可以大幅度的影響到DFS & BFS的效能！

Slides are from Josh Hug CS61B

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License