投稿
  1. 首页
  2. C

图论算法整理

code • 2022-4-25 • C • 阅读 47

图论算法整理,第1张

图论算法整理

图算法专题的一些基础知识。

文章目录
  • 图论算法整理
  • 一、图的遍历
  • 二、最短路算法
    • 1.Dijkstra算法
    • 2.Bellman-Ford和SPFA算法
    • 3.Floyd算法
  • 三、最小生成树算法
    • 1.prim算法
    • 2.kruskal算法
  • 四、拓扑排序
  • 总结

一、图的遍历
  1. DFS
    深度优先搜索：采用递归实现，访问当前节点，然后对于所有该节点的出边。如果出边的端点没有被访问过则递归访问该节点。
#include 
#include 
using namespace std;
#define MAXV 1000
#define INF 1e9
//邻接矩阵版
int n;
int G[MAXV][MAXV];
bool vis[MAXV]={false};
void dfs_adjmatrix(int u, int depth){
    vis[u]=true;
    for(int v=0;v<n;v++){
        if(vis[v]==false&&G[u][v]!=INF){
            dfs_adjmatrix(v, depth+1);
        }
    }
}
void dfs_trave(){
    for(int u=0;u<n;u++){
        if(vis[u]==false){
            dfs_adjmatrix(u, 1);
        }
    }
}


//邻接表版
vector<int> Adj[MAXV];
int n; //n为顶点数
bool vis[MAXV]={false};
void dfs_adjvec(int u, int depth){
    vis[u]=true;
    for(int i=0;i<Adj[u].size();i++){
        int v=Adj[u][i];
        if(vis[v]==false){
            dfs_adjvec(v, depth+1);
        }
    }
}

void dfsTrave_vec(){
    for(int u=0;u<n;u++){
        if(vis[u]==false){
            dfs_adjvec(u, 1);
        }
    }
}
  1. BFS
    使用队列实现广度优先遍历，先访问源点，再使用while循环，每次都将当前访问节点u的所有未访问过的邻接点加入到队列中去，直至队列为空。
#include 
#include 
#include 
using namespace std;
//邻接矩阵版
#define MAXV 1000
#define INF 1e9
int n, G[MAXV][MAXV];
bool inq_1[MAXV]={false};
void BFS_1(int u){
    queue<int> q;
    q.push(u);
    inq_1[u]=true;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int v=0;v<n;v++){
            if(inq_1[v]==false&&G[u][v]!=INF){
                q.push(v);
                inq_1[v]=true;
            }
        }
    }
}
void bFSTrave_1(){
    for(int u=0;u<n;u++){
        if(inq_1[u]==false){
            BFS_1(u);
        }
    }
}
//邻接表版
vector<int> Adj[MAXV];
int n;
bool inq_2[MAXV]={false};
void BFS_2(int u){
    queue<int> q;
    q.push(u);
    inq_2[u]=true;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<Adj[u].size();i++){
            int v=Adj[u][i];
            if(inq_2[v]==false){
                q.push(v);
                inq_2[v]=true;
            }
        }
    }
}

void BFSTrave_2(){
    for(int u=0;u<n;u++){
        if(inq_2[u]==false){
            BFS_2(u);
        }
    }
}
二、最短路算法 1.Dijkstra算法

朴素版本的dijkstra算法：
（1）初始化：将vis数组标记为未访问，将dis数组标记为INF。然后将dis[s]置为0.
（2）n次循环：每次从未访问过的点中找出一个距离源点s最近的点，置为已访问，然后松弛和这个点相连的所有边的端点（未而访问过的）。如果找不到这个点，说明剩下的图已经不连通。

#include 
#include 
#include 
using namespace std;
#define MAXV 1005
#define INF 1e9
//邻接表版本
struct Node{
    int v;
    int w;
};
vector<Node> Adj[MAXV];
int pre_1[MAXV]; //前驱节点
int n, dis[MAXV];
bool vis[MAXV]={false};
void Dijkstra(int s){
    fill(dis, dis+MAXV, INF); //注意
    dis[s]=0;
    for(int i=0;i<n;i++){
        int u=-1;
        int MIN=INF;
        for(int j=0;j<n;j++){
            if(vis[j]==false&&dis[j]<MIN){
                u=j;
                MIN=dis[j];
            }
        }
        if(u==-1) return ;//说明剩下的已经不和s连通了
        vis[u]=true;
        for(int j=0;i<Adj[u].size();j++){
            int v=Adj[u][j].v;
            int w=Adj[u][j].w;
            if(vis[v]==false&&dis[u]+w<dis[v]){
                dis[v]=dis[u]+w;
            }
        }
    }
}

//打印路径
void dfs(int s, int v){ //s为起点编号，v为当前访问的顶点编号
    if(v==s){
        printf("%d\n", s); //如果已经到达起点则返回
        return ;
    }
    dfs(s, pre_1[v]);
    printf("%d\n", v); //从最深处return回来之后，输出每一层的顶点号
}

//第二标尺
int st;
int ed;
int optvalue; //第二标尺最优值
vector<int> pre[MAXV];
vector<int> path, tempPath;
void DFS(int v){
    if(v==st){
        tempPath.push_back(v);
        int value;
        //计算tempPath上的value值
        if(value>optvalue){
            //更优
            optvalue=value;
            path=tempPath;
        }
        tempPath.pop_back(); //将刚加入的节点删除
        return ;
    }
    tempPath.push_back(v);
    for(int i=0;i<pre[v].size();i++){
        DFS(pre[v][i]);
    }
    tempPath.pop_back(); //遍历完所有前驱节点，将当前节点v删除
}

使用堆优化后的dijkstra算法：
堆优化的dijkstra算法，优化的点在于每次选取距离源点最近的点的时候使用优先队列来实现（小顶堆）。
两种实现方式：
（1）使用pair的排序特性, pair<-d[u], u> 构建小顶堆，即将距离源点的距离取相反数加入到队列中去。

priority_queue<pair<int, int>> q;

（2）使用结构体，自定义/重载<符号。
首先将源点加入到优先队列中去，然后设立vis数组，每次松弛后变小的点加入到队列中去。pop的时候如果已经访问过就跳过。

#include 
#include 
#include 
#include 
using namespace std;
const int N=1e5+10;
int n;
int dis[N];
bool vis[N];
struct node{
    int index;
    int dist;
    bool operator <(const node& x) const{
        return dist>x.dist;
    }
};
vector<node> adj[N];
priority_queue<node> q;
void dijkstra(int s){
    memset(dis, 0x3f, sizeof(dis));
    dis[s]=0;
    node now;
    now.index=s;
    now.w=0;
    q.push(now);
    while (!q.empty())
    {
        int u=q.top().index;
        q.pop();
        if(vis[u]==true) continue;
        vis[u]=true;
        for(int i=0;i<adj[u].size();i++){
            int v=adj[u][i].index;
            int w=adj[u][i].dist;
            if(w+dis[u]<dis[v]){
                dis[v]=dis[u]+w;
                now.index=v;
                now.dist=dis[v];
                q.push(now);
            }
        }
    }
}
2.Bellman-Ford和SPFA算法

bellman-ford算法可用于解决单源最短路径问题，包括权值为负的情况。
进行n-1轮松弛，每次都对所有点进行松弛。
n-1轮后如果还可以松弛，说明存在负环。
代码如下：

#include 
#include 
#include 
using namespace std;
#define MAXV 1005
#define INF 0x3fffffff
struct node{
    int v;
    int cost;
};
vector<node> adj[MAXV];
int n; //顶点数
int d[MAXV]; //起点S到个点的最短距离
bool bellmanFord(int s){
    fill(d, d+MAXV, INF);
    d[s]=0;
    for(int i=0;i<n-1;i++){
        //n-1轮松弛
        for(int u=0;u<n;u++){
            for(int j=0;j<adj[u].size();j++){
                int v=adj[u][j].v;
                int w=adj[u][j].cost;
                if(d[u]+w<d[v]){
                    d[v]=d[u]+w;
                }

            }
        }
    }
    //判断是否存在负环
    //对每条边进行判断
    for(int u=0;u<n;u++){
        for(int j=0;j<adj[u].size();j++){
            int v=adj[u][j].v;
            int w=adj[u][j].cost;
            if(d[u]+w<d[v]){
                return false;
            }
        }
    }
    return true;
}

SPFA算法
使用队列实现。

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define MAXV 1005
#define INF 0x3fffffff
struct node{
    int v;
    int cost;
};
//BFS版本的SPFA
//可尝试DFS版本的SPFA
vector<node> adj[MAXV];
int d[MAXV];
bool inq[MAXV];//顶点是否在队列中
int num[MAXV]; //num数组记录顶点的入队次数
int n;
bool SPFA(int s){
    //初始化
    memset(inq, false, sizeof(inq));
    memset(num, 0, sizeof(num));
    fill(d, d+MAXV, INF);
    //源点入队列
    queue<int> Q;
    Q.push(s);
    inq[s]=true;
    num[s]++;
    d[s]=0;
    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
        inq[u]=false;
        //遍历u的所有邻接边v
        for(int j=0;j<adj[u].size();j++){
            int v=adj[u][j].v;
            int w=adj[u][j].cost;
            //松弛 *** 作
            if(d[u]+w<d[v]){
                d[v]=d[u]+w;
                if(inq[v]==false){
                    //不在队列中才能入队
                    Q.push(v);
                    inq[v]=true;
                    num[v]++;
                    if(num[v]>=n){
                        return false; //有源点可达负环
                    }
                }
            }
        }
    }
    return true; //无可达负环
}
3.Floyd算法 
#include 
#include 
#include 
#include 
using namespace std;
#define INF 0x3fffffff
#define MAXV 10010
int n, m;
int dis[MAXV][MAXV]; //表示顶点i到顶点j的最短距离

//注意k不能放到内层（i->j->k)，否则前面的dis[i][j]因为已经访问过而无法再进行优化

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(void){
    int u, v, w;
    fill(dis[0], dis[0]+MAXV*MAXV, INF); //dis数组赋初值INF
    scanf("%d%d", &n,&m);
    for(int i=0;i<n;i++){
        dis[i][i]=0;
    }
    for(int i=0;i<m;i++){
        scanf("%d%d%d", &u, &v, &w);
        dis[u][v]=w; //以有向图为例进行输入
    }
    Floyd();
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            printf("%d ", dis[i][j]);
        }
        printf("\n");
    }
    return 0;

}
三、最小生成树算法 1.prim算法

适用于稠密图。

在这里插入代码片#include <iostream>
#include 
#include 
using namespace std;
#define MAXV 1005
#define INF 0x3fffffff
struct node{
    int v;
    int w;
};
vector<node> adj[MAXV];
int n;
int d[MAXV]; //顶点和集合S的距离
bool vis[MAXV]={false}; //标记数组
int prim(){
    fill(d, d+MAXV, INF);
    d[0]=0;//选取0号点作为初始集合S中的顶点
    long long int ans=0;
    //循环n次
    for(int i=0;i<n;i++){
        //每次先找到一个距离集合S最近的点
        int u=-1;
        int MIN=INF;
        for(int j=0;j<n;j++){
            if(vis[j]==false&&d[j]<MIN){
                u=j;
                MIN=d[j];
            }
        }
        if(u==-1) return -1;
        vis[u]=true;
        ans+=d[u];
        //加入集合S，松弛临近点
        for(int j=0;j<adj[u].size();j++){
            int v=adj[u][j].v;
            int w=adj[u][j].w;
            if(vis[v]==false&&w<d[v]){
                d[v]=+w;
            }  
        }
    }
    return ans;

}
2.kruskal算法

适用于稀疏图。

#include 
#include 
#include 
using namespace std;
#define MAXV 1005
#define MAXE 10010
#define INF 0x3f3f3f3f
struct edge{
    int u, v;
    int cost;
}E[MAXE];
bool cmp(edge a, edge b)
{
    return a.cost<b.cost;
}
//并查集部分
int father[MAXV];
int findFather(int x){
    int a=x;
    while(x!=father[x]){
        x=father[x];
    }
    while (a!=father[a])
    {
        int z=a;
        a=father[a];
        father[z]=x;
    }
    return x;
}

int kruskal(int n, int m){
    long long int ans=0;
    int Num_Edge=0;
    for(int i=0;i<n;i++){
        father[i]=i;//初始化，每个点都是一个连通块
    }
    sort(E, E+m, cmp);
    for(int i=0;i<m;i++){
        //按照边权从小到大依次枚举所有边
        int faU=findFather(E[i].u);
        int faV=findFather(E[i].v);
        if(faU!=faV){
            //两个连通块
            father[faU]=faV;
            ans+=E[i].cost;
            Num_Edge++;
            if(Num_Edge==n-1){
                break;
            }
        }
    }
    if(Num_Edge!=n-1){
        return -1;
    }else{
        return ans;
    }
}

int main(void){
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i=0;i<m;i++){
        scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].cost);
    }
    int ans=kruskal(n, m);
    printf("%d\n", ans);
    return 0;
}
四、拓扑排序

代码如下：

#include 
#include 
#include 
using namespace std;
#define MAXV 10010
vector<int> G[MAXV];//邻接表
int n, m, inDegree[MAXV]; //顶点数、边数、入度
//拓扑排序
bool topologicalSort(){
    int num=0;//记录加入拓扑序列的顶点数
    queue<int> q; 
    for(int i=0;i<n;i++){
        if(inDegree[i]==0){
            q.push(i); //将所有入度为0的顶点入队
        }
    }
    while(!q.empty()){
        int u=q.front(); //取队首顶点u
        //printf("%d", u); //此处可输出顶点u，作为拓扑序列中的顶点
        q.pop();
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i]; //u的后继节点v
            inDegree[v]--; //顶点v的入度减1
            if(inDegree[v]==0){
                q.push(v); //顶点v的入度减为0则入队
            }
        }
        G[u].clear(); //清空顶点u的所有出边
        num++;   //加入拓扑序列的顶点数加1
    }
    if(num==n) return true; //加入拓扑序列的定点数为n,说明拓扑成功
    else return false; //加入拓扑序列的顶点数小于n，说明拓扑排序失败
}
总结

待补充：

上述算法都只是比较基础的算法，具体的优化待补充。

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/716986.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-04-25
下一篇 2022-04-25

发表评论

登录后才能评论

评论列表（0条）

保存