summary of graph algorithms

goodrich-15-wiley-data structures & algorithms in java
ch14.1 Graphs

‧圖(graph)由頂點(vertex)及邊(edge)組成。
‧頂點又稱節點(node)，邊又稱弧(arc)。
‧依邊有方向與否分成有向邊(directed edge)及無向邊(undirected edge)。
‧圖若純由有向邊組成，稱為有向圖(directed graph, digraph)。
‧圖若純由無向邊組成，稱為無向圖(undirected graph)。
‧混合圖(mixed graph)的邊包含有向邊及無向邊。
‧每個邊有兩個端頂點(end vertices)或稱端點(endpoints)。
‧有向邊的端點又分成起點(origin)及終點(destination)。

‧若兩頂點為某邊的兩端點，稱兩頂點相鄰(adjacent)。
‧若頂點為邊的端點，稱邊接於(incident to)頂點。
‧頂點的去向邊(outgoing edge)包含所有以頂點為起點的有向邊。
‧頂點的來向邊(incoming edge)包含所有以頂點為終點的有向邊。
‧頂點的邊數(degree)為接於頂點的所有邊個數，
        可細分成去向邊數(out-degree)及來向邊數(in-degree)。

‧存放圖的邊容器為收藏容器(collection)，而非集合(set)，
  表示兩頂點可以有兩個以上的有向或無向邊相接，
  稱為平行邊(parallel edges)或多重邊(multiple edges)。
‧若有向/無向邊的兩端點相同，稱邊為自我迴圈。
‧若圖不包含平行邊或自我迴圈，稱圖為簡單圖(simple graph)，
  簡單圖可用不允許重複的邊集合描述。

‧路徑(path)由一連串的頂點及邊交替組成，起源於某頂點，終止於某頂點，
  串列中每個邊的起點為其前一個頂點，終點為其下一個頂點。
‧迴圈(cycle)為一路徑，其起點及終點為同一頂點，且至少有一個邊。
‧若路徑的每個頂點皆不同，稱為簡單路徑(simple path)。
‧若迴圈的每個頂點皆不同，起終兩頂點相同不算，稱為簡單迴圈(simple cycle)。
‧有向路徑(directed path)的每個邊皆為有向邊。
‧有向迴圈(directed cycle)的每個邊皆為有向邊。
‧無迴圈的有向圖(acyclic directed graph)不存在有向迴圈。

‧若存在頂點u到頂點v的路徑，稱u可到達v，或v可由u到達(reachable)。
‧無向圖的可到達性(reachability)具對稱性，即u可到達v等同v可達u，有向圖則否。
‧若圖的任兩頂點存在路徑相連，稱為連通圖(connected graph)。
‧若有向圖的任兩頂點存在雙向路徑相連，稱為強連通圖(strongly connected graph)。

‧圖G的子圖(subgraph)為一圖H，其頂點及邊分別為G的頂點及邊的子集合。
‧圖G的生成子圖(spanning subgraph)為G的子圖，包含G的所有頂點。
‧若圖G不連通，其最大連通子圖稱為G的連通組件(connected components)。
‧沒有迴圈的圖稱為森林(forest)。
‧樹(tree)為一連通森林，即沒有迴圈的連通圖。
‧圖的生成樹(spanning tree)為圖的生成子圖，本身也是樹。



ch14.2 Data Structures for Graphs

‧四種表現圖的資料結構
1.邊清單(edge list)
2.相鄰清單(adjacency list)
3.相鄰映射(adjacency map)    <== 課本採用,可由點找邊,及邊找點
        圖有頂點鏈結清單vertices，邊鏈結清單edges，及有向狀態isDirected
        頂點記錄元素element，所處頂點鏈結清單位置pos，
                去向邊的<頂點,邊>映射表outgoing，
                來向邊的<頂點,邊>映射表incoming，
                註:有向圖outgoing及incoming才不同，無向圖兩者一樣
        邊記錄元素element，所處邊鏈結清單位置pos，及兩端頂點endpoints
4.相鄰矩陣(adjacency matrix)



14.3 Graph Traversals

‧圖走訪(graph traversal)基本上在作圖轉樹的工作，
  可產生走訪樹(search tree)，回答有關頂點間可到達性問題。
  其困難點在如何有效率的檢視圖的所有頂點及邊，
  最好花費的時間能和頂點數及邊數成線性正比。

‧無向圖的可到達性問題:
         1.給定圖形G頂點u,v,若到得了,找出u到v的任一條路徑
         2.給定圖形G頂點u,若到得了,找出u到每個頂點v的路徑,路徑的邊數需最少
         3.給定圖形G,判定所有頂點是否相連
         4.給定圖形G,若存在,找出G的任一迴圈
        *5.給定連通圖形G,找出任一G的生成樹
        *6.給定圖形G,找出所有連通組件(最大相連子圖).

        註: 無向圖走訪樹的邊分類:
            樹幹邊(tree edge): 尋獲邊(discovery edge)
            非樹幹邊(nontree edge): 後退邊(back edge), 跨越邊(cross edge)

‧有向圖的可到達性問題
         1.給定圖形G頂點u,v,若到得了,找出u到v的任一條有向路徑
         2.給定圖形G頂點u,列出所有u可到達頂點
         3.給定圖形G,判定G是否強相連
         4.給定圖形G,判定有無迴圈

        註: 有向圖走訪樹的邊分類:
            樹幹邊: 尋獲邊
            非樹幹邊: 後退邊, 前進邊(forward edge), 跨越邊

‧兩種最基本的圖走訪法:
        1.深度優先走訪(depth-first search)
        2.寬度優先走訪(breadth-first search)

       GraphAlgorithms.DFS(g, u, known, forest)
                從圖 g 的頂點 u 出發,建立深度優先走訪樹,
                回傳走訪頂點 known,走訪頂點的尋獲邊 forest

       GraphAlgorithms.DFSComplete(g)
                回傳圖 g 的深度優先走訪森林,其走訪頂點的尋獲邊 forest

       GraphAlgorithms.BFS(g, u, known, forest)
                從圖 g 的頂點 u 出發,建立寬度優先走訪樹,
                回傳走訪頂點 known,走訪頂點的尋獲邊 forest

       GraphAlgorithms.BFSComplete(g)
                回傳圖 g 的深度優先走訪森林,其走訪頂點的尋獲邊 forest

       GraphAlgorithms.constructPath(g, u, v, forest)
                從圖 g 的走訪樹森林 forest
                回傳頂點 u 到 v 的路徑 (由路徑沿途的邊組成)