当前位置: 代码迷 >> 综合 >> 图论小总结
  详细解决方案

图论小总结

热度:85   发布时间:2024-01-16 20:14:36.0

这几天一直在看图论的东西,什么Dijkstra,Floyd,Prim,Kruskal等等的东西吧,之前总感觉这些东西好难,也就没怎么看,这段时间接触多了,每天都看那么一丢丢,感觉真的也就那么回事,什么东西都是要一点一点去学,慢慢的去掌握的不是么,所以看了好几天的东西,今天想花点时间去总结一次,就当做省赛前的小放松了,哈哈,其实平常也挺放松的.......好了,进入正题吧!


Dijkstra算法

Dijkstra算法是典型的  单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是 以起点为中心向外层扩展,直到扩展到终点为止。特别注意的是   Dijkstra算法要求图中不存在负权边。

 Dijkstra单源最短路 邻接矩阵形式

/**  单源最短路径,Dijkstra算法,邻接矩阵形式,复杂度为O(n^2)*  求出源beg到所有点的最短路径,传入图的顶点数和邻接矩阵cost[][]*  返回各点的最短路径lowcost[],路径pre[],pre[i]记录beg到i路径上的父节点,pre[beg] = -1*  可更改路径权类型,但是权值必须为非负,下标0~n-1*/
const int MAXN = 1010;
const int INF = 0x3f3f3f3f; //  表示无穷
bool vis[MAXN];
int pre[MAXN];void Dijkstra(int cost[][MAXN], int lowcost[], int n, int beg)
{for (int i = 0; i < n; i++){lowcost[i] = INF;vis[i] = false;pre[i] = -1;}lowcost[beg] = 0;for (int j = 0; j < n; j++){int k = -1;int min = INF;for (int i = 0; i < n; i++){if (!vis[i] && lowcost[i] < min){min = lowcost[i];k = i;}}if (k == -1){break;}vis[k] = true;for (int i = 0; i < n; i++){if (!vis[i] && lowcost[k] + cost[k][i] < lowcost[i]){lowcost[i] = lowcost[k] + cost[k][i];pre[i] = k;}}}
}
Dijkstra 单源最短路 邻接矩阵形式 双路径信息
/*
*单源最短路径,dijkstra算法,邻接矩阵形式,复杂度为o(n^2)
*两点间距离存入map[][],两点间花费存入cost[][]
*求出源st到所有点的最短路径及其对应最小花费
*返回各点的最短路径lowdis[]以及对应的最小花费lowval[]
*可更改路径权类型,但是权值必须为非负,下标1~n
*/
const int MAXN=1010;
const int INF=0x3f3f3f3f;int n,m;int lowdis[MAXN];
int lowval[MAXN];
int visit[MAXN];
int map[MAXN][MAXN];
int cost[MAXN][MAXN];void dijkstra(int st)
{int temp=0;for(int i=1;i<=n;i++){lowdis[i]=map[st][i];lowval[i]=cost[st][i];}memset(visit,0,sizeof(visit));visit[st]=1;for(int i=1;i<n;i++){int MIN=INF;for(int j=1;j<=n;j++){if(!visit[j]&&lowdis[j]<MIN){temp=j;MIN=lowdis[j];}}visit[temp]=1;for(int j=1;j<=n;j++){if(!visit[j]&&map[temp][j]<INF){if(lowdis[j]>lowdis[temp]+map[temp][j]){lowdis[j]=lowdis[temp]+map[temp][j];lowval[j]=lowval[temp]+cost[temp][j];}else if(lowdis[j]==lowdis[temp]+map[temp[j]){if(lowval[j]>lowval[temp]+cost[temp][j]){lowval[j]=lowval[temp]+cost[temp][j];}}}}}return;}

Dijkstra起点Strat结点有权值

#define M 505
const int inf=0x3f3f3f3f;
int num[M];    //结点权值
int map[M][M];  //图的临近矩阵
int vis[M];     //结点是否处理过
int ans[M];     //最短路径结点权值和
int dis[M];     //各点最短路径花费
int n,m,Start,End;    //n结点数,m边数,Start起点,End 终点void Dij(int v)
{ans[v]=num[v];memset(vis,0,sizeof(vis));for(int i=0;i<n;i++){if(map[v][i]<inf){ans[i]=ans[v]+num[i];}dis[i]=map[v][i];}dis[v]=0;vis[v]=1;for(int i=1;i<n;i++){int u=0,min=inf;for(int j=0;j<n;j++){if(!vis[j]&&dis[j]<min){min=dis[j];u=j;}}vis[u]=1;for(int k=0;k<n;k++){if(!vis[k]&&dis[k]>map[u][k]+dis[u]){dis[k]=map[u][k]+dis[u];ans[k]=ans[u]+num[k];}}for(int k=0;k<n;k++){if(dis[k]==map[u][k]+dis[u]){ans[k]=max(ans[k],ans[u]+num[k]);}}}printf("%d %d\n",dis[End],ans[End]);//输出终点最短路径花费、最短路径结点权值和
}
int main()
{scanf("%d%d%d%d",&n,&m,&Strat,&End);for(int i=0;i<n;i++)scanf("%d",&num[i]);memset(vis,0,sizeof(vis));memset(map,0x3f,sizeof(map));for(int i=0;i<m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);if(map[x][y]>z){map[x][y]=z;map[y][x]=z;}}Dij(Start);return 0;
}

Floyd算法

Floyd-Warshallsu算法是解决任意两点间的最短路径的一种算法,可以处理有向图或负权的最短路径问题,同时也被用于计算有向图的传递闭包。

算法描述:

      a)从任意一条单边路径开始。所有两点之间的距离是边的权,如果两点之间没有相连,则权为无穷大。

      b)对于每一对定点u和v,看看是否存在一个顶点w使得从u到w再到v比已知的路径更短.如果是,那么就更新它.


Floyd算法 邻接矩阵形式

/*
*Floyd算法,求从任意节点i到任意节点j的最短路径
*cost[][]:初始化为INF(cost[i][i]:初始化为0)
*lowcost[][]:最短路径,path[][]:最短路径(无限制)
*/
const int MAXN=100;
int cost[MAXN][MAXN];
int lowcost[MAXN][MAXN];
itn path[MAXN][MAXN];
void Floyd(int n)
{memcpy(lowcost,cost,sizeof(cost));memset(path,-1,sizeof(path));for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++){if(lowcost[i][j]>(lowcost[i][k]+lowcost[k][j])){lowcost[i][j]=lowcost[i][k]+lowcost[k][j];path[i][j]=k;}   }
}

Floyd算法 点权 + 路径限制

/*Floyd算法,求任意节点i到任意节点j的最短路径
*cost[][]:初始化为INF(cost[i][i]:初始化为0)
*val[]:点权,lowcost[][]:除起点,终点外的点权之和+最短路径
*path[][]:路径限制,要求字典序最小的路径,下表1~N
*/
const int MAXN=110;
const int INF=0x3f3f3f3f;
int val[MAXN];  //点权
int cost[MAXN][MAXN];
int lowcost[MAXN][MAXN];
int path[MAXN][MAXN];  //i~j路径中第一个结点
void Floyd(int n)
{memccpy(lowcost,cost,sizeof(cost));for(itn i=0;i<=n;i++){for(int j=0;j<=n;j++){path[i][j]=j;}}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){int temp=lowcost[i][k]+lowcost[k][j]+val[k];if(lowcost[i][j]>temp){lowcost[i][j]=temp;path[i][j]=path[i][k];}else if(lowcost[i][j]==temp&&path[i][j]>path[i][k])path[i][j]=path[i][k];}return;
}
Prim算法
prim算法:每次选取一条边,该边满足:1.一端已选,一端未选;2.该边权值最小。

算法描述:Prim只与定点有关,求最小生成树的时候,和边数无关,只和定点的数量相关,所以适合求稠密网的最小生成树

/**  Prim求MST*  耗费矩阵cost[][],初始化为INF,标号从0开始,0 ~ n-1*  返回最小生成树的权值,返回-1表示原图不连通*/const int INF = 0x3f3f3f3f;
const int MAXN = 110;
bool vis[MAXN];
int lowc[MAXN];
int cost[MAXN][MAXN];//  修正cost(添加边)
void updata(int x, int y, int v)
{cost[x - 1][y - 1] = v;cost[y - 1][x - 1] = v;return ;
}int Prim(int cost[][MAXN], int n)   //  0 ~ n - 1
{int ans = 0;memset(vis, false, sizeof(vis));vis[0] = true;for (int i = 1; i < n; i++){lowc[i] = cost[0][i];}for (int i = 1; i < n; i++){int minc = INF;int p = -1;for (int j = 0; j < n; j++){if (!vis[j] && minc > lowc[j]){minc = lowc[j];p = j;}}if (minc == INF){return -1;  //  原图不连通}ans += minc;vis[p] = true;for (int j = 0; j < n; j++){if (!vis[j] && lowc[j] > cost[p][j]){lowc[j] = cost[p][j];}}}return ans;
}
Kruskal算法
在带权连通图中,不断地在边集合中找到最小的边,如果该边满足得到最小生成树的条件,就将其构造,直到最后得到一颗最小生成树。    

克鲁斯卡尔算法的执行步骤:
       第一步:在带权连通图中,将边的权值排序;
       第二步:判断是否需要选择这条边(此时图中的边已按权值从小到大排好序)。判断的依据是边的两个顶点是否已连通,如果连通则继续下一条;如果不连通,那么就选择使其连通。
       第三步:循环第二步,直到图中所有的顶点都在同一个连通分量中,即得到最小生成树。

/**  Kruskal算法求MST*  对边操作,并排序*  切记:初始化赋值问题(tol)*/const int MAXN = 110;   //  最大点数
const int MAXM = 10000; //  最大边数int F[MAXN];    //  并查集使用struct Edge
{int u;      //  起点int v;      //  终点int w;      //  权值
} edge[MAXM];   //  存储边的信息int tol;        //  边数,加边前赋值为0void addEdge(int u, int v, int w)
{edge[tol].u = u;edge[tol].v = v;edge[tol++].w = w;return ;
}bool cmp(Edge a, Edge b)
{//  排序函数,将边按照权值从小到大排序return a.w < b.w;
}int find(int x)
{if (F[x] == x){return x;}else{return F[x] = find(F[x]);}
}int Kruskal(int n)  //  传入点数,返回最小生成树的权值,如果不连通则返回-1
{for (int i = 0; i <= n; i++){F[i] = i;}sort(edge, edge + tol, cmp);int cnt = 0;    //  计算加入的边数int ans = 0;for (int i = 0; i < tol; i++){int u = edge[i].u;int v = edge[i].v;int w = edge[i].w;int tOne = find(u);int tTwo = find(v);if (tOne != tTwo){ans += w;F[tOne] = tTwo;cnt++;}if (cnt == n - 1){break;}}if (cnt < n - 1){return -1;  //  不连通}else{return ans;}
}










  相关解决方案