# AP325 (圖論)
## DFS深度優先搜尋
```cpp=
#include<bits/stdc++.h>
using namespace std;
int arr[10000];
void postorder(int n){
if(arr[n]==-1)return;
cout<<arr[n];
postorder(2*n+1);
postorder(2*n+2);
}
int main(){
int n;
cin>>n;
memset(arr, -1, sizeof(arr));
for(int i=0;i<n;i++)cin>>arr[i];
postorder(0);
}
```
## DAG ( 無環有向圖 )
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define N 20
int main(){
vector<int> adj[N];
int indeg[N]={0};
int n, m;
int ans[N]={0};
int cnt=0;
cin>>n>>m;
for(int i=0;i<m;i++){
int from, to;
cin>>from>>to;
adj[from].push_back(to);
indeg[to]++;
}
queue<int> q;
for(int i=0;i<n;i++){
if(indeg[i]==0){
q.push(i);
ans[cnt++]=i;
}
}
while(!q.empty()){
int p=q.front();
q.pop();
for(int i=0;i<adj[p].size();i++){
int x=adj[p][i];
indeg[x]--;
if(indeg[x]==0){
q.push(x);
ans[cnt++]=x;
}
}
}
for(int i=0;i<cnt;i++)cout<<ans[i]<<' ';
}
```
## 鄰接串列
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, m, s;
cin>>n>>m>>s;
vector<int> v[105];
queue<int> q;
int vis[105];
int cnt=0, sum=0;
memset(vis, -1, sizeof(vis));
for(int i=0;i<m;i++){
int from, to;
cin>>from>>to;
v[from].push_back(to);
}
q.push(s);
vis[s]=0;
while(!q.empty()){
int p=q.front();
q.pop();
for(int i=0;i<v[p].size();i++){
int x=v[p][i];
if(vis[x]==-1){
vis[x]=vis[p]+1;
q.push(x);
cnt++;
sum+=vis[x];
}
}
}
cout<<cnt<<'\n'<<sum;
}
```
## 鄰接矩陣
```cpp=
#include<bits/stdc++.h>
using namespace std;
int n, m, s;
int adj[100][100]={0};
int d[100];
void bfs(int s){
bool vis[n]={0};
queue<int> q;
q.push(s);
d[s]=0;
vis[s]=1;
int cnt=0, ans=0;
while(!q.empty()){
int v=q.front();
q.pop();
for(int i=0;i<n;i++){
if(!vis[i] && adj[v][i]){
q.push(i);
d[i]=d[v]+1;
ans+=d[i];
vis[i]=1;
cnt++;
}
}
}
cout<<cnt<<'\n'<<ans;
}
int main(){
cin>>n>>m>>s;
for(int i=0;i<m;i++){
int x, y;
cin>>x>>y;
adj[x][y]=1;
}
bfs(s);
}
```
## DAG最長與最短路徑
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, m, s, t;
int cnt=0;
int indeg[10000]={0};
vector<pair<int,int>> v[10000];
queue<int> q;
int maxw[10000], minw[10000];
cin>>n>>m>>s>>t;
for(int i=0;i<m;i++){
int from, to, w;
cin>>from>>to>>w;
v[from].push_back({to,w});
indeg[to]++;
}
for(int i=0;i<n;i++)maxw[i]=-10000001;
for(int i=0;i<n;i++)minw[i]=10000001;
maxw[s]=0, minw[s]=0;
for(int i=0;i<n;i++){
if(indeg[i]==0){
q.push(i);
}
}
while(!q.empty()){
int p=q.front();
q.pop(), cnt++;
for(auto e:v[p]){
if(minw[p]<1000001){
maxw[e.first]=max(maxw[e.first], maxw[p]+e.second);
minw[e.first]=min(minw[e.first], minw[p]+e.second);
}
indeg[e.first]--;
if(indeg[e.first]==0){
q.push(e.first);
}
}
}
if (cnt!=n) fprintf(stderr, "Not a dag, %d < %d\n", cnt, n);
if(minw[t]<10000001)cout<<minw[t]<<'\n'<<maxw[t];
else cout<<"No path"<<'\n'<<"No path";
}
```
## 最短路徑 ( dijkstra )
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define MAX 10000005
#define N 100
int main(){
int n, m, w[N][N], parent[N];
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
w[i][j]=MAX;
for(int i=0;i<m;i++){
int u, v, t;
cin>>u>>v>>t;
w[u][v]=w[v][u]=min(w[u][v], t);
}
int d[N], source=0;
bool done[N]={0};
for(int i=0;i<n;i++){
d[i]=MAX;
parent[i]=-1;
}
d[source]=0;
while(1){
int v=-1, mind=MAX;
for(int i=0;i<n;i++){
if(!done[i] && d[i]<mind){
mind=d[i], v=i;
}
}
if(v<0)break;
done[v]=1;
for(int i=0;i<n;i++){
if(d[v]+w[v][i]<d[i]){
d[i]=d[v]+w[v][i];
parent[i]=v;
}
}
}
int maxd=-1, cnt=0, far;
for(int i=0;i<n;i++){
if(d[i]<MAX){
if(d[i]>maxd)maxd=d[i], far=i;
}else cnt++;
}
cout<<maxd<<'\n'<<cnt<<'\n';
}
```
## 最小生成樹
### prim 演算法
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define MAX 2147483647
#define N 10005
int main(){
vector<pair<int,int>> v[N];
int n, m;
int d[N], done[N]={0};
cin>>n>>m;
for(int i=0;i<m;i++){
int from, to, w;
cin>>from>>to>>w;
v[from].push_back({to,w});
v[to].push_back({from,w});
}
for(int i=0;i<n;i++)d[i]=MAX;
priority_queue<pair<int,int>> pq;
pq.push({d[0]=0, 0});
while(!pq.empty()){
auto p=pq.top();
pq.pop();
if(done[p.second])continue;
done[p.second]=1;
for(auto e:v[p.second]){
if(done[e.first])continue;
if(e.second<d[e.first]){
d[e.first]=e.second;
pq.push({-d[e.first], e.first});
}
}
}
int cost=0, cnt=0;
for(int i=0;i<n;i++){
if(d[i]<MAX)cost+=d[i];
else cnt++;
}
if(cnt)cout<<-1<<'\n';
else cout<<cost<<'\n';
}
```
### kruskal演算法
```cpp=
#include<bits/stdc++.h>
using namespace std;
int p[10005];
struct EDGE{
int u, v, w;
};
int cmp(EDGE &p, EDGE &q){
return p.w<q.w;
}
int rfind(int n){
if(p[n]<0)return n;
return p[n]=rfind(p[n]);
}
bool joint(int u, int v){
int r1, r2;
r1=rfind(u);
r2=rfind(v);
if(r1==r2)return false;
if(r1<r2){
p[r1]+=p[r2];
p[r2]=r1;
}
else{
p[r2]+=p[r1];
p[r1]=r2;
}
return true;
}
int main(){
int n, m;
cin>>n>>m;
vector<EDGE> edge;
for(int i=0;i<m;i++){
int u, v, t;
cin>>u>>v>>t;
edge.push_back({u, v, t});
}
int cost=0, n_edge=0;
for(int i=0;i<n;i++)p[i]=-1;
sort(edge.begin(), edge.end(), cmp);
for(EDGE e:edge){
if(joint(e.u, e.v)){
cost+=e.w;
n_edge++;
}
}
if(n_edge<n-1)cout<<-1<<'\n';
else cout<<cost<<'\n';
}
```
Sign in with Wallet
Connect another wallet