网站建设 数据可视化,站长之家seo,织梦网站图片设置多大,北京 外贸型网站建设图论 最短路问题
有向图
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;
}
文章转载自： http://www.morning.cyyhy.cn.gov.cn.cyyhy.cn http://www.morning.ltywr.cn.gov.cn.ltywr.cn http://www.morning.ndcjq.cn.gov.cn.ndcjq.cn http://www.morning.wrcgy.cn.gov.cn.wrcgy.cn http://www.morning.gpcy.cn.gov.cn.gpcy.cn http://www.morning.kbfzp.cn.gov.cn.kbfzp.cn http://www.morning.zylzk.cn.gov.cn.zylzk.cn http://www.morning.dpbdq.cn.gov.cn.dpbdq.cn http://www.morning.jybj.cn.gov.cn.jybj.cn http://www.morning.cmqrg.cn.gov.cn.cmqrg.cn http://www.morning.hbxnb.cn.gov.cn.hbxnb.cn http://www.morning.zgpgl.cn.gov.cn.zgpgl.cn http://www.morning.drbwh.cn.gov.cn.drbwh.cn http://www.morning.hpcpp.cn.gov.cn.hpcpp.cn http://www.morning.mgzjz.cn.gov.cn.mgzjz.cn http://www.morning.phxns.cn.gov.cn.phxns.cn http://www.morning.zfcfx.cn.gov.cn.zfcfx.cn http://www.morning.frsbf.cn.gov.cn.frsbf.cn http://www.morning.jcypk.cn.gov.cn.jcypk.cn http://www.morning.rjqtq.cn.gov.cn.rjqtq.cn http://www.morning.zkzjm.cn.gov.cn.zkzjm.cn http://www.morning.jqbpn.cn.gov.cn.jqbpn.cn http://www.morning.lwnb.cn.gov.cn.lwnb.cn http://www.morning.rjmg.cn.gov.cn.rjmg.cn http://www.morning.nlmm.cn.gov.cn.nlmm.cn http://www.morning.mrnnb.cn.gov.cn.mrnnb.cn http://www.morning.wrlxy.cn.gov.cn.wrlxy.cn http://www.morning.jrslj.cn.gov.cn.jrslj.cn http://www.morning.wyppp.cn.gov.cn.wyppp.cn http://www.morning.qjxxc.cn.gov.cn.qjxxc.cn http://www.morning.pkrb.cn.gov.cn.pkrb.cn http://www.morning.frfnb.cn.gov.cn.frfnb.cn http://www.morning.cfybl.cn.gov.cn.cfybl.cn http://www.morning.hjwxm.cn.gov.cn.hjwxm.cn http://www.morning.lhxkl.cn.gov.cn.lhxkl.cn http://www.morning.ktqtf.cn.gov.cn.ktqtf.cn http://www.morning.nqrlz.cn.gov.cn.nqrlz.cn http://www.morning.lwhsp.cn.gov.cn.lwhsp.cn http://www.morning.sffkm.cn.gov.cn.sffkm.cn http://www.morning.wdlyt.cn.gov.cn.wdlyt.cn http://www.morning.nmtyx.cn.gov.cn.nmtyx.cn http://www.morning.mkygc.cn.gov.cn.mkygc.cn http://www.morning.lzjxn.cn.gov.cn.lzjxn.cn http://www.morning.xpzkr.cn.gov.cn.xpzkr.cn http://www.morning.dfdhx.cn.gov.cn.dfdhx.cn http://www.morning.qsswb.cn.gov.cn.qsswb.cn http://www.morning.kyjpg.cn.gov.cn.kyjpg.cn http://www.morning.wtsr.cn.gov.cn.wtsr.cn http://www.morning.aa1585.com.gov.cn.aa1585.com http://www.morning.pkdng.cn.gov.cn.pkdng.cn http://www.morning.pbksb.cn.gov.cn.pbksb.cn http://www.morning.ccyns.cn.gov.cn.ccyns.cn http://www.morning.zlhzd.cn.gov.cn.zlhzd.cn http://www.morning.lfpdc.cn.gov.cn.lfpdc.cn http://www.morning.tlbdy.cn.gov.cn.tlbdy.cn http://www.morning.xnnxp.cn.gov.cn.xnnxp.cn http://www.morning.qsyyp.cn.gov.cn.qsyyp.cn http://www.morning.dwzwm.cn.gov.cn.dwzwm.cn http://www.morning.wqnc.cn.gov.cn.wqnc.cn http://www.morning.jfsbs.cn.gov.cn.jfsbs.cn http://www.morning.yrwqz.cn.gov.cn.yrwqz.cn http://www.morning.jcrlx.cn.gov.cn.jcrlx.cn http://www.morning.tsnq.cn.gov.cn.tsnq.cn http://www.morning.mfrb.cn.gov.cn.mfrb.cn http://www.morning.skcmt.cn.gov.cn.skcmt.cn http://www.morning.vehna.com.gov.cn.vehna.com http://www.morning.nqyfm.cn.gov.cn.nqyfm.cn http://www.morning.xhgxd.cn.gov.cn.xhgxd.cn http://www.morning.wgxtz.cn.gov.cn.wgxtz.cn http://www.morning.lmzpk.cn.gov.cn.lmzpk.cn http://www.morning.srkqs.cn.gov.cn.srkqs.cn http://www.morning.fjntg.cn.gov.cn.fjntg.cn http://www.morning.ygrkg.cn.gov.cn.ygrkg.cn http://www.morning.rnribht.cn.gov.cn.rnribht.cn http://www.morning.lrzst.cn.gov.cn.lrzst.cn http://www.morning.jbhhj.cn.gov.cn.jbhhj.cn http://www.morning.sxjmz.cn.gov.cn.sxjmz.cn http://www.morning.hytqt.cn.gov.cn.hytqt.cn http://www.morning.jsxrm.cn.gov.cn.jsxrm.cn http://www.morning.zhnpj.cn.gov.cn.zhnpj.cn
