---
title: 'Graph 圖形'
disqus: kyleAlien
---

Graph 圖形
===

## OverView of Content

如有引用參考請詳註出處，感謝 :smile:

* Graph 無法從單個節點訪問全部節點，但樹可以~

> 最常被應用在`最短路徑搜尋`、`拓樸排序`

## 簡介
* 樹狀結構是在討論 Node 之間的 ==層次== 關係，圖形是討論 Node 之間 ==連線與否==，在圖形中可在相互連線的部分加入**權重** (網路關係)

### 尤拉橋
* 圖形理論是來自，數學家**尤拉** ([Euler](https://zh.wikipedia.org/wiki/%E8%90%8A%E6%98%82%E5%93%88%E5%BE%B7%C2%B7%E6%AD%90%E6%8B%89))，為了解決`肯尼茲保橋梁` (七橋理論) 問題，7 座橫跨 4 個大都市的橋梁
> 

Euler 得出了以下結論
1. 當所有的分支度 **都是偶數** 時，才能==從原點走過每座橋，**再回原點**==，上圖每個 Node 分之度都是奇數所以不可能
> 上圖分支度
> A city: 5
> B city: 3
> C city: 3
> D city: 3
2. 如果條件改成，==經過每座橋然後**不用回原點**==，亦即**只允許其中兩個 Node 的分支度為奇數，其他 Node 必須是偶數**

### 圖形定義
* 圖形以`頂點` + `邊`組成，其表示法為，圖形名稱=(V, E)，**V 為所有頂點的集合，E 為所有邊的集合**

### 無向圖形
* 無向圖形，其 ==**表示法為 (V, E)**==，邊 (A, B) **等於** (B, A)
> 
>
> **頂點的集合**為，V = {A, B, C, D, E, F}
> **邊的集合**為，E = {(A, B), (B ,D), (C, D), (D, E), (D, F), (E, F)}

| 數語 | 解釋 |
| -------- | -------- |
| 完整圖形 | 符合 : 邊條數量 = 頂點數量(N) * (N - 1) **/ 2**，每個頂點的分支數為 N - 1 |
| 子圖 | 子圖的定義是，該子圖必定包含在主圖中 |
| 循環 | 起點與終點相同 |
| 依附 | Node 所有有關的邊，上圖 D 的依附為 (C, D), (D, F), (D, E), (B,D) |
| 分支度 | Node 的依附的數量，D 的分之度為 4 |

### 有向圖形
* 有向圖形，其 ==**表示法為 <V, E>**==，邊 (A, B) **不等於** (B, A)
> 
>
> **頂點的集合**為，V = {A, B, C, D, E}
> **邊的集合**為，E = {<A, B>, <B, D>, <B, E>, <C, B>, <D, C>, <E, D>}

| 數語 | 解釋 |
| -------- | -------- |
| 完整圖形 | 符合 : 邊條數量 = 頂點數量(N) * (N - 1)，每個頂點的分支數為 N - 1 |
| 強連結 | 相互連結， <A, B> && <B, A> |
| 強連結單元 | **每個 Node** 間都必須是強連結 |
| 出分之度 | 從 Node 發出的數量，上圖 Node D 的出分之度為 1 |
| 入分之度 | 進入 Node 的數量，上圖 Node D 的入分之度為 2 |

### 複線圖
* **==圖中任意兩點只能有一條邊==**，如果兩個 Node 之間有 >= 2 條邊，則是複線圖，**++嚴格來說複線圖並不算是圖形++**，要進行 **切割子圖**
> 複線圖，尤拉橋
> 
>
> 換成有子圖的圖形
> 

## 圖形表示法
* 在電腦中，常使用的圖形表示法有四種，`相鄰矩陣`、`相鄰串列`、`相鄰複合串列`、`索引表格法`

### 相鄰矩陣
* **圖形有 N 個 Node 就使用 N * N 個二為陣列**，並且有向圖形 & 無向圖形的特性不同

1. 對於**無向圖形**來說，**相鄰==矩陣是對稱的，並且對角線一定為 0==**(不指向自己)，**有向圖形**就 ==**不一定是對稱的**==
2. **無向圖形任意 Node i 的分支度就是二為陣列中 i `列` 的加總**
3. **有向圖形任意 Node i 的==出分支度==就是二維陣列中 i `列`的加總，==入分支度==是二維陣列中 i `行`的加總**
4. 以消耗空間來說，**無向圖形**因為對角對稱，**只需[儲存上三角 or 下三角](https://hackmd.io/T3he4PgnRnK7vTtNQwcymw#%E4%B8%89%E8%A7%92%E7%9F%A9%E9%99%A3)的資料即可**，僅需要 n(n-1) / 2 的空間

* **無向圖形**
> 
> Node.1 的分支度為，列 1 的總和，0 + 1 + 0 + 0 + 1 = 2
> Node.2 的分支度為，列 2 的總和，1 + 0 + 1 + 1 + 0 = 3
> Node.3 的分支度為，列 3 的總和，0 + 1 + 0 + 1 + 1 = 3
> 以此類推...

import java.util.LinkedList;

public class Tree_Basic {

	public static void main(String[] args) {
		NonDirect();
	}
	
	public static void NonDirect() {
		// 14's node to node
		int[][] data = {
				{1,2}, {2,1}, {1,5}, {5,1}, {2,3}, {3,2}, {2,4}, {4,2},
				{3,4}, {4,3}, {3,5}, {5,3}, {4,5}, {5,4}
		};
		
		int len = NodeCount(data);
		Msg("Len is " + len);
		
		int[][] newData = new int[len][len];
		
		for(int i = 0; i < data.length; i++) {
			int x = data[i][0];
			int y = data[i][1];
			// for each Array
			for(int j = 1; j <= len; j++) {
				for(int k = 1; k <= len; k++) {
					if(j == x && k == y) {
						newData[x - 1][y - 1] = 1;
					}
				}
			}
		}
	}
	
	private static int NodeCount(int[][] data) {
		if(data == null) return 0;
		
		LinkedList<Integer> link = new LinkedList<>();
		
		for(int i = 0;i < data.length; i++) {
			int cache = data[i][0];        // 取正方形，所以只需要比對 data[i][0] 即可以
			if(!link.contains(cache)) {
				link.push(cache);
			}
		}
		
		return link.size();
	}
	
	private static void Msg(String str) {
		if(str == null) return;
		System.out.println(str);
	}
}

**實作**
> 

* 有向圖形
> 
> Node.4 的==出分支度==，**==列== 4 的總和**，0 + 0 + 1 + 0 + 1 = 2
> Node.4 的==入分支度==，**==行== 4 的總和**，0 + 1 + 0 + 0 + 1 = 2
> 以此類推...

import java.util.LinkedList;

public class Tree_Basic {

	public static void main(String[] args) {
		
		HasDirect();
	}
	
	public static void HasDirect() {
	    int[][] data = {
	        {1,2}, {2,1}, {2,3}, {2,4}, {3,5}, {4,3}, {4,5}, {5,4}
	    };
	    
	    int len = DirNodeCount(data);
	    Msg("Len is " + len, true);
	    
	    int[][] newData = new int[len][len];
	    
	    for(int i = 0; i < data.length; i++) { // for each data array
	        int x = data[i][0];
	        int y = data[i][1];
	        for(int j = 0; j < len; j++) { // for each newData array to put data
	            for(int k = 0; k < len; k++) {
	                newData[x - 1][y - 1] = 1;
	            }
	        }
	    }
		
		printArray(len, newData);
	}
	
    //"1. "
	private static int DirNodeCount(int[][] data) {
		if(data == null) return 0;
		
		LinkedList<Integer> link = new LinkedList<>();
		
		for(int i = 0; i < data.length; i++) {
			int cache = data[i][0];
			int cache2 = data[i][1];
			if(!link.contains(cache) || !link.contains(cache)) {
				link.push(cache);
			}
		}
		
		return link.size();
	}
	
	private static void printArray(int len, int[][] newData) {
			for(int j = 0; j < len; j++) {
				for(int k = 0; k < len; k++) {
					Msg("[" + newData[j][k] + "]", false);
				}
				Msg("", true);
			}
	}
	
	private static void Msg(String str, boolean ln) {
		if(str == null) return;
		
		if(ln) {
		    System.out.println(str);
		} else {
		    System.out.print(str);
		}
	}
}

1. DirNodeCount 作用是取得所有的節點，並返回 Node 數量，與無向圖形不同的地方在
> 無向圖形 : 一定是**相互對應**所以只需取一個值
> 有向圖形 : **可能單方面指向**，所以必須兩個值都取出，Ex: <1, 5> 但 5 並沒有指向外面，會造成掃描不到 Node 5

### 相鄰串列
* 矩陣的表示法，如果過多 0 的話就形成的[稀疏矩陣](https://hackmd.io/T3he4PgnRnK7vTtNQwcymw#稀疏矩陣)，造成空間浪費
> 其缺點也是如同鏈接，搜索會較花時間

* 無邊圖形規則 : n 個 Node 就有 n 個首節點，m 個邊就有 2m 個串鏈結，所有頂點分支度的時間為 O(m+n)
> 
> 5 個綠色首節點，5 個末節點，**7個邊，14 個白色串鏈結**

import java.util.LinkedList;

public class Tree_Basic {

	public static void main(String[] args) {
	    	NoDirList();
	}
	
	private static void NoDirList() {
	    int[][] data = {
	        {1,2}, {2,1}, {1,5}, {5,1}, {2,3}, {3,2}, {2,4}, {4,2}, {3,4}, {4,3},
	        {3,5}, {5,3}, {4,5}, {5,4}
	    };
	    
	    int count = HeaderCount(data);
	    Msg("Header Count: " + count, true);
	    
	    for(int i = 0; i < count; i++) {
	        MyGraphList mList = new MyGraphList();
	        
	        for(int j = 0; j < data.length; j++) {
	            int cache = data[j][0];
	            
	            if(i == (cache - 1)) {
	                mList.push(data[j][1]);
	            }
	        }
	        Msg("Header [" + (i+1) + "]: ", false);
	        mList.printList();
	    }
	}
	
	private static int HeaderCount(int[][] data) {
	    LinkedList<Integer> list = new LinkedList<>();
	    
	    for(int i = 0; i < data.length; i++) {
	        int cache = data[i][0];
	        if(!list.contains(cache)) {
	            list.push(cache);
	        }
	    }
	    
	    return list.size();
	}
	
	private static void Msg(String str, boolean ln) {
		if(str == null) return;
		
		if(ln) {
		    System.out.println(str);
		} else {
		    System.out.print(str);
		}
	}
}

class Node {
    int value;
    Node next = null;
    
    Node(int value) {
        this.value = value;
    }
}

class MyGraphList {
    Node first, last;
    
    MyGraphList() {
    }
    
    boolean isEmpty() {
        return first == null;
    }
    
    void push(int value) {
        Node n = new Node(value);
        
        if(isEmpty()) {
            first = n;
            last = n;
            return;
        } else {
            last.next = n;
            last = n;
        }
    }
    
    void printList() {
        if(isEmpty()) {
            return;
        }
        
        Node temp = first;
        while(temp != null) {
            System.out.print("[" + temp.value + "] ");
            temp = temp.next;
        }
        System.out.println();
    }

}

**--實作--**
> 

* 有邊圖形規則 : n 個 Node 就有 n 個首節點，m 個邊就有 m 個串鏈結，所有頂點分支度的時間為 O(2n)
> 
> 5 個綠色首節點，5 個末節點，**8個邊，8 個白色串鏈結**

import java.util.LinkedList;

public class Tree_Basic {

	public static void main(String[] args) {
	    HasDirectList();
	}
	
	public static void HasDirectList() {
	    int[][] data = {
	        {1,2}, {2,1}, {2,3}, {2,4}, {3,5}, {4,3}, {4,5}, {5,4}
	    };
	    
	    int count = HeaderCount(data);
	    Msg("Header Count: " + count, true);
	    
	    for(int i = 0; i < count; i++) {
	        MyGraphList mList = new MyGraphList();
	        
	        for(int j = 0; j < data.length; j++) {
	            int cache = data[j][0];
	            
	            if(i == (cache - 1)) {
	                mList.push(data[j][1]);
	            }
	        }
	        Msg("Header [" + (i+1) + "]: ", false);
	        mList.printList();
	    }
	}
	
	private static int HeaderCount(int[][] data) {
	    LinkedList<Integer> list = new LinkedList<>();
	    
	    for(int i = 0; i < data.length; i++) {
	        int cache = data[i][0];
	        int cache2 = data[i][1];
	        if(!list.contains(cache) || !!list.contains(cache2)) {
	            list.push(cache);
	        }
	    }
	    
	    return list.size();
	}
	
	private static void Msg(String str, boolean ln) {
		if(str == null) return;
		
		if(ln) {
		    System.out.println(str);
		} else {
		    System.out.print(str);
		}
	}
}

class Node {
    int value;
    Node next = null;
    
    Node(int value) {
        this.value = value;
    }
}

class MyGraphList {
    Node first, last;
    
    MyGraphList() {
    }
    
    boolean isEmpty() {
        return first == null;
    }
    
    void push(int value) {
        Node n = new Node(value);
        
        if(isEmpty()) {
            first = n;
            last = n;
            return;
        } else {
            last.next = n;
            last = n;
        }
    }
    
    void printList() {
        if(isEmpty()) {
            return;
        }
        
        Node temp = first;
        while(temp != null) {
            System.out.print("[" + temp.value + "] ");
            temp = temp.next;
        }
        System.out.println();
    }

}

**--實作--**
> 

### 相鄰複合串列
* 特色是處理邊 ==**邊**==，不像是上方兩個方式是以**頂**的觀點出發
* 相鄰複合串列是處理**無向圖形**，使用的鏈結內容有 5 個

| Mark | V1 | V2 | Link1 | Link2 |
| -------- | -------- | -------- | -------- | -------- |
| 紀錄 Flag | 邊的**起點** | 邊的**終點** | 連結下一個==未被記錄==並與 V1 相連的點 | 連結下一個==未被記錄==並與 V2 相連的點 |

> 

### 索引表格法
* 一維陣列來表示儲存與各頂點相鄰的所有 Node

> 

## 圖形遍歷
* 圖形遍歷有分，深度優先(DSF)、廣度優先(BSF)

### Depth Search Frist (DSF)
* **使用到 `堆疊 Stack`、`遞歸` 的概念**

import java.util.LinkedList;

public class Tree_Dsf {
    //"1. "
	static DsfTreeStack[] myArray;
    //"2. "
	static boolean MarkStamp[];

	public static void main(String[] args) {
		int[][] data = {
		        {1,2}, {2,1}, {1,5}, {5,1}, {2,3}, {3,2}, {2,4}, {4,2}, 
		        {3,4}, {4,3}, {3,5}, {5,3}, {4,5}, {5,4}
		};
		/*
		int[][] data = {
				{1,2}, {2,1}, {1,3}, {3,1}, {2,4}, {4,2}, {2,5}, {5,2}, {3,6}, {6,3},
				{3,7}, {7,3}, {4,5}, {5,4}, {6,7}, {7,6}, {5,8}, {8,5}, {6,8}, {8,6}
		};
		*/
		
		int count = HeaderCount(data);
	    Msg("Header Count: " + count, true);
	    
	    myArray = new DsfTreeStack[count];
	    MarkStamp = new boolean[count];
	    
	    for(int i = 0; i < count; i++) {
	    	myArray[i] = new DsfTreeStack();
	    	
	    	for(int j = 0; j < data.length; j++) {
	            int cache = data[j][0];
	            
	    		if((cache - 1) == i) {
	    			myArray[i].push(data[j][1]);
	    		}
	    	}
	    	
	    	myArray[i].printBsf();
	    }
	    
	    Msg("深度走訪: ", true);
	    // start point is 1    "3. "
	    dfs(1);
	}
	
	private static void dfs(int current) {
		MarkStamp[current - 1] = true;
		
	    Msg("[" + current + "] ", false);
	    
	    DsfNode temp = myArray[current - 1].first;
	    while(temp != null) {
	    	int v = temp.value;
	    	if(!MarkStamp[v - 1]) {
	    		dfs(temp.value);
	    	}
	    	temp = temp.next;
	    }
	    
	}

	private static int HeaderCount(int[][] data) {
	    LinkedList<Integer> list = new LinkedList<>();
	    
	    for(int i = 0; i < data.length; i++) {
	        int cache = data[i][0];
	        if(!list.contains(cache)) {
	            list.push(cache);
	        }
	    }
	    return list.size();
	}
	
	private static void Msg(String str, boolean ln) {
		if(str == null) return;
		
		if(ln) {
		    System.out.println(str);
		} else {
		    System.out.print(str);
		}
	}

}

// 使用相鄰串列
class DsfNode {
	int value;
	DsfNode next;
	
	DsfNode(int value) {
		this.value = value;
		next = null;
	}
}

class DsfTreeStack {
	DsfNode first, last;
	
	boolean isEmpty() {
		return first == null;
	}
	
	void push(int value) {
		DsfNode n = new DsfNode(value);
		
		if(isEmpty()) {
			first = n;
			last = n;
			return;
		} else {
			last.next = n;
			last = n;
		}
	}
	
	void printBsf() {
		DsfNode cache = first;
		
		while(cache != null) {
			System.out.print("[" + cache.value + "]");
			cache = cache.next;
		}
		System.out.println("");
	}
	
}

1. DsfTreeStack 以**相鄰串列**的方式表達圖形
2. MarkStamp 做為頂點已走過的標記，**每走過一個 Node 皆需要 Mark，因為走過的頂點不能再走**
3. 開始走訪的 Node 此範例定為 1 (也可按照自己的意思從不同節點走)

**--實做--**
> 

### Breadth Search First (BSF)
* **使用到 `佇列 Queue` 的概念**

package dataStruct;

import java.util.LinkedList;

public class Tree_Bsf {
	static BsfTreeLink[] myLink;
	static boolean[] MarkStamp;

	public static void main(String[] args) {
		int[][] data = {
		        {1,2}, {2,1}, {1,5}, {5,1}, {2,3}, {3,2}, {2,4}, {4,2}, 
		        {3,4}, {4,3}, {3,5}, {5,3}, {4,5}, {5,4}
		};
		/*
		int[][] data = {
				{1,2}, {2,1}, {1,3}, {3,1}, {2,4}, {4,2}, {2,5}, {5,2}, {3,6}, {6,3},
				{3,7}, {7,3}, {4,5}, {5,4}, {6,7}, {7,6}, {5,8}, {8,5}, {6,8}, {8,6}
		};
		*/
		
		int count = HeaderCount(data);
	    Msg("Header Count: " + count, true);
	    
	    myLink = new BsfTreeLink[count];
	    MarkStamp = new boolean[count];
	    
	    for(int i = 0; i < count; i++) {
	    	myLink[i] = new BsfTreeLink();
	    	
	    	for(int j = 0; j < data.length; j++) {
	            int head = data[j][0];
	    		if(i == (head - 1)) {
	    			myLink[i].push(data[j][1]);
	    		}
	    	}
	    	
	    	myLink[i].printBsf();
	    }
	    
	    Msg("廣度走訪: ", true);
	    // start point is 1
	    bfs(1, count);
	}
	
	private static void bfs(int current, int size) {
		BsfQueue queue = new BsfQueue(size);
		
		MarkStamp[current - 1] = true;
		queue.enqueue(current);
		
		System.out.print("[" + current +"] ");
		
		while(queue.front != queue.rear) {
			current = queue.dequeue();
			//"1. "
			BsfNode temp = myLink[current - 1].first;
			while(temp != null) {
				if(!MarkStamp[temp.value - 1]) {
					//"2. "
					MarkStamp[temp.value - 1] = true;
					//"3. "
					queue.enqueue(temp.value);
					System.out.print("[" + temp.value +"] ");
				}
				temp = temp.next;
			}
		}
	}

	private static int HeaderCount(int[][] data) {
	    LinkedList<Integer> list = new LinkedList<>();
	    
	    for(int i = 0; i < data.length; i++) {
	        int cache = data[i][0];
	        if(!list.contains(cache)) {
	            list.push(cache);
	        }
	    }
	    return list.size();
	}
	
	private static void Msg(String str, boolean ln) {
		if(str == null) return;
		
		if(ln) {
		    System.out.println(str);
		} else {
		    System.out.print(str);
		}
	}
	

}
//使用相鄰串列
class BsfNode {
	int value;
	BsfNode next;
	
	BsfNode(int value) {
		this.value = value;
		next = null;
	}
}

class BsfQueue {
	int front = -1;
	int rear = -1;
	private int[] array;
	
	BsfQueue(int size) {
		array = new int[size];
	}
	
	void enqueue(int value) {
		if(array.length <= rear) {
			System.out.println("array full, cannot enqueue");
			return;
		}
		
		array[++rear] = value;
	}
	
	int dequeue() {
		if(rear == front) {
			System.out.println("array empty, cannot dequeue");
			return -1;
		}
		
		return array[++front];
	}
}

class BsfTreeLink {
	BsfNode first, last;
	
	boolean isEmpty() {
		return first == null;
	}
	
	void push(int value) {
		BsfNode n = new BsfNode(value);
		
		if(isEmpty()) {
			first = n;
			last = n;
			return;
		} else {
			last.next = n;
			last = n;
		}
	}
	
	void printBsf() {
		BsfNode cache = first;
		
		while(cache != null) {
			System.out.print("[" + cache.value + "]");
			cache = cache.next;
		}
		System.out.println("");
	}
	
}

1. 取出當前的頂點，-1 是為了符合 array 在電腦中的 index
2. 當前 Node 並未走訪時就開始走訪，開始走訪前先標註 Mark
3. 走訪過的結點壓入 Queue

**--實做--**
> 

## Appendix & FAQ

:::info
相鄰複合串列的規則跟圖有點問題 ? 座標 m5(3->4)/m5(4->3) 可以反向指，但是為何 m6 不能反向指 m2(5->1) 不行 ?
:::

###### tags: `資料結構`