圖是甚麼

圖在數學上可定義為 G = (V,E)
其中V是圖上所有點所成的集合
E是圖上所有邊所成的集合

並且邊可以表示為 (u,v) ，u,v屬於V

白話來說，圖是一些點與邊所構成的結構
可以說是泛化的資料結構，比如tree, linked list都是圖的子集

正因為圖很泛化，可以記錄大量資訊
比如社群網路的追蹤關係、各城市的交通流量

至於方向、degree、權重、cycle、連通圖、子圖、二分圖..概念就不在此贅述

如何記錄圖

以上圖為例:

方法1: 2D matrix (adjacent matrix)

會以2D 矩陣的方式，如果有邊可以記為1，或是其權重值
反之為0

比如 1->2 有邊 , 1->3 有邊 .. 所以對應值是1

Some Fact :

適合紀錄邊很多的圖，否則會有大量0 (稀疏矩陣)
如果是無向圖，矩陣必對稱，只需記一半即可

方法2: linked list (adjacent list)

會以點數量個linked list ，紀錄各點有指向的點

Some Fact:

適合紀錄有向、邊很少的圖
實作上，每個節點都是一個struct (或class)
因此若有權重就放在裡面一起記錄，然後箭頭用指標就可以達到
實作上，可能需要一個陣列把n個list紀錄起來

Traversal

紀錄完圖之後，常常會需要取出裡面的一條path，或是確認所有點
這時有兩個常見的做法，即BFS 與 DFS

BFS (Breadth-first search)

會優先搜尋鄰近點
以例子而言，
1 會先搜尋到 2、3
2 搜尋到3 (但3看過了)
3 搜尋到4
4 搜尋到2 (但2看過了)

通常會搭配Queue來實作，利用先進先出的特性，來紀錄下一回合該哪個點

並且我們通常會讓點多記一個visited變數，如果訪問過就打開，否則遇到有cycle的圖會無窮traversal

概念

Queue = [各子圖起點們]  
while Queue is not empty:
	center_point = Queue.Dequeue()

	for node in center_point`s neighbor:
		if node not visited:
			Queue.Enqueue(node)  
			# do something

關鍵就是如何取得center_point`s neighbor (這邊的neighbor在有向圖中就是center point 指向的點)

Matrix 版BFS

neighbor就是第center point列中 > 0 的行號

for i in range(n_vertex):
	if graph_matrix[center_point][i] > 0:
		center_point direct ith point  neighbor

list 版BFS

neighbor 就是自己list 的linked list 上的所有點

for i in range(n_vertex):
	for node in graph_list[i]:
		node and ith point is neighbor

比較

這是看出資料結構對演算法影響的時機之一

matrix版本因為要檢查整的matrix，所以最後時間複雜度是 O(V^2)

list版本則因為只需要查看每一個點連出去的邊
時間複雜度是 O(V+E)

因此通常情況下，list比較適合做traversal

DFS (Depth-first search)

會優先搜尋同一條path 以例子而言，
1 會先搜尋到 2、3、4 (如果只traversal點，則到此結束)

通常會搭配Stack來實作，利用先進後出的特性，來紀錄下一回合該哪個點

概念

Stack = [各子圖起點們]  
while Stack is not empty:
	center_point = Stack.pop()
    
    while center_point!=None && center_point is not visited:
    	#Do something 

    	Next_center_point = center_point.getOneNeighbor()
    
    	Stack.push(Next_center_point)

    	center_point = Next_center_point

類似BFS，關鍵在於center_point.getOneNeighbor()

matrix版本就是找出該列第一個非零的行號
linked list版本就是傳下一個節點

並且時間複雜度也是O(V^2) 與 O(V+E)

注意:

通常也可以用recursive來traversal (遞迴也是function stack實作，因此也有stack)
stack 與 queue , DFS 與 BFS 互相對應
DFS、BFS是很基礎的算法，以後演算法可能會以他們為基礎

Little Cube`s box

基礎graph - 圖的表示、DFS、BFS