# 圖論

## 歐拉路徑&漢米爾頓路徑
度：連接點的邊數
入度：進入某點邊的個數
出度：走出某點邊的個數
偶頂點：過點的線段為偶數條
奇頂點：過點的線段為奇數條

歐拉圖：能一筆畫完成的圖(一筆畫問題是考慮邊不是點)
歐拉路徑:由起點走到終點 (起點和終點可以不用相同)
歐拉迴路：由起點走回起點、圖形每條邊恰經過一次(起點和終點相同)
奇點為0個滿足歐拉迴路
理由：有進有出所以入度=出度，度數為偶
奇點為0或2個滿足歐拉路徑，且終點和起點為奇點
理由：入度<出度代表出了不會再進入，為起點 ; 入度>出度代表進入就不會再出，為終點

漢米爾頓(哈密頓)：考慮點(歐拉圖考慮邊)、為NPC問題
漢米爾頓路徑跟歐拉路徑很像，只是漢米爾頓是每個點恰好經過一次（歐拉路徑是邊）

旅行銷售員問題為漢米爾頓迴路延伸

**歐拉迴路&歐拉路徑實作:**

#include<iostream>
#include<cstring>
using namespace std;
int graph[105][105],v[105],d[105],ans[105];
int n,m,k=0;//n為輸入幾行 m為點的個數

void dfs(int s){
    for(int i=1;i<=m;i++)
        if(graph[s][i]){
            graph[s][i]=0;
            graph[i][s]=0;
            dfs(i);
        }
     ans[++k]=s;
}

int main(){
    int start=1;
    int cnt=0;
    cin>>n>>m;
    memset(d,0,sizeof(d));
    for(int i=1;i<=n;i++){
        int a,b;//a為起點 b為終點
        cin>>a>>b;
        graph[a][b]=1;
        graph[b][a]=1;
        d[a]++;
        d[b]++;
    }
    for(int i=1;i<=m;i++){
        if(d[i]%2){
            if(cnt==0)start=i;
            cnt++;
        }
    }
    if(cnt==0)dfs(start);
    if(cnt==2){
        dfs(start);
        ans[k]=start;//奇點個數為偶,起點=終點
    }
    if(cnt==0||cnt==2){
        for(int i=1;i<=k;i++)
            cout<<ans[i]<<' ';
    }
}

## 最短路徑
Single Sorce Shortest Path(單源最短路徑)：
Dijkstra:
看所有點到起點的最短路徑，邊的權重不能為負(如果為負就沒辦法確定當前的路徑必為最短路徑)
實作方法：不斷更新到點的最短路徑，走到的下個點為更新後路徑最短且未走過的點，如果點v被選中就會產生從起點到v的最短路徑

**Dijkstra實作**:

#include<iostream>
#include<cstring>
#define INF 100000 //infinite
using namespace std;
int graph[105][105];
int dis[105];//distance
int arr[105];//判斷是否走過
int n,m;
void dijkstra(){
    int cnt=1;
    while(cnt<n){
        int min_k=INF;
        int k=-1;
        for(int i=2;i<=n;i++){
            if(arr[i])continue;
            if(dis[i]<min_k){
                k=i;
                min_k=dis[i];
            }
        }
    arr[k]=1;
    cnt++;
    for(int i=1;i<=n;i++){
        if(!(arr[i])&&(dis[k]+graph[k][i])<dis[i]){
            dis[i]=dis[k]+graph[k][i];
        }
    }
    }
}

int main(){
    cin>>n>>m; //n為點的個數 m為路徑數
    memset(arr,0,sizeof(arr));
    for(int i=1;i<=n;i++)dis[i]=INF;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            graph[i][j]=INF;
        }
    }
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;//a到b的距離
        cin>>graph[a][b];
        if(a==1)dis[b]=graph[a][b];//如果為1到某點的距離可直接更新最短路徑
    }
    dis[1]=0;
    arr[1]=1;
    dijkstra();
    cout<<"所有點到1的最短路徑:"<<'\n';
    for(int i=1;i<=n;i++)cout<<dis[i]<<' ';
}