**在介紹今天的演算法前，我們先來了解一些先備知識**
# 何謂圖
**「圖」是一種用來記錄關聯、關係的東西。一張圖由數個點（ vertex ）以及數條邊（ edge ）所構成。點與點之間，得以邊相連接，表示這兩點有關聯、關係。點的大小形狀和線的粗細長短是無所謂的，我們只在乎它們如何連接。而圖又分為幾個種類：**
### 有向圖
**他有方向，就像 $\overrightarrow{ab}$ 一樣，從 $a$ 連到 $b$ ，不能由 $b$ 走到 $a$。**
### 無向圖

**沒有方向，就像 $\overline{cd}$ 一樣，$c$、$d$ 兩點之間可以雙向通行**

### 有環圖

**他有環，這應該很好理解，但有時候有沒有環實作難度差很多。"環"是指可以一直重複走不到盡頭的情況，例如 1 -> 2 -> 3 -> 1，永遠跑不完。**
### 無環圖

**沒有任何邊可以形成一個完整的環**

### 連通圖

**每一個點都和除了自己之外的所有點相連通。**

# 如何建圖
### **$Edge List$邊圖(MST常用)**
**「邊表」。一條陣列，或者串列，記錄所有點與點之間的邊。**

struct Edge
{
	int start , end;	// 一條邊的起點與終點，變數名稱建議簡短一點
};

Edge edge[4];	// 四條邊
void edge_list()
{
	int e = 0;	// 邊數

	int a, b;	// 一條邊的端點、另一個端點
	while (cin >> a >> b)
	{
		edge[e].start = a;
		edge[e].end = b;
		e++;
	}
}

**這種資料結構相當簡單直觀，也非常節省空間，卻不適合用於計算 ── 無法迅速找到一個點碰觸的所有邊。
因此大家又發明了其他的方式，這裡介紹其中兩種最常見的方式： Adjacency Matrix 、 Adjacency Lists 。 Adjacency 為「相鄰」之意，以邊相連接的兩個點，則稱這兩個點「相鄰」。**

****

### **$Adjacency Matrix$相鄰矩陣**
**「相鄰矩陣」。把一張圖上的點依序標示編號。然後建立一個方陣，記錄連接資訊。方陣中的每一個元素都代表著某兩點的連接資訊。例如元素 (0,1) 記錄著第 0 點到第 1 點的連接資訊、元素 (4, 2) 記錄著第 4 點到第 2 點的連接資訊。**


**連接資訊可以是邊的數目，也可以是邊的權重。
例如底下這張圖，每條邊的值不同，可以代表距離或其他的資訊。**


**另外，當兩點之間的邊超過一條的時候， Adjacency Matrix 無法記錄權重。 Adjacency Matrix 的一個格子只能存入一個數字，無法同時存入多個數字。我們可以修改 Adjacency Matrix 的構造，以存入更多數字，例如更改變數型態為pair，這樣就可以存兩個數字。**

int graph[5][5];
void adjacency_matrix()
{
	for (int i=0; i<5; ++i)
		for (int j=0; j<5; ++j)
			graph[i][j] = 0;

	int a, b, w;	// 一條邊的端點、另一個端點、邊的權重
	while (cin >> a >> b >> w)
		graph[a][b] = w;
}

****
### $Adjacency Lists$相鄰列表
**「相鄰列表」。把一張圖上的點依序標示編號。每一個點，後方列出所有可以到的點。例如第 4 列是第 4 點所有可以到的點。另外，相鄰的點也可以想成是相鄰的邊。**

vector<int> list[5];
void adjacency_lists()
{
	for (int i=0; i<5; ++i)
		list[i].clear();

	int a, b;	// 一條邊的起點、終點
	while (cin >> a >> b)
		list[a].push_back(b); //如果是無向圖只需多加一個相同但互換ab的動作
}


****
# 圖的遍歷
**圖的遍歷，也就是指讀取圖的資訊：決定好從哪裡開始讀，依照什麼順序讀，要讀到哪裡為止。**
**用最簡單的資料結構 queue 和 stack (都可以用vector取代)，就能製造不同的遍歷順序，得到兩種遍歷演算法： Breadth-first Search 和 Depth-first Search。**
### $BFS$
**先搜完同一層的搜尋法**
**依照編號順序不斷找出尚未遍歷的點當作起點，進行下述行為：
　一、把起點塞入queue。
　二、重複下述兩步驟，直到queue裡面沒有東西為止：
　　甲、queue彈出一點。
　　乙、找出跟此點相鄰的點，並且尚未遍歷的點，
　　　　通通（依照編號順序）塞入queue。**

**如何實作**

bool adj[9][9];	// 一張圖，資料結構為adjacency matrix。
bool visit[9];	// 記錄圖上的點是否遍歷過，有遍歷過為true。

void BFS()
{
	// 建立一個queue。
	queue<int> q;

	// 全部的點都初始化為尚未遍歷
	for (int i=0; i<9; i++)
		visit[i] = false;

	for (int k=0; k<9; k++)
        {
		if (!visit[k])
		{
			// 一、把起點塞入queue。
			q.push(k);
			visit[k] = true;

			// 二、重複下述兩點，直到queue裡面沒有東西為止：
			while (!q.empty())
			{
				// 甲、queue彈出一點。
				int i = q.front(); q.pop();

				// 乙、找出跟此點相鄰的點，並且尚未遍歷的點，
				//     依照編號順序通通塞入queue。
				for (int j=0; j<9; j++)
					if (adj[i][j] && !visit[j])
					{
						q.push(j);
						visit[j] = true;
					}
			}
		}
        }
}

### $DFS$
**一條路走到底的搜尋法**

bool adj[9][9];	// 一張圖，資料結構為adjacency matrix。
bool visit[9];	// 記錄圖上的點是否遍歷過，有遍歷過為true。

void DFS(int i)
{
	for (int j=0; j<9; j++)
		if (adj[i][j] && !visit[j])
		{
			visit[j] = true;	// 標記為已遍歷
			DFS(j);
		}
}

void traversal()
{
	// 全部的點都初始化為尚未遍歷
	for (int i=0; i<9; i++)
		visit[i] = false;

	for (int i=0; i<9; i++)
		if (!visit[i])
		{
			visit[i] = true;
			DFS(i);
		}
}

**兩種演算法遍歷方式示意圖**