圖

有若干個節點，有若干條邊連接節點。（兩個點之間不是必須相連）
比如：

有向圖

可以理解為邊上面有箭頭的圖，比如下面這張圖：

在這張圖中，點 $1$ 可以通過這條有向邊到達點 $2$，但是點 $2$ 到達不了點 $1$。
有向圖的邊是有單向性的。

無向圖

只要連了邊，邊兩端的點都可以互相到達。

這張圖是無向圖，里面任一點都可以互相到達。
這就是一張連通圖。

連通圖

一張無向圖，如果任意一個點都可以到達圖上的所有點，那么這張無向圖就是連通圖。
如圖¹。

強連通圖

一張有向圖，如果任意兩個點都可以互相到達，這就是一張強連通圖。
比如上面的這張圖就是不聯通的，不是強連通圖。
如果再加上一條邊：

現在這就是一張強連通圖了。

帶權圖

可以理解為圖中的邊被加上了一個權值，經過這條邊就要付出對應權值的代價。
比如：

在這張圖中，點 $1$ 走到點 $4$ 的總權值是 $3+5+2=10$。

圖的存儲

鄰接矩陣

假設有一個 $N$ 個點的圖，我們可以開一個 $N?N$ 的二維數組 $a$，$a_{ij}$ 表示點 $i$ 到點 $j$ 有沒有邊。
如果是帶權圖，也可以用 $a_{ij}$ 表示點 $i$ 到點 $j$ 邊的權值。

例題1

題目描述
給出一個無向圖，頂點數為 $n$，邊數為 $m$。$n\le 1000,m\le 10000$
輸入格式
第一行兩個整數 $n,m$，接下來有 $m$ 行，每行兩個整數 $u,v$,表示點 $u$ 到點 $v$ 有一條邊。
輸出格式
由小到大依次輸出每個點的鄰接點，鄰接點也按照由小到大的順序輸出。

首先 $n$ 只有 $1000$，可以用鄰接矩陣存圖。
是無向圖，所以 $u$ 到 $v$ 和 $v$ 到 $u$ 都有一條邊，所以要雙向存。

#include<bits/stdc++.h>
#define psp putchar(' ')
#define endl putchar('\n')
using namespace std;
const int M=1e3+5;
int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();return x*f;
}
void print(int x){if(x<0)putchar('-'),x=-x;if(x<10){putchar(x+'0');return;}print(x/10);putchar(x%10+'0');
}
int n,m;
int a[M][M];
signed main(){n=read(),m=read();for(int i=1;i<=m;i++){int u=read(),v=read();//雙向存邊a[u][v]=1;a[v][u]=1;}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(a[i][j])print(j),psp;//有邊，輸出。}endl;}
}

鄰接表

假如一張圖有 $2048$ 個點，那么用鄰接矩陣就要開 $2048^2$ 的數組，那如果這張圖只有 $10$ 條邊，開這么大的空間就全浪費了。
這時候就要用到鄰接表。
可以用動態數組來存點和邊，減少空間的浪費。

vector<int>a[N];

例題2

題目描述
給出一個無向圖，頂點數為 $n$，邊數為 $m$。$n\le 1000,m\le 10000$
輸入格式
第一行兩個整數 $n,m$，接下來有 $m$ 行，每行兩個整數 $u,v$,表示點 $u$ 到點 $v$ 有一條邊。
輸出格式
第i行輸出第點 $i$ 的所有鄰接點，鄰接點按照度數由小到大輸出,如果度數相等，則按照編號有小到大輸出。

按照度數排序，用鄰接表更方便。

#include<bits/stdc++.h>
#define endl putchar('\n')
using namespace std;
const int N=1e6+5;
int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();return x*f;
}
void print(int x){if(x<0)putchar('-'),x=-x;if(x<10){putchar(x+'0');return;}print(x/10);putchar(x%10+'0');
}
int n,m;
vector<int>a[N];
int d[N];
bool cmp(int a,int b){//按照度數排序return d[a]<d[b]||(d[a]==d[b]&&a<b);
}
signed main(){n=read(),m=read();for(int i=1;i<=m;i++){int u=read(),v=read();//鄰接表存圖a[u].push_back(v);a[v].push_back(u);d[u]++,d[v]++;}for(int i=1;i<=n;i++){sort(a[i].begin(),a[i].end(),cmp);for(int j=0;j<a[i].size();j++)print(a[i][j]),psp;endl;}
}

例題3

題目描述
$K(1\le K\le 100)$ 只奶牛分散在 $N(1\le N\le 1000)$ 個牧場。現在她們要集中起來進餐。
牧場之間有 $M(1\le M\le 10000)$ 條有向路連接，而且不存在起點和終點相同的有向路。她們進餐的地點必須是所有奶牛都可到達的地方。
那么，有多少這樣的牧場呢？
輸入格式
第1行輸入 $K,N,M$。
接下來 $K$ 行，每行一個整數表示一只奶牛所在的牧場編號。
接下來 $M$ 行，每行兩個整數，表示一條有向路的起點和終點。
輸出格式
所有奶牛都可到達的牧場個數。

由于 $N$ 最大只有 $1000$，$K$ 最大只有 $100$，所以可以考慮枚舉每一頭牛，然后記他們可以到達的點，最后的答案就有所有牛都能到達點的數量。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();return x*f;
}
void print(int x){if(x<0)putchar('-'),x=-x;if(x<10){putchar(x+'0');return;}print(x/10);putchar(x%10+'0');
}
int n,m,k;
int cow[N];
vector<int>a[N];
int vis[N];
int dis[N];//dis[i]表示點i有幾頭牛可以到達
signed main(){k=read(),n=read(),m=read();for(int i=1;i<=k;i++)cow[i]=read();while(m--){int u=read(),v=read();a[u].push_back(v);}for(int i=1;i<=k;i++){queue<int>q;for(int j=1;j<=n;j++)vis[j]=0;vis[cow[i]]=1;q.push(cow[i]);while(!q.empty()){int x=q.front();q.pop();dis[x]++;//記錄for(int p=0;p<a[x].size();p++){int y=a[x][p];if(vis[y])continue;vis[y]=1;q.push(y);}}}int ans=0;for(int i=1;i<=n;i++)ans+=(dis[i]==k);print(ans);
}

例題4

P3144 [USACO16OPEN] Closing the Farm S
依次遍歷每個倉庫關閉，檢查是否能遍歷到除關閉倉庫外的所有倉庫。

#include<bits/stdc++.h>
#define endl putchar('\n')
using namespace std;
const int N=1e6+5;
int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();return x*f;
}
void putstr(string s){for(char v:s)putchar(v);
}
int n,m;
vector<int>a[N];
int cl[N];
int vis[N];
signed main(){n=read(),m=read();while(m--){int u=read(),v=read();a[u].push_back(v);a[v].push_back(u);}int st=1;for(int i=1;i<=n;i++){while(cl[st])st++;queue<int>q;q.push(st);for(int i=1;i<=n;i++)vis[i]=0;vis[st]=1;while(!q.empty()){int x=q.front();q.pop();for(int i=0;i<a[x].size();i++){int y=a[x][i];if(vis[y])continue;if(cl[y])continue;vis[y]=1;q.push(y);}}bool flag=1;for(int i=1;i<=n;i++){if(cl[i])continue;if(!vis[i])flag=0;}cl[read()]=1;if(flag)putstr("YES");else putstr("NO");endl;}
}

最短路

一張帶權圖，一個點 $x$ 到另一個點 $y$ 所經過邊的最小權值和稱為點 $x$ 到點 $y$ 的最短路。

Dijkstra

一種高效的求最短路的算法，缺點是不能求帶負權的最短路。
它的主要用途是求一個點到圖中其他點的最短路。
具體過程
最開始，除了起點外所有點沒有被標記過，起點是最開始被選中的點。
開始模擬：找到被選中的點連接的最小邊權的且沒有被標記過的點 $y$，記錄最短路，然后點 $y$ 被標記，并成為下一個被選中的點，直到所有點都被標記。

例題5

P4779 【模板】單源最短路徑（標準版）
具體代碼見單源最短路徑

SPFA

講解+例題見帶負權的最短路問題

---

1. 見無向圖 ??