1.圖的表示

對于一個圖（graph）G=（V，E）由頂點集V（vertex）和邊集E（edges）組成。每一條邊就是一個點對（u，w），其中u、w屬于V。

邊：單向邊，雙向邊

權值：有點權，邊權

2.一般做法

建圖+算法??

3.建邊

建邊有三種方法：

1.鄰接矩陣 a[maxn][maxn]?

int main()
{memset(a,0,sizeof(a));int u,v,val;//若u,v之間有權值為val的雙向邊a[u][v]=a[v][u]=val;//u->v單向邊,無權值a[u][v]=1;
}

2.stl:vector存邊

沒有權值vector存int ，有全權值的話要用結構體

struct node
{int to,val;
};
vector<node>v1[maxn];//儲存雙向邊
vector<int>v[maxn];//儲存單向邊
int main()
{int n,x,y,val;for(int i=1;i<=n;i++) v[i].clear();//x->y 單向邊沒有權值v[x].push_back(y);//x<->y 雙向邊有權值val,要加兩次v1[x].push_back(node{y,val});v1[y].push_back(node{x,val});
}

3.鄰接表（鏈式向前星）?

較為抽象，但是也是用的最多的。

struct node
{int to,next,val;
}edge[maxn*2];
void init()
{sign=0;for(int i=0;i<=n;i++)head[i]=-1;
}
void add(int u,int v,int val)
{edge[sign].to=v;edge[sign].next=head[u];edge[sign].val=val;head[u]=sign++;
}

最短路算法：

1.dij? ?復雜度O(n^2)

從最小點松弛，從沒有走過中的最小的點去看能不能，通過邊mp[minpos][j],將其他點到起點的距離縮短。

#include<bits/stdc++.h>
using namespace std;
const int inff=0x3f3f3f3f;
const int maxn=105;
int d[maxn];//d[i]表示i點到起點的最短距離
int mp[maxn][maxn];//圖
int vis[maxn];//標記是否走過
int n,m;
void dij(int start)
{for(int i=1;i<=n;i++) d[i]=inff;d[start]=0;memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++)//找到最所有點中最小的點{int minpos=-1;//標記最小位置for(int j=1;j<=n;j++){if(!vis[j])//j點沒有走過if(minpos==-1||d[j]<d[minpos])minpos=j;}//找到所有點中的最小點,松弛該點到其他的距離if(d[minpos]==inff) break;vis[minpos]=1;for(int j=1;j<=n;j++){if(!vis[j]){int x=d[minpos]+mp[minpos][j];//最小點到其他點的距離if(x<d[j])d[j]=x;}}}
}
int main()
{int x,y,val;while(cin>>n>>m,n+m){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)mp[i][j]=inff;while(m--){scanf("%d %d %d",&x,&y,&val);mp[x][y]=mp[y][x]=val;}//以上為建邊dij(1);printf("%d\n",d[n]);}return 0;
}

vector版本的

#include<bits/stdc++.h>
using namespace std;
const int inff=0x3f3f3f3f;
const int maxn=105;
int d[maxn];//d[i]表示i點到起點的最短距離
int vis[maxn];//標記是否走過
int n,m;
struct node
{int to,val;
};
vector<node>v[maxn];
void dij(int start)
{for(int i=1;i<=n;i++) d[i]=inff;d[start]=0;memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++)//找到最所有點中最小的點{int minpos=-1;//標記最小位置for(int j=1;j<=n;j++){if(!vis[j])//j點沒有走過if(minpos==-1||d[j]<d[minpos])minpos=j;}//找到所有點中的最小點,松弛該點if(d[minpos]==inff) break;vis[minpos]=1;//這里就不用O（n）循環，就是遍歷minpos連接的邊for(int j=0;j<v[minpos].size();j++){int to=v[minpos][j].to;int val=v[minpos][j].val;if(d[minpos]+val<d[to])d[to]=d[minpos]+val;}}
}
int main()
{int x,y,val;while(cin>>n>>m,n+m){for(int i=1;i<=n;i++) v[i].clear();while(m--){scanf("%d %d %d",&x,&y,&val);v[x].push_back(node{y,val});v[y].push_back(node{x,val});}dij(1);printf("%d\n",d[n]);}return 0;
}

復雜度O（mlogn）優先隊列+dij

https://blog.csdn.net/qq_41575950/article/details/80246217

2 .SPFA? 期望復雜度O(E)

可以解決邊權有負值的，最長路等等dij無法處理的。

#include<bits/stdc++.h>
using namespace std;
const int inff=0x3f3f3f3f;
const int maxn=105;
int d[maxn];//d[i]表示i點到起點的最短距離
int vis[maxn];//標記是否走過
int n,m;
struct node
{int to,val;
};
vector<node>v[maxn];
void spfa(int start)
{for(int i=1;i<=n;i++) d[i]=inff;memset(vis,0,sizeof(vis));d[start]=0;queue<int> q;q.push(start);vis[start]=1;while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=0;i<v[u].size();i++){int e=v[u][i].to;int val=v[u][i].val;if(d[e]>d[u]+val){d[e]=d[u]+val;if(!vis[e]){q.push(e);vis[e]=1;}}}}
}
int main()
{int x,y,val;while(cin>>n>>m,n+m){for(int i=1;i<=n;i++) v[i].clear();while(m--){scanf("%d %d %d",&x,&y,&val);v[x].push_back(node{y,val});v[y].push_back(node{x,val});}spfa(1);printf("%d\n",d[n]);}return 0;
}

鄰接表版：

const int maxn=105;
const int maxm=2e5+4;
struct node
{int to,p,val;
}edge[maxm];
int d[maxn],vis[maxn],head[maxn];
int n,m,sign;
void add(int u,int v,int val)
{edge[sign]=node{v,head[u],val};head[u]=sign++;
}
void init()
{memset(head,-1,sizeof(head));memset(d,inff,sizeof(d));
}
void spfa()
{d[1]=0;queue<int>q;q.push(1);while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=head[u];~i;i=edge[i].p){int v=edge[i].to;int val=edge[i].val;if(d[v]>d[u]+val){d[v]=d[u]+val;if(!vis[v]){q.push(v);vis[v]=1;}}}}
}
int main()
{int x,y,z;while(cin>>n>>m,n+m){init();while(m--){scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);}spfa();printf("%d\n",d[n]);}return 0;
}

3.flyod 復雜度O(n^3)

#include<bits/stdc++.h>
using namespace std;
const int inff=0x3f3f3f3f;
const int maxn=105;
int a[maxn][maxn];
int n,m;
int main()
{int x,y,z;while(cin>>n>>m,n+m){for(int i=1;i<=n;i++){a[i][i]=0;for(int j=i+1;j<=n;j++)a[i][j]=a[j][i]=inff;}for(int i=1;i<=m;i++)scanf("%d%d%d",&x,&y,&z),a[x][y]=a[y][x]=z;for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=min(a[i][j],a[i][k]+a[k][j]);cout<<a[1][n]<<endl;}return 0;
}

?

?

?

總結

以上是生活随笔為你收集整理的图论基本知识的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。