# 圖論-無權重無向圖建造
###### tags: `程式設計` `圖論`
## 論述
當我們看到一張無向圖時,如果要對於圖形加以存取,例如得知這個圖形上的某個點與多少個點連接,我們可以透過圖形的建造,將圖形建造成二維陣列。
首先,我們來看這一張圖。
![](https://i.imgur.com/S2dKefq.png)
在這張圖上,我們可以先做幾個簡單的分析再進行建圖,請接續看下去。
## 建圖流程
#### 建圖流程一、分析每個點與其他點的連接:
在這張圖上可以得知
第零個點與第1,第2個點連接
第一個點與第0,第3個點連接
第二個點與第0,第4個點連接
第三個點與第1,第4個點連接
第四個點與第3,第2個點連接
#### 建圖流程二、建立二維陣列:
好的索引會使事情事半功倍
我們可以用二維陣列的索引值來當作欲索引的點
在該索引值的陣列則用來存放與該點連接的列表
例如,假設我們有一個二維陣列叫做graph,則:
graph[0] = {1,2};
graph[1] = {0,3};
graph[2] = {0,4};
graph[3] = {1,4};
graph[4] = {3,2};
這樣可以方便的索引出該點的連接數量(degree),和與該點連接的列表。
#### 建圖結束 - 如何做到更好:
以C++為例,在C++中有動態陣列vector。
以普通陣列array作為建圖的二維陣列,
當點的數量逐漸變多(例如有N個),則我們最多需要花費空間複雜度(N²)。
但若我們使用vector,讓陣列的大小值隨著該點的連接而改變,則我們可以花更少空間複雜度來完成建圖作業。
約莫只需要空間複雜度(N)即可完成建表作業。
接下來,了解如何建表後,我們將會在以下舉例一些常用的無權重無向圖描述方式
以及我們要如何針對於圖形的描述進行建圖的動作。
## 建圖範例
#### 建圖 - 輸入為點與點的連接
第一行有兩個數字n,m,代表有n個點,m個邊。
接下來有m行,m代表該圖的邊(edge)數量,
每一行都有兩個數值x,y,代表x點與y點連通,請問要如何建圖?
範例:
5 5
0 1
0 2
1 3
3 4
4 2
我們可以用上述的方式:
1. 將x點當成索引,在該索引之陣列放入y點。
2. 將y點當成索引,在該索引之陣列放入x點。
由於無向圖是雙向連通的,我們必須要將x點與y點分別當成索引放入與該點連接的點。
以上面的無向圖為例:
```cpp
#include<bits/stdc++.h>
#define mp make_pair
#define pr pair<int,int>
using namespace std;
int main(){
int n = 5; //五個點
int m = 5; //五個邊
vector<vector<int>> graph(n); //長度為5,資料型態為vector<int>的陣列
pr edge[5] = {mp(0,1),mp(0,2),mp(1,3),mp(3,4),mp(4,2)}; //x與y
for(int i = 0; i < m; i++){
int x,y;
x = edge[i].first;
y = edge[i].second;
graph[x].push_back(y); //雙向連通,將x當成索引,放入y點
graph[y].push_back(x); //雙向連通,降y當成索引,放入x點
}
}
```
#### 建圖 - 輸入為adjacency matrix
第一行有一個數字n,代表有n個點
接下來有n行,每一行n~x~有n個數字a~y~ {a~0~,a~1~...a~n-1~}。
其中若在n~x~中的a~y~為0,則代表x與y不連通,否則連通。
保證a~x~等於0。
範例:
5
0 1 1 0 0
1 0 0 1 0
1 0 0 0 1
0 1 0 0 1
0 0 1 1 0
首先,我們先將描述用的陣列存取。
接下來我們開兩個迴圈i,j,第一個為索引的點,第二個為索引點陣列的項次。
接下來完整的讀取陣列,如果array[i][j] == 1,則代表i,j連通,反之則不連通。
若知道i點與j點為連通的,則可照上面的方式建造。
但我們只需要以i為索引點將j放入graph[i]內,原因是我們是按照點去讀取的
因此會將從資料得知每一個點的與該點是否連接,而不需要再做雙向連接的建立。
換句話說,若索引點為a,索引點的陣列項數為b。
若a不等於b,
array[a][b] = 1,則array[a][b]也必為1。
array[a][b] = 0,則array[a][b]也必為0。
若a等於b,則array[a][b] = 0
```cpp
#include<bits/stdc++.h>
#define mp make_pair
#define pr pair<int,int>
using namespace std;
int main(){
int n = 5; //五個點
int m = 5; //五個邊
vector<vector<int>> graph(n); //長度為5,資料型態為vector<int>的陣列
int array[5][5] = { //輸入的資料
{0,1,1,0,0},
{1,0,0,1,0},
{1,0,0,0,1},
{0,1,0,0,1},
{0,0,1,1,0}};
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(array[i][j] == 0) continue; //如果兩點不連通就跳過
graph[i].push_back(j); //將x當成索引,放入y點
}
}
}
```
#### 兩種方式的輸出
程式碼:
```cpp
for(int i = 0; i < n; i++){
cout << i << " ";
for(int node : graph[i]){
cout << node << " ";
}
cout << endl;
}
```
方式1:
0 1 2
1 0 3
2 0 4
3 1 4
4 3 2
方式2:
0 1 2
1 0 3
2 0 4
3 1 4
4 2 3
#### 索引該點的degree
我們可以透過取得該索引點陣列的陣列大小,來知道該點的degree為多少。
程式碼:
```cpp
int n = 3; //你想要索引的點
int degree = graph[n].size();
```
## 總結
我們可以透過許多的方式來建立無向圖,而這也是其中一種較簡便的方式。
用二維陣列來陳述,或者使用結構struct來進行建立,都是一種方式。
利用索引的方式獲取連接點列表,進而進行其他的作業,相對而言會簡便許多。
*write by Xuan*