圖形演算法(graph algorithms)

Graph比Tree更加廣義,其定義僅僅使用了集合(Set),並且不限制結構裡的node/vertex只能有唯一的parent field,因此,更多的問題能夠以Graph建立模型。 以Graph建立之模型能夠保持資料之間的「關係」,使得各種巧妙的演算法能夠在Graph中完成各種任務。

實際案例

以遊戲常見的天賦樹來說,如果僅以Excel方式記錄有哪些天賦是不夠的,因為其天賦之間是有優先順序的,因此,每種天賦樹都可以劃成一顆樹狀結構來表示。

名詞解釋

  • vertex:稱每一個「資料節點」為vertex(或是node),並定義所有的vertex所形成之集合(Set)為VV或V(G)V(G)
  • edge:稱每一個「線段(箭號)」為edge(實際上是用一對vertex表示edge,例如(Vi,Vj)(Vi,Vj)即為連結Vi與Vj的edge),並定義所有的edge所形成之集合(Set)為EE或E(G)E(G);
  • Graph定義為VV與EE所形成的集合,表示成G(V,E)G(V,E)

分類

可以據 edge是否有方向性,再將Graph分為: directed graph(有向圖)與undirected graph(無向圖)。

  • directed graph(有向圖):edge的方向性表示資料間的關係,若vertex(A)與vertex(B)之關係是「單向的」,那麼連結vertex(A)與vertex(B)的edge即具有方向性。 如:天賦樹
  • undirected graph(無向圖):edge的方向性表示資料間的關係,若vertex(A)與vertex(B)的關係是「雙向的」,那麼連結vertex(A)與vertex(B)之edge就不具有方向性。 如:路徑規劃,可以由A到B,同理也可以由B到A。

表示法

Adjacency Matrix(相鄰矩陣):一個二維矩陣,若從vertex(A)到vertex(B)有edge,則矩陣位置[A][B]值為11,反之,則為00。

Adjacency List(相鄰串列):先以一個一維陣列列出所有的vertex,再以Linked list表示所有與vertex相連的vertex。(vertex接進Linked list的順序不重要,因為是Graph是定義成Set。)

參考資料