东莞万江网站制作,上海网站建设流,网站策划建设方案书,南阳最新通知今天图论 最短路问题
有向图
1.邻接矩阵#xff0c;稠密图
2.邻接表 #xff08;常用#xff09;单链表#xff0c;每一个点都有一个单链表 #xff0c;插入一般在头的地方插#xff0c;
图的邻接表的存储方式
树的深度优先遍历
特殊的深度优先搜索#xff0c…图论 最短路问题
有向图
1.邻接矩阵稠密图
2.邻接表 常用单链表每一个点都有一个单链表 插入一般在头的地方插
图的邻接表的存储方式
树的深度优先遍历
特殊的深度优先搜索难点是如何实现一条道走到黑
const int N100010,Mn*2;
int h[N],e[N],ne[N],idx;
bool st[N];//记录状态void add(int a,int b)
{e[idx]b;ne[idx]h[a];h[a]idx;
}
void dfs(int u)
{st[u]true;for(ih[u];i!-1;ine[i]){int je[i];//当前节点对应的图的值if(!st[j])dfs(j);}
}
int main()
{memset(h,-1,sizeof(h));return 0;
}树的宽度优先遍历
例题图的层序搜索
#includeiostream
#includealgorithm
#includecstring
#includecstdio
#includequeue
using namespace std;const int N100010;
int n,m;
int d[N];
int e[N],h[N],idx,ne[N];
void add(int a,int b)
{e[idx]b;ne[idx]h[a];h[a]idx;
}
void bfs()
{memset(d,-1,sizeof d);queueint q;d[1]0;q.push(1);while(q.size()){auto tq.front();q.pop();for(int ih[t];i!-1;ine[i]){int je[i];if(d[j]-1){d[j]d[t]1;q.push(j);}}}printf(%d,d[n]);
}
int main()
{cinnm;memset(h,-1,sizeof h);for(int i0;im;i){int a,b;cinab;add(a,b);}bfs();return 0;
}拓扑序列有向图
例题 有向图的拓扑序列
#include cstring
#include iostream
#include algorithmusing namespace std;const int N 100010;int n, m;
int h[N], e[N], ne[N], idx;
int d[N];
int q[N];void add(int a, int b)
{e[idx] b, ne[idx] h[a], h[a] idx ;
}bool topsort()
{int hh 0, tt -1;for (int i 1; i n; i )if (!d[i])q[ tt] i;while (hh tt){int t q[hh ];for (int i h[t]; i ! -1; i ne[i]){int j e[i];if (-- d[j] 0)q[ tt] j;}}return tt n - 1;
}int main()
{scanf(%d%d, n, m);memset(h, -1, sizeof h);for (int i 0; i m; i ){int a, b;scanf(%d%d, a, b);add(a, b);d[b] ;}if (!topsort()) puts(-1);else{for (int i 0; i n; i ) printf(%d , q[i]);puts();}return 0;
}迪杰斯特拉算法(朴素版)
#includecstdio
#includealgorithm
#includeiostream
#includecstring
using namespace std;
const int a1510;
int n,m;
int g[a1][a1];
int dist[a1];
bool st[a1];
int dijk()
{memset(dist,0x3f,sizeof dist);dist[1]0;for(int i0;in-1;i){int t-1;for(int j1;jn;j){if(!st[j](t-1||dist[t]dist[j]))tj;}for(int j1;jn;j)dist[j]min(dist[j],dist[t]g[t][j]);st[t]true;}if(dist[n]0x3f3f3f3f)return -1;return dist[n];
}
int main()
{cinnm;memset(g,0x3f,sizeof g);while(m--){int a,b,c;cinabc;g[a][b]min(g[a][b],c);}coutdijk();return 0;
}迪杰斯特拉算法堆优化版
#includeiostream
#includequeue
#includealgorithm
#includecstdio
#includecstring
using namespace std;
typedef pairint,int pii;
const int N 1e6 10;
int n,m,a,b,c;
int h[N],e[N],ne[N],w[N],idx;
int dist[N];
bool st[N];
void add(int a,int b,int c)
{e[idx]b,w[idx]c,ne[idx]h[a],h[a]idx;
}
int dijk()
{memset(dist,0x3f3f3f3f,sizeof dist);dist[1]0;priority_queuepii, vectorpii, greaterpii heap;heap.push({0,1});while(heap.size()){auto theap.top();heap.pop();int vert.second,distancet.first;if(st[ver])continue;st[ver]true;for(int ih[ver];i!-1;ine[i]){int je[i];if(dist[j]dist[ver]w[i]){dist[j]dist[ver]w[i];heap.push({dist[j],j});}}}if(dist[n]0x3f3f3f3f)return -1;return dist[n];
}
int main()
{cinnm;memset(h,-1,sizeof h);while(m--){cinabc;add(a,b,c);}coutdijk();return 0;
}
