Graph 的例子包括

• City Map
• Power Distribution Network
• Water Distribution Network
• Flight Network or Airports

相關(guān)概念:

• Vertex / Vertices
• Edge
• Degree: the degree (or valency) of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice
• Directed / Undirected
• Simple Graph: graphs with no parallel edges or self-loops
• Connected: for any two vertices, there is a path between them
• Strongly Connected: A directed graph is strongly connected if for any two vertices u and v of the graph , u reaches v and v reaches u
• Forest: A forest is an undirected graph, all of whose connected components are trees; in other words, the graph consists of a disjoint union of trees. Equivalently, a forest is an undirected acyclic graph. As special cases, an empty graph, a single tree, and the discrete graph on a set of vertices (that is, the graph with these vertices that has no edges), are examples of forests.

Graph ADT:

• field variables:
  • Collection of vertices
  • Collection of edges
• numOfVertices()
• numOfEdges()
• getVertices(): return collection of vertices
• getEdges(): return collection of edges
• outDegree(Vertex v) / inDegree(Vertex v)
• add(Vertex v)
• add(Edge e, Vertex v, Vertex u)
• removeVertex(Vertex v)
• removeEdge(Edge e)

Graph 的若干總表達(dá)方式：

• Edge List
• Adjacency List:
  • getEdge(Vertex v, Vertex u): O( min ( deg(v), deg(u) ) )
• Adjacency Map
• Adjacency Matrix

public class GraphNode {
    int val;
    List<GraphNode> neighbors;

    public GraphNode(int val) {
        this.val = val;
        this.neighbors = new ArrayList<GraphNode>();
    }
}

DFS (O(2^n), O(n!)) (思想:構(gòu)建搜索樹+判斷可行性)

1. Find all possible solutions
2. Permutations / Subsets

BFS (O(m), O(n))

1. Graph traversal (每個(gè)點(diǎn)只遍歷一次)
2. Find shortest path in a simple graph

Graph BFS

HashSet<GraphNode> visited is for:

1. Avoid infinite loop in Graph circle
2. 消除冗余計(jì)算

public List<List<Integer>> bfsGraph(GraphNode root) {
    List<List<Integer>> res = new ArrayList<>();

    if (root == null) {
        return res;
    }

    Queue<GraphNode> queue = new LinkedList<>();
    Set<GraphNode> visited = new HashSet<>();
    queue.offer(root);
    visited.add(root);
    // int level = 0;

    while (!queue.isEmpty()) {
        // level++;
        ArrayList<Integer> layer = new ArrayList<>(queue.size());
        int size = queue.size();
        while (size > 0) {
            GraphNode node = queue.poll();
            layer.add(node.val);
            for (GraphNode neighbor: node.neighbors) {
                if (!visited.contains(neighbor)) {
                    queue.offer(neighbor);
                    visited.add(neighbor);
                }
            }
            size--;
        }
        res.add(layer);
    }

    return res;
}

comparing Binary Tree BFS traversal

public List<List<Integer>> bfsTree(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();

    if (root == null) {
        return res;
    }

    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        ArrayList<Integer> layer = new ArrayList<Integer>(queue.size());
        int size = queue.size();
        
        while(size > 0) {
            TreeNode node = queue.poll();
            layer.add(node.val);

            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }

            size--;
        }
        res.add(layer);
    }

    return res;
}

BFS 易于計(jì)算 minimum level for each node in Graph or Tree.

BFS 并不適于計(jì)算 maximum level for each GraphNode. 可能需要 max level 運(yùn)算的題目: Topological Sorting. 此題題解：GeeksForGeeks, 尚未細(xì)看寸潦。

Graph BFS 也不適用于判斷 Graph 中是否存在 circle，因?yàn)?visited Hash 已經(jīng)將 circle 過濾處理了咖为。DFS 應(yīng)該更適用于判斷 circle沽翔。

Graph DFS

使用 DFS 判斷 Graph 中是否存在 circle:

public boolean hasCircle(GraphNode root) {
    if (root == null) {
        false;
    }

    Set<GraphNode> visited = new HashSet<>();

    return dfsGraph(root, visited);
}

private boolean dfsGraph(GraphNode root, Set<GraphNode> visited) {
    visited.add(root);

    for (GraphNode neighbor: root.neighbors) {
        if (visited.contains(neighbor)) {
            return true;
        }
        dfsGraph(neighbor, visited);
    }

    visited.remove(root);
    return false;
}

上面的實(shí)現(xiàn)方式存在冗余計(jì)算吓歇。這里的visited Hash實(shí)際上是 path. 優(yōu)化的實(shí)現(xiàn)方法：

public boolean hasCircle(GraphNode root) {
   if (root == null) {
       false;
   }

   Set<GraphNode> path = new HashSet<>();
   Set<GraphNode> visited = new HashSet<>();

   return dfsGraph(root, path, visited);
}

private boolean dfsGraph(GraphNode root, Set<GraphNode> path, Set<GraphNode> visited) {
   visited.add(root);
   path.add(root);

   for (GraphNode neighbor: root.neighbors) {
       if (path.contains(neighbor)) {
           return true;
       }
       if (!visited.contains(neighbor)) {
           dfsGraph(neighbor, path);
       }
   }

   path.remove(root);
   return false;
}

題解中的 path: 1. add current node; 2. dfs neighbors; 3. remove current node是 BackTracking 的經(jīng)典實(shí)現(xiàn)方式。實(shí)際上 BackTracking 也正是使用 DFS 來實(shí)現(xiàn)的。

以上基本就是 Graph DFS 的實(shí)現(xiàn)方式粉寞，不同于 Tree DFS 之處：

• Graph DFS 只有 preorder 和 postorder 形式昌执，inorder 并沒有多大意義烛亦。
• Graph DFS 同 Graph BFS一樣，可以使用 visited Hash來消除冗余計(jì)算懂拾，防止 circle 死循環(huán)煤禽。
• 如果涉及到 GraphNode depth，visited Hash是不可以使用的岖赋，因?yàn)樾枰闅v所有path檬果，不同的path 對(duì)同一個(gè) GraphNode depth 產(chǎn)生不一樣的值。這種情況唐断，可以使用 path Hash來防止死循環(huán)选脊。

Problems Solved with Graph DFS

1) For an unweighted graph, DFS traversal of the graph produces the minimum spanning tree and all pair shortest path tree.

2) Detecting cycle in a graph
A graph has cycle if and only if we see a back edge during DFS. So we can run DFS for the graph and check for back edges.

3) Path Finding
We can specialize the DFS algorithm to find a path between two given vertices.

4) Topological Sorting
Topological Sorting is mainly used for scheduling jobs from the given dependencies among jobs. In computer science, applications of this type arise in instruction scheduling, ordering of formula cell evaluation when recomputing formula values in spreadsheets, logic synthesis, determining the order of compilation tasks to perform in makefiles, data serialization, and resolving symbol dependencies in linkers.

5) To test if a graph is bipartite
We can augment either BFS or DFS when we first discover a new vertex, color it opposited its parents, and for each other edge, check it doesn’t link two vertices of the same color. The first vertex in any connected component can be red or black! See this for details.

6) Finding Strongly Connected Components of a graph A directed graph is called strongly connected if there is a path from each vertex in the graph to every other vertex. (See this for DFS based algo for finding Strongly Connected Components)

7) Solving puzzles with only one solution, such as mazes. (DFS can be adapted to find all solutions to a maze by only including nodes on the current path in the visited set.)