目录
图的存储
图常用的两种存储方式是邻接矩阵跟邻接表
邻接矩阵
邻接矩阵定义
const int maxn=1005; //最大顶点数
int G[maxn][maxn]; //G存储图的边
图的邻接矩阵的遍历方式
深度优先遍历（DFS）
DFS脱单法则：先追一个妹子，如果不合适，换追这个妹子的朋友，还不合适就追妹子朋友的朋友…🤪
void dfs(int v){ //邻接矩阵的深度优先遍历
visit[v]=1; //标记已访问
cout<<v<<' '; //访问方式
for(int i=1;i<=N;i++){
if(visit[i]==0&&G[v][i]==1) //如果i未被访问且i与v有相连的边，则访问顶点i
dfs(i); //访问i
}
}
广度优先遍历（BFS）
BFS脱单法则:同时追几个妹子，直到找到合适自己的🤪
void bfs(int s){ //s为访问的起点
queue<int>q; //定义队列
q.push(s); //把起始顶点入队
visit[s]=1; //把起始顶点标记为已访问
while(!q.empty()){ //当队列不为空时，一直循环
int v=q.front(); //取队首顶点
cout<<v<<' '; //访问的方式
q.pop(); //访问完该顶点，即可将其出队
for(int i=1;i<=N;i++){//遍历所有顶点，找到所有与v相连的顶点
if(visit[i]==0&&G[v][i]==1){ //如果i未被访问且i与v有相连的边，则把i入队
visit[i]=1; //访问标记要在此处写
q.push(i); //入队
}
}
}
}
完整程序代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005; //最大顶点数
int G[maxn][maxn],N,M;
int visit[maxn]={0}; //初始化未访问
void dfs(int v){ //邻接矩阵的深度优先遍历
visit[v]=1; //标记已访问
cout<<v<<' '; //访问方式
for(int i=1;i<=N;i++){ //零阶矩阵需要遍历1~N
if(visit[i]==0&&G[v][i]==1) //如果i未被访问且i与v有相连的边，则dfs(i)
dfs(i); //访问i
}
}
void bfs(int s){ //s为访问的起点
queue<int>q; //定义队列
q.push(s); //把起始顶点入队
visit[s]=1; //把起始顶点标记为已访问
while(!q.empty()){ //当队列不为空时，一直循环
int v=q.front(); //取队首顶点
cout<<v<<' '; //访问的方式
q.pop(); //访问完该顶点，即可将其出队
for(int i=1;i<=N;i++){
if(visit[i]==0&&G[v][i]==1){ //如果i未被访问且i与v有相连的边，则把i入队
visit[i]=1; //访问标记要在此处写
q.push(i); //入队
}
}
}
}
int main(){
cin>>N>>M; //N为定点数1~N，M为边的个数
for(int i=0;i<M;i++){
int a,b;
scanf("%d %d",&a,&b);
G[a][b]=G[b][a]=1;//有向图的输入
//G[a][b]=1; 有向图的输入
}
// dfs(1); //深度优先遍历
// bfs(1); //广度优先遍历
return 0;
}
//输入
7 7
4 1
4 6
1 3
6 5
6 7
3 2
3 5
邻接表
邻接表的定义
vector<int>G[maxn]; //初始化大小maxn
图的邻接矩阵的遍历方式
深度优先遍历（DFS）
void dfs(int v){
visit[v]=1;
cout<<v<<' ';
for(int i=0;i<G[v].size();i++){
if(visit[G[v][i]]==0)
dfs(G[v][i]);
}
}
广度优先遍历（BFS）
void bfs(int s){
queue<int>q;
q.push(s);
visit[s]=1;
while(!q.empty()){
int v=q.front();
q.pop();
cout<<v<<' ';
for(int i=0;i<G[v].size();i++){
if(visit[G[v][i]]==0){ //注意顶点是G[v][i]，而不是i
visit[G[v][i]]=1;
q.push(G[v][i]);
}
}
}
}
完整程序代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005; //最大定点数
int N,M;
vector<int>G[maxn]; //初始化maxn
int visit[maxn]={0}; //初始化全部顶点为未访问
void dfs(int v){
visit[v]=1; //标记已访问
cout<<v<<' '; //访问方式
for(int i=0;i<G[v].size();i++){ //与邻接矩阵不同的是，只需要遍历与v相连接的顶点
if(visit[G[v][i]]==0) //如果未访问
dfs(G[v][i]); //访问
}
}
void bfs(int s){
queue<int>q;
q.push(s);
visit[s]=1;
while(!q.empty()){
int v=q.front();
q.pop();
cout<<v<<' ';
for(int i=0;i<G[v].size();i++){
if(visit[G[v][i]]==0){ //注意顶点是G[v][i]，而不是i
visit[G[v][i]]=1;
q.push(G[v][i]);
}
}
}
}
int main(){
cin>>N>>M; //N为定点数1~N，M为边的个数
for(int i=0;i<N;i++){
int a,b;
scanf("%d %d",&a,&b);
//无向图输入
G[a].push_back(b); //表示a与b相连
G[b].push_back(a); //表示b与a相连
//有向图输入
//G[a].push_back(b); //表示a指向b
}
dfs(1); //深度优先遍历
// bfs(1); //广度优先遍历
return 0;
}
图的相关算法
最短路径
单源最短路径(Dijktra)
Dijkstra脱单法则：找到所有自己亲近的朋友，以这些朋友为中介，让他们找到你想追的女孩的最短路径🤪
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
const int inf=0xfffffff; //设inf为无穷大
int G[maxn][maxn]; //存放图
int N,M,dis[maxn+1];//N为顶点数，M为边数，dis是存放源点到各个顶点的距离
bool visit[maxn]={false};//访问
void Dijkstra(int s){ //s为源点
fill(dis,dis+maxn+1,inf);//初始化源点到各顶点的距离都为无穷
dis[s]=0; //源点到源点的距离为0
for(int i=1;i<=N;i++){ //循环N次
int u=-1,min=inf;
for(int j=1;j<=N;j++){ //找到未访问，且与源点距离最短的点
if(dis[j]<min&&visit[j]==false){
u=j;
min=dis[j];
}
}
visit[u]=true; //标记未已访问
if(u==-1) return; //如果找不到则u还是为-1，即该源点与其他顶点不连通
for(int v=1;v<=N;v++){
if(visit[v]==false&&G[v][u]!=inf&&dis[u]+G[u][v]<dis[v]){ //以顶点u作为标尺优化所有能使距离变小的且未访问的顶点
dis[v]=G[u][v]+dis[u]; //更新dis[v]
}
}
}
}
int main(){
cin>>N>>M;
fill(G[0],G[0]+maxn*maxn,inf); //初始化所有边的距离为无穷
for(int i=0;i<M;i++){
int a,b,c; //a,b为顶点，c为权值（距离）
cin>>a>>b>>c;
G[a][b]=G[b][a]=c; //无向图
//有向图可写成以下
//G[a][b]=1;
}
Dijkstra(1); //源点为1
for(int i=1;i<=N;i++){
cout<<dis[i]<<' ';
}
return 0;
}
/**输入**
5 6
1 2 3
1 3 1
2 4 2
2 5 1
3 4 6
3 5 5
*/
/**输出**
0 3 1 5 4
*/
Dijkstra+DFS求解算法
算法思路分两部分：
1、对源点进行Dijkstra，在求最短路径的时候，需要用到二维数组pre[maxn]记录前驱顶点
2、通过对终点进行DFS，可枚举所用的最短路径，可统计最短路径的条数、或者计算每条路径的优化尺度等等，选择最优的路径。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005; //最大顶点数
const int inf=0x3fffffff; //设inf为无穷大
int G[maxn][maxn]; //存放图
int N,M,st,ed,dis[maxn+1],n;//N为顶点数，M为边数，dis是存放源点到各个顶点的距离,n为最短路径的条数
bool visit[maxn]={false};//访问
vector<int>pre[maxn],path;//pre[]为二维数组，来存每个顶点的前驱顶点，path为dfs时走的路径
void Dijkstra(int s){ //s为源点
fill(dis,dis+maxn+1,inf);//初始化源点到各顶点的距离都为无穷
dis[s]=0; //源点到源点的距离为0
for(int i=1;i<=N;i++){ //循环N次
int u=-1,min=inf;
for(int j=1;j<=N;j++){ //找到未访问且与源点距离最短的点
if(dis[j]<min&&visit[j]==false){
u=j;
min=dis[j];
}
}
visit[u]=true; //标记未已访问
if(u==-1) return; //如果找不到则u还是为-1，即该源点与其他顶点不连通
for(int v=1;v<=N;v++){
if(visit[v]==false&&G[u][v]!=inf){
if(dis[u]+G[u][v]<dis[v]){ //以顶点u作为标尺优化所有能使距离变小的且未访问的顶点
dis[v]=G[u][v]+dis[u]; //更新dis[v]
pre[v].clear(); //找到更短的路径，则删除顶点v的所有的前驱顶点
pre[v].push_back(u); //将u作为新的前驱顶点
}
else if(dis[u]+G[u][v]==dis[v]){//如果相等则说明短路路径不只一条
pre[v].push_back(u);//同样把u作为v的前驱结点
}
}
}
}
}
void DFS(int ed){ //ed为终点
path.push_back(ed);//将顶点ed放入路径中
if(ed==st){ //如果dfs到起点，这时一条以起点为st终点为ed的最短路径生成
n++;
for(int i=path.size()-1;i>=0;i--){ //由于是从终点往前dfs，故所走的路径是倒过来的，逆序输出即可
cout<<path[i]<<' ';
}
cout<<endl;
}
for(int i=0;i<pre[ed].size();i++){ //DFS顶点ed所有的前驱顶点
DFS(pre[ed][i]);
}
path.pop_back(); //递归到此处，所有经过顶点ed的路径已枚举完毕，即可删除。
}
int main(){
cin>>N>>M>>st>>ed; //N、M分别为顶点数跟边数，st为源点，ed为终点
fill(G[0],G[0]+maxn*maxn,inf); //初始化所有边的距离为很大的数来表示无穷
for(int i=0;i<M;i++){
int a,b,c; //a,b为顶点，c为权值（距离）
cin>>a>>b>>c;
G[a][b]=G[b][a]=c; //无向图
//有向图可写成以下
//G[a][b]=1;
}
Dijkstra(st); //源点为st
DFS(ed); //终点为ed
return 0;
}
/**输入**
6 7 1 6
1 2 3
1 3 4
1 5 1
2 3 1
2 4 1
3 6 2
4 5 1
*/
/**输出**
1 3 6
1 2 3 6
1 5 4 2 3 6
*/
全源最短路径（Floyd）
#include<bits/stdc++.h>
using namespace std;
const int maxv=500; //最大顶点数
const int INF=0xfffffff; //设INF为很大的数
int N,M; //N、M分别为顶点数跟边数
int dis[maxv][maxv];
void Floyd(){
for(int k=0;k<N;k++){
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(dis[i][k]!=INF&&dis[k][j]!=INF&&dis[i][k]+dis[k][j]<dis[i][j]){
dis[i][j]=dis[i][k]+dis[k][j];
}
}
}
}
}
int main(){
cin>>N>>M;
fill(dis[0],dis[0]+maxv*maxv,INF); //初始化图中的所有边都为INF，即所有边都不存在
for(int i=0;i<N;i++)
dis[i][i]=0; //顶点i到i的距离为0
for(int i=0;i<M;i++){
int u,v,w; //u、v为顶点，w为边权
cin>>u>>v>>w;
//dis[u][v]=G[v][u]=w; //无向图
dis[u][v]=w; //有向图
}
Floyd(); //算法入口
for(int i=0;i<N;i++){ //打印
for(int j=0;j<N;j++)
cout<<dis[i][j]<<' ';
cout<<endl;
}
return 0;
}
/**输入**
6 8
0 1 1
0 3 4
0 4 4
1 3 2
2 5 1
3 2 2
3 4 3
4 5 3
*/
/**输出**
0 1 5 3 4 6
268435455 0 4 2 5 5
268435455 268435455 0 268435455 268435455 1
268435455 268435455 2 0 3 3
268435455 268435455 268435455 268435455 0 3
268435455 268435455 268435455 268435455 268435455 0
*/
最小生成树
最小生成树之Prim
Prim跟Dijkstra的思路基本相同，区别是dis数组的意义不同，在Dijsktra算法中dis数组记录的是顶点到源点的距离，而Prim算法中dis记录的是顶点到集合的距离。
#include<bits/stdc++.h>
using namespace std;
const int maxv=1005; //最大顶点数
const int INF=0xfffffff; //设INF为很大的数
int N,M,G[maxv][maxv]; //N、M分别为顶点数跟边数
int dis[maxv]; //顶点与集合S的最短距离
bool visit[maxv]={false}; //标记是否访问的数组，初始化为未访问
int Prim(int s){ //参数s为源点
fill(dis,dis+maxv,INF); //初始化源点s到所有点的距离为INF
dis[s]=0; //源点到自己的距离为0
int sum=0; //记录边权之和
for(int i=0;i<N;i++){
int u=-1,MIN=INF;
for(int j=0;j<N;j++){
if(visit[j]==false&&dis[j]<MIN){
u=j;
MIN=dis[j];
}
}
if(u==-1)return -1;
visit[u]=true; //标记已访问
sum+=dis[u]; //计算边权
for(int v=0;v<N;v++){
//如果以u为中介能使dis[v]距离更短，则优化
if(visit[v]==false&&G[u][v]!=INF&&G[u][v]<dis[v]){
dis[v]=G[u][v]; //将G[u][v]赋给dis[v]
}
}
}
return sum; //返回最小生成树的边权之和
}
int main(){
cin>>N>>M;
fill(G[0],G[0]+maxv*maxv,INF); //初始化图中的所有边都为INF，即所有边都不存在
for(int i=0;i<M;i++){
int u,v,w; //u、v为顶点，w为边权
cin>>u>>v>>w;
G[u][v]=G[v][u]=w; //无向图
//G[u][v]=w; 有向图
}
cout<<Prim(0); //以0为源点
return 0;
}
/**输入**
6 10
0 1 4
0 4 1
0 5 2
1 2 6
1 5 3
2 3 6
2 5 5
3 4 4
3 5 5
4 5 3
*/
/**输出**
15
*/
最小生成树之Kruskal
Kruskal算法最耗时的部分是排序，所以适合用于边少的图（稀疏图）
算法思想：
1、对所有边按边权从小到大排序。
2、然后遍历所有边，依次判断该边的两个顶点是否在同一个集合中（利用并查集中的查找父亲函数Find()），如果不在同一个集合则将它们合并（利用并查集中的Union(a,b)函数）且统计合并的边数跟总边权。
3、遍历完后，判断边数是否是顶点数减一，是则是连通图，反之不是连通图。
#include<bits/stdc++.h>
using namespace std;
struct Node{
int u,v;
int cost;
};
const int Maxn = 10005; //最大顶点数
int N,M,cost=0,egen=0; //N、M分别为顶点数跟边数，cost为边权，egen为生成树的边
vector<Node >T;
int father[Maxn];
int Find(int x){
while(x!=father[x]){ //找树根
x=father[x];
}
return x;
}
void Union(int x,int y){ //并查集合并两个元素到一个集合中
x=Find(x);
y=Find(y);
if(x<y)
father[x]=y;
else
father[y]=x;
}
int cmp(Node a,Node b){
return a.cost<b.cost;
}
int Kruskal(){
for(int i=0;i<=N;i++) //初始化顶点的根为自己
father[i]=i;
sort(T.begin(),T.end(),cmp); //对边进行排序
for(int i=0;i<T.size();i++){ //遍历所有边
if(Find(T[i].u) != Find(T[i].v)){ //如果两个顶点不在一个集合中
Union(T[i].u,T[i].v); //合并一个集合中
cost+=T[i].cost; //统计边权
egen++; //统计边数
}
}
if(egen!=N-1)return -1; //如果边数 != 顶点数-1。说明该图不连通返回-1
else return cost;
}
int main(){
cin>>N>>M;
for(int i=0;i<M;i++){
Node temp;
cin>>temp.u>>temp.v>>temp.cost;
T.push_back(temp);
}
cout<<Kruskal();
return 0;
}
/**输入**
6 10
0 1 4
0 4 1
0 5 2
1 2 1
1 5 3
2 3 6
2 5 5
3 4 5
4 5 3
3 5 4
*/
/**输出**
11
*/