# 圖論-無權重無向圖建造
###### tags: `程式設計` `圖論`

## 論述

當我們看到一張無向圖時，如果要對於圖形加以存取，例如得知這個圖形上的某個點與多少個點連接，我們可以透過圖形的建造，將圖形建造成二維陣列。

首先，我們來看這一張圖。


在這張圖上，我們可以先做幾個簡單的分析再進行建圖，請接續看下去。

## 建圖流程

#### 建圖流程一、分析每個點與其他點的連接：

在這張圖上可以得知
第零個點與第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點分別當成索引放入與該點連接的點。
以上面的無向圖為例：

#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

#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點
        }
    }
}

#### 兩種方式的輸出

程式碼：

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為多少。

程式碼：

int n = 3; //你想要索引的點
int degree = graph[n].size(); 

## 總結
我們可以透過許多的方式來建立無向圖，而這也是其中一種較簡便的方式。
用二維陣列來陳述，或者使用結構struct來進行建立，都是一種方式。

利用索引的方式獲取連接點列表，進而進行其他的作業，相對而言會簡便許多。

*write by Xuan*