山东企业建站软件,旅游网站这么做,南京做中英文网站设计,阐述企业搭建网站的重要性我们约定#xff1a;以下n表示点的数目#xff0c;m表示边的数目。
引子1——邻接表存储图的方法#xff08;#xff09;#xff08;暂时不考虑重边和自环#xff09; 现在我们有n个点#xff08;编号为1~n#xff09;和m条边#xff0c;要用数组存储它们#xff0c… 我们约定以下n表示点的数目m表示边的数目。
引子1——邻接表存储图的方法暂时不考虑重边和自环 现在我们有n个点编号为1~n和m条边要用数组存储它们我们可以怎么做呢我们可以采取逐条加边的方法。假如我们要存储一条从a指向b的长度为w的边注意这里的a、b代表的是端点的具体编号而非端点被加入图中的次序号。为了不与下面的idx“编号”发生混淆我们这里称a、b分别为加入的边的起点和终点的值
const int K ……此处根据题目所给数据范围确定
int h[K],e[K],ne[K],w[K],idx;
void add(int a,int b,int w)
{e[idx] b;ne[idx] h[a];w[idx] w;h[a] idx;
}
//初始化
memset(h,-1,sizeof h);以上便是经典的邻接表加边函数的代码。下面我们详尽解释各变量、数组和代码的含义。至于为什么它们的含义如此我们将在下面的模拟图中看出。 idx:编号下文中的“编号”指的是在e数组中的编号编号是几就是第几加一条被存进数组的边的终点的编号减1。在最后的idx执行完后表示当前图中有idx条边idx1个点下一条要加入的边如果有的话的终点在e数组中的下标为idx。 h数组存储编号的数组。h[k]表示值为k的点指向的下一个点的编号x如果有多个“下一个点”则表示的是最后加入的那一个。这里很多资料说h数组存储的是头节点但实际上h数组的下标的值并不总是某条路径的头因此这种说法是不正确的。 w数组存储边的长度。w[k]表示第k1条被加入的边的长度 ne数组虚拟指针数组。邻接表保证了每个节点除头节点无出边外都必定有入边和出边若某个节点没有真正的出边就让它指向-1。ne[k]表示编号为k的点的下一个点的编号 e数组存储值的数组。e[k]表示第k1条加入的边的终点的值。 那么我们自然可以推导出遍历所有边的代码——
for(int i h[u];i!-1;i ne[i])
………………引子2——邻接矩阵存储图 邻接矩阵存储图较为简单。我们开一个二维数组g其中g[i][j]表示从值为i的点到值为j的点的距离。
一.朴素Dijkstra算法适用于求解稠密图且所有边权威正的单源最短路问题复杂度为On^2 基本思想循环n次找到每个点到起点的最短距离并且用已经更新过的点去更新未被更新的点。
#includeiostream
#includecstring
using namespace std;const int N 510;
//g[i][j]表示点i到点j的距离dis[i]表示当前(注意是当前未必是最小)第i个点到起点的最短距离
int g[N][N],dis[N],n,m;
//isConfirmed集合用于记录某点到起点距离的最小值是否已经被确定
bool isConfirmed[N];int Dijkstra()
{dis[1] 0;//之所以要有最外层循环是因为我们一共有n个点每次我们只能找到一个不在isConfirmed集合里的且离起点最近的点我们一共要找n个这样的点。i k表示当前最短路径上一共有了k个点for(int i 1;in;i){//t表示所有不在已经生成的路径中的点中离起点最近的点初始时未确定因此赋值-1int t -1;//枚举所有点找到不在isConfirmed集合中离起点最近的点赋予给tfor(int j 1;jn;j){if(!isConfirmed[j](t-1||dis[t]dis[j])) t j;}isConfirmed[t] true;//找到不在isConfirmed集合中离起点最近的点后用该点更新它所有相邻点到起点的最短距离for(int j 1;jn;j)dis[j] min(dis[j],g[t][j]dis[t]);}//不要直接返回无穷大否则可能出现无法预料的后果//0x3f和0x3f3f3f3f不同它们仅在用memset初始化时可以互换if(dis[n]0x3f3f3f) return -1;else return dis[n];
}int main()
{//刚开始所有点到起点的距离都还没有确定因此赋值为正无穷memset(dis,0x3f,sizeof dis);cinnm;for(int i 1;in;i){for(int j 1;jn;j){//处理自环if(ij) g[i][j] 0;else g[i][j] 0x3f3f3f;}}while(m--){int x,y,z;cinxyz;//若存在重边取最短边g[x][y] min(g[x][y],z);}printf(%d,Dijkstra());return 0;
}二.堆优化版的Dijkstra算法适用于求解稀疏图且所有边权为正的单源最短路问题复杂度为Omlogn 基本思想在Dijkstra算法中有求不在isConfirmed集合中的到起点距离最短的点的操作这一步可以用堆进行优化。
#includeiostream
#includecstring
#includequeue
using namespace std;
const int N 200000;
int h[N],e[N],ne[N],w[N],dis[N],idx,n,m;
//因为要存储编号和到起点的距离两个量所以要用pair
typedef pairint,int PII;
bool isConfirmed[N];int add(int a,int b,int c)
{e[idx] b;ne[idx] h[a];//这里是w[idx]而非w[b]w[k]表示第k条边的长度w[idx] c;h[a] idx;
}int Dijkstra()
{dis[1] 0;//定义小根堆priority_queuePII, vectorPII, greaterPII heap; //把起点放进堆中//这个顺序不能倒。因为heap首先是根据距离排序而不是点的编号heap.push({0,1});//由于堆中存的是不在isConfirmed集合中的点当堆不空意味着还有没确定最短距离的点while(heap.size()){//取出堆顶这就是当前不在isConfirmed集合中距离起点最近的点这里的“距离”并不指最终的最短距离而是更新到当前为止的最短距离PII t heap.top();heap.pop();int number t.second;int distance t.first;//这句话必不可少。因为若number这个点到起点的最短距离已经确定我们再进行操作的话会导致复杂度增加.为了不爆TLE我们应该在操作完毕后停止if(isConfirmed[number] true) continue;isConfirmed[number] true;//用当前不在isConfirmed集合中且离起点最近的点来更新它能到达的点到起点的最短距离for(int i h[number];i!-1;i ne[i]){//得到当前点的编号int j e[i];//如果j到起点的最短距离已经被确定就不用继续做下去了if(!isConfirmed[j]dis[j]distancew[i]){dis[j] distancew[i];//在这一步重边和自环被无形中处理掉了。若有重边只有长度最短的那一条边对应的距离会进堆。heap.push({dis[j],j});//这里不能写isConfirmed[j] true。因为j的“最短”只是暂时的是当前已经生成的最短路径下到起点的最小值}}}if(dis[n]0x3f3f3f3f) return -1;else return dis[n];
}int main()
{memset(dis,0x3f,sizeof dis);memset(h,-1,sizeof h);scanf(%d%d,n,m);while(m--){int x,y,z;scanf(%d%d%d,x,y,z);add(x,y,z);}coutDijkstra();return 0;
}
三.Bellman_ford算法适用于求解存在负权边或限制经过的边数的单源最短路问题复杂度为Onm #includeiostream
#includecstring
using namespace std;
const int K 10010;
//这里也可以用结构体数组存
int backup[K],dist[K],n,m,k;struct Edge
{int a,b,w;
}edges[K];bool bellman_ford()
{memset(dist,0x3f,sizeof dist);dist[1] 0;for(int i 1;ik;i){memcpy(backup,dist,sizeof dist);//这里j开始的下标要和main函数中i开始的下标相同这样才访问到edges数组的同一个地方for(int j 1;jm;j)//遍历所有边每条边终点到源点的最短距离等于该点到源点的直接距离与该边起点到源点的最短距离和该边长度的和的较小值//j是编号不是值这样恰好符合dist数组的定义。dist[k]表示编号为k这里的编号指的是该点第几个被插入的点到源点的最短距离。edges[j].w指的是跟第j个出现被输入的点相连的边的长度dist[edges[j].b] min(dist[edges[j].b],backup[edges[j].a]edges[j].w);}//这里由于可能出现负权边导致dist[n]被更新成比0x3f3f3f3f小一点的数但是又不会小太多所以我们改为dist[n]比某个较大的数大就可以认为它是正无穷了。if(dist[n]0x3f3f3f/2) return false;else return true;
}int main()
{cinnmk;for(int i 1;im;i)cinedges[i].aedges[i].bedges[i].w;if(!bellman_ford()) coutimpossible;else coutdist[n];return 0;
}四.spfa算法Bellman_ford的优化版。一般情况下复杂度为Om最坏为Onm #includeiostream
#includequeue
#includecstring
using namespace std;
const int K 100010;
int h[K],e[K],ne[K],w[K],dist[K],n,m,idx;
bool isInQueue[K];void add(int a,int b,int c)
{e[idx] b;ne[idx] h[a];w[idx] c;h[a] idx;
}bool spfa()
{memset(dist,0x3f,sizeof dist);dist[1] 0;//队列用于存储可以更新别的距离的点queueint q;q.push(1);isInQueue[1] true;//当队列不空说明我们还有材料更新别的点说明我们的最短距离未全部确定while(q.size()){int t q.front();q.pop();isInQueue[t] false;for(int i h[t];i!-1;i ne[i]){int j e[i];if(dist[j]dist[t]w[i]){dist[j] dist[t]w[i];if(!isInQueue[j]){q.push(j);isInQueue[j] true;}}}}if(dist[n] 0x3f3f3f3f/2) return false;else return true;}int main()
{memset(h,-1,sizeof h);cinnm;while(m--){int x,y,z;cinxyz;add(x,y,z);}if(!spfa()) puts(impossible);else coutdist[n];return 0;
}
五.floyd算法求解多源头最短路问题 #includeiostream
using namespace std;
const int N 210,M 20010;
int g[N][N],n,m,k;void floyd()
{for(int k 1;kn;k)for(int i 1;in;i)for(int j 1;jn;j)g[i][j] min(g[i][j],g[i][k]g[k][j]);
}int main()
{cinnmk;for(int i 1;in;i){for(int j 1;jn;j){if(ij) g[i][j] 0;else g[i][j] 0x3f3f3f3f;}}while(m--){int x,y,z;cinxyz;g[x][y] min(g[x][y],z);}floyd();while(k--){int x,y;cinxy;if(g[x][y]0x3f3f3f3f/2) coutimpossibleendl;else coutg[x][y]endl;}return 0;}六.Prim算法用于求最小生成树复杂度On^2 最小生成树是怎么生成的呢我们看下面一个图就明白了。 我们用S表示所有在已有连通块即生成树中的点构成的集合。最开始还没有生成树点1、2、3、4到连通块的距离均为正无穷。然后选取一个距离已有连通块这时为空最近这时1、2、3、4都是正无穷一样近那就选1好了的点加入到连通块中并用这个点更新其它在连通块外的点到连通块的距离。某点到连通块的距离定义为该点到连通块中所有点的距离的最小值以此类推我们可以得到最小生成树。Prim算法的想法与Dijkstra类似循环n次每次找到不在连通块中且离连通块最近的点。具体的代码实现如下——
#includeiostream
#includecstring
using namespace std;
const int N 510;
//因为边的数量较多(~N^2)这里我们用邻接矩阵来存储图
int g[N][N],dist[N],n,m,res;
bool isInTree[N];
int prim()
{memset(dist,0x3f,sizeof dist);//这里不能初始化dist[1]为0.因为此时还没有连通块dist[1]也应该被看作正无穷//尽可能把所有点都包进连通块中for(int i 0;in;i){int t -1;//找到当前不在连通块中离连通块最近的点for(int j 1;jn;j)if(!isInTree[j](t-1||dist[t]dist[j])) t j;//如果此时找到的最短距离都是无穷大那么说明此时剩下的所有点根连通块都是不连通的就返回正无穷表示不存在生成树//如果找到的不是第一个点(第一个点编号为0)而且到已有连通块的距离为正无穷说明不连通。为什么要排除第一个点呢因为第一个点到已有连通块的距离本来就应该是负无穷因为彼时还没有连通块。if(idist[t]0x3f3f3f3f) return 0x3f3f3f3f;if(i) resdist[t];isInTree[t] true;//遍历t的所有邻边用这个找到的离连通块最近的点更新其它点到连通块的距离for(int j 1;jn;j)//这里不需要像Dijkstra那样再加上dist[t]因为dist[i]表示第i个点到已有连通块的距离而非源点的距离。既然t已经在连通块中那么只要取dist[i]和个g[t][j]中的较小值即可dist[j] min(dist[j],g[t][j]);}return res;
}int main()
{//先输入再初始化cinnm;for(int i 1;in;i){for(int j 1;jn;j){if(ij) g[i][j] 0;else g[i][j] 0x3f3f3f3f;}}while(m--){int u,v,w;cinuvw;g[u][v] g[v][u] min(g[u][v],w);}int l prim();if(l0x3f3f3f3f) puts(impossible);else coutl;return 0;
}七.Kruskal算法用于求最小生成树复杂度Omlogn Kruskal算法的想法很简单就是将所有边按照边长从小到大排序然后再枚举每条边即可。
#include cstring
#include iostream
#include algorithmusing namespace std;const int N 100010, M 200010, INF 0x3f3f3f3f;int n, m;
int p[N];
//用结构体存储所有边和点即可不用邻接表或邻接矩阵
struct Edge
{int a, b, w;
//重载小于号按照边的长度将所有边排序bool operator (const Edge W)const{return w W.w;}
}edges[M];
//并查集模板寻找祖宗节点
int find(int x)
{if (p[x] ! x) p[x] find(p[x]);return p[x];
}int kruskal()
{//按照边的长度将所有边排序sort(edges, edges m);for (int i 1; i n; i ) p[i] i; // 初始化并查集
//res表示所有边的长度之和int res 0, cnt 0;//从小到大枚举每条边for (int i 0; i m; i ){int a edges[i].a, b edges[i].b, w edges[i].w;
//如果a和b的祖宗节点不同说明不在同一个连通块中这时候就把它们连起来
//cnt表示当前生成树中边的条数a find(a), b find(b);if (a ! b){p[a] b;res w;cnt ;}}if (cnt n - 1) return INF;return res;
}int main()
{scanf(%d%d, n, m);for (int i 0; i m; i ){int a, b, w;scanf(%d%d%d, a, b, w);edges[i] {a, b, w};}int t kruskal();if (t INF) puts(impossible);else printf(%d\n, t);return 0;
}
