投稿
  1. 高性能架构探索首页
  2. C/C++

数据结构-图编程知识详细总结C++（图创建、图遍历、最短路径、拓扑排序、关键路径）

admin • • C/C++ • 阅读 161

一、图的存储

  • 邻接矩阵，适用于节点数不超过1000个的情况：
const int MAXV = 1000;
int n;
const int INF = 1000000000;
int G[MAXV][MAXV];
bool vis[MAXV] = {false};
  • 邻接表
const int MAXV;
int n;
struct node{
    int id, v;
}
vector<int> Adj[MAXV];
vector<node> Adj[MAXV];
bool vis[MAXV] = {false};

二、基本遍历（DFS、BFS）

1、DFS

  • 邻接矩阵版：主要是G邻接矩阵的初始化，使用fill函数, fill(G[0], G[0] + MAXV * MAXV, INF);
  • 以及在判断的时候加上如果两点间距离为INF，表示不连通
fill(G[0], G[0] + MAXV*MAXV, INF);
void DFS(int u){
    vis[u] = true;
    for(int i = 0; i < n; i++){
        if(vis[i] == false && G[u][i] != INF){
            DFS(i);
        }
    }
}
void DFSTrave(){
    for(int u = 0; u < n; u++){
        if(vis[u] == false){
            DFS(u);
        }
    }
}
  • 邻接表版:如果是使用DFS的邻接表，一般是尽量不含有其他参数的，不然尽量使用BFS。
vector<int> Adj[MAXV];
void DFS(int u){
    vis[u] = true;
    for(int v = 0; v < Adj[u].size(); v++){
        if(vis[Adj[u][v]] == false){
            DFS(Adj[u][v]);
        }
    }
}
void DFSTrave(){
    for(int v = 0; v < n; v++){
        if(vis[v] == false){
            DFS(v);
        }
    }
}

2、BFS

  • 邻接表版
struct node{
    int id, v;
}
bool vis[MAXV] = {false};
vector<node> Adj[MAXV];
void BFS(int u){
    queue<int> q;
    q.push(u);
    vis[u] = true;
    while(!q.empty()){
        int now = q.front();
        //进行操作
        for(int v = 0; v < Adj[now].size(); v++){
            int id = Adj[u][v].id;
            if(vis[id] == false){
                q.push(id);
                vis[id] = true;
            }
        }
    }
}

一些需要注意的点

  • 如果是那种深度有限的遍历，统计结果最好使用BFS，因为DFS可能出现结果重复，以及缺点的情况。
  • 还有就是统计连通块的数量，也就是需要添加的路径使得整个区域连接起来，就是连通块的数量减一；

三、最短路径

1. Dijkstra算法（迪杰斯特拉算法）

  • 用于解决单源最短路径问题（无负权图）。
  • 邻接矩阵版本
const int MAXN;
const int INF = 1000000000;
int G[MAXN][MAXN];
int d[MAXN];
bool vis[MAXN] = {false};
int n;
void Dijkstra(int s){
    fill(d, d + MAXN, INF);
    d[s] = 0;
    for(int i = 0; i < n; i++){
        int u = -1, MIN = INF;
        for(int j = 0; j < n; j++){
            if(d[j] < MIN && vis[j] == false){
                u = j;
                MIN = d[j];
            }
        }
        if(u == -1) return;
        vis[u] = true;
        for(int j = 0; j < n; j++){
            if(vis[j] == false && G[u][j] != INF && d[u] + G[u][j] < d[j]){
                d[j] = d[u] + G[u][j];
            }
        }
    }
}
  • 邻接表版本
struct node{
    int v, dis;
};
vector<node> G[MAXV];
int n;
int d[MAXV];
bool vis[MAXV] = {false};

void Dijkstra(int s){
    fill(d, d + MAXV, INF);
    d[s] = 0;
    for(int i = 0; i < n; i++){
        int u = -1, MIN = INF;
        for(int j = 0; j < n; j++){
            if(d[j] < MIN && vis[j] == false){
                u = j;
                MIN = d[j];
            }
        }
        if(u == -1) return;
        vis[u] = true;
        for(int i = 0; i < G[u].size(); i++){
            int v = G[u][i].v;
            if(vis[v] == false && d[u] + G[u][i].dis < d[v]){
                d[v] = d[u] + G[u][i].dis;
            }
        }
    }
}
2) 对于一些情况的改进，如加上点权和边权
  • 加新的边权的权值
  • 城市点的花费，新增判断，首先是以第一标准为判断条件，如果出现第一判断条件相等，那么再使用第二条件进行判断；记得初始化起点的权值为当前的权值
  • 最短路径的条数:使用一个path数组进行存储，如果出现路径小于，就用上面的路径覆盖掉当前路径，如果出现最短路径相等的情况，用那就加上当前的路径。要记得初始化起点的路径为1
  • 初始化起点路径为0
  • 逻辑没问题，一般是判断的时候 == 写成了 =
3) Dijkstra+DFS
  • 对于Dijkstra部分的任务是统计出路径最短的条数即可；
  • 注意判断的时候双等号；
  • 以及添加的pre数组，存储前驱结点；
  • G在初始化的时候是fill(G[0], G[0]+maxn*maxn, INF);
void Dijkstra(int s){
    fill(d, d+maxn, INF);
    d[s] = 0;
    for(int i = 0; i < n; i++){
        int u = -1, 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;
        vis[u] = true;
        for(int v = 0; v < n; v++){
            if(vis[v] == false && G[u][v] != INF){
                if(d[u] + G[u][v] < d[v]){
                    d[v] = d[u] + G[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }else if(d[u] + G[u][v] == d[v]){
                    pre[v].push_back(u);
                }
            }
        }
    }
}
  • 对于DFS部分，是用Dijkstra统计出的路径pre统计第二判定条件下选择最优路径；
  • 递归边界是，遍历到结点等于起点st；
  • 递归条件是对于当前结点接下来可以到的结点；
  • 还有就是回溯，一个是起点要自己临时添加进入tempPath，在返回前还要弹出；遍历完当前节点可以到的结点后也要弹出结点；
void DFS(int v){
    if(v == s){
        tempPath.push_back(v);
        int value = 0;
        for(int i = tempPath.size() - 1; i > 0; i--){
            int id = tempPath[i], next = tempPath[i - 1];
            value += Cost[id][next];
        }
        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();
}

2. Bellman-Ford算法和SPFA算法

  • 用于解决单源最短路径的问题，用于可能出现负环的情况，也就是边中存在负的权值；
  • 主要思想也就是判断n-1循环，每次判断其中每一条边，最后一次判断如果，还是会有出现距离变短，说明会出现负环的情况；
  • 使用邻接表更加方便
  • 跟Dijkstra区别是统计最短路径的条数;如果出现更短的路径还是一样直接覆盖；如果出现一样的路径，那么直接需要创建set进行存储，记住前驱是使用set进行存储的
set<int> pre[maxn];
if(d[u] + dis < d[v]){
    d[v] = d[u] + dis;
    w[v] = w[u] + weight[u];
    num[v] = num[u];
    pre[v].clear();
    pre[v].insert(u);
}else if(d[u] + dis == d[v]){
    if(w[u] + weight[v] > w[v]){
        w[v] = w[u] + weight[v];
    }
    pre[v].insert(u);
    num[v] = 0;
    set<int>::iterator it;
    for(auto it = pre[v].begin(); it != pre[v].end(); it++){
        num[v] += num[*it];
    }
}

struct node{
    int v, dis;
};
vector<node> G[maxn];
int n;
int d[maxn];
bool Bellman(int s){
    fill(d, d+maxn, INF);
    d[s] = 0;
    for(int i = 0; i < n - 1; i++){
        for(int u = 0; u < n; u++){
            for(int j = 0; j < G[u].size(); j++){
                int v = G[u][j].v;
                int dis = G[u][j].dis;
                if(d[u] + dis < d[v]){
                    d[v] = d[u] + dis;
                }
            }
        }
    }

    for(int u = 0; u < n; u++){
        for(int j = 0; j < G[u].size(); j++){
            int v = G[u][j].v;
            int dis = G[u][j].dis;
            if(d[u] + dis < d[v]){
                return false;
            }
        }
    }
    return true;
}

3. Floyd算法(弗洛伊德算法)

  • 用于解决全源最短路径问题
  • 使用邻接矩阵解决问题, 结点限制在200个以内；
  • 枚举顶点k数，然后以该结点作为中介点，能否使得i, j顶点之间的距离变短；
int dis[maxn][maxn];
int n;
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];
                }
            }
        }
    }
}

四、最小生成树

  • 给定一个无向图G，然后求其中一棵生成树T，使得这棵树拥有图的所有结点；
  • 且所有边来自图中的边，使得整棵树的边权之和最小；

1. prim算法（普里姆算法）

  • 用于稠密图，边多
  • 跟Dijkstra只有一点不同，即距离数组d的含义，在这里含义是到集合S的距离，即已经生成的树，而在Dijkstra是两结点的距离；
  • 同时多一个变量ans，用于存储最小生成树的所有边权之和
const int INF = 100000000;
const int maxn;
int n, G[maxn][maxn];
int d[maxn];
bool vis[maxn] = {false};
//以s为根结点生成的最小生成树
int prim(int s){
    fill(d, d+maxn, INF);
    d[s] = 0;
    int ans = 0;
    for(int i = 0; i < n; i++){
        int u = -1, MIN = INF;
        for(int j = 0; j < n; j++){
            if(vis[j] == false && d[j] < MIN){
                u = j;
                MIN = dis[j];
            }
        }
    }
    if(u == -1) return -1;
    ans += d[u];
    for(int v = 0; v < n; v++){
        if(vis[v] == false && G[u][v] != INF && G[u][v] < d[v]){
            d[v] = G[u][v];
        }
    }
    return ans;
}

2. kruskal(克鲁斯卡尔算法)

  • 用于稀疏图，边少
  • 算法思想是需要判断两个端点是否在不同的连通块中，因此两个端点的编号一定是需要的，边权也是需要的；
  • 所有边按从小到大进行排序；
  • 一个是判断两个顶点是否在不同的连通块中；
  • 如何将测试边加入连通块；
struct edge{
    int u, v;
    int cost;
}E[maxn];

bool cmp(edge a, edge b){
    return a.cost < b.cost;
}

int father[N];
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;
}

//n是顶点个数，m为图的边数
int kruskal(int n, int m){
    int ans = 0, num_edge = 0;
    for(int i = 1; i <= n; i++){//假设顶点范围位1-n
        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;
}

五、拓扑排序

  • 明确两个东西，一个是有向无环图和拓扑排序之间的关系；对于一个有向无环图，可以生成拓扑序列；同时，也可以根据所给序列判定其是否为该有向无环图的拓扑序列；核心是每个结点的入度
  • 在一个就是怎么样判定有向无环图和拓扑排序；
  • 首先是必不可少存储图的邻接表和存储每个结点的入度的数组
  • 明确一点当访问当该点时，一定这时入度已经是0，否则该序列不是拓扑序列；
  • 在判定图是否为有向无环图时，首先将入度为0的结点加入队列中，然后遍历访问到该结点时，将该结点能够到达的左右结点的入度减一，如果出现入度为0，则加入队列中，然后统计结点变为0的数量num，如果等于图的结点数量，说明为有向无环图；
  • 如果有向无环图，想要从编号从小开始生成拓扑序列，使用priority_queue, 优先队列是默认从大到小排序，访问队首元素使用top()函数
  • 其优先级设置刚好跟sort相反；
//表示从小到大
priority_queue<int， vector<int>, greater<int>> q;

//从大到小
priority_queue<int, vector<int>, less<int>> q;

结构体
struct cmp{
    bool operator() (fruit f1, fruit f2){
        return f1.price > f2.price;
    }
}
//表示从小到大
priority_queue<fruit， vector<fruit>, cmp> q;

vector<int> G[maxn];
int indegree[maxn];
vector<int> tin(indegree, indegree+n+1);//将入度直接赋值到tin向量中，用于判定序列是否为拓扑序列

bool toplogicalSort(){
    queue<int> q;
    for(int i = 0; i < n; i++){
        if(indegree[i] == 0){
            q.push(i);
        }
    }
    int num = 0;
    while(!q.empty()){
        int top = q.front();
        //printf("%d", top);
        q.pop();
        for(int j = 0; j < G[top].size(); j++){
            indegree[G[top][j]]--;
            if(indegree[G[top][j]] == 0){
                q.push(G[top][j]);
            }
        }
        G[top].clear();
        num++;
    }
    if(num == n) return true;
    else return false;
}

六、关键路径

  • 明确两个点，结点代表事件，他有最早开始时间ve和最迟开始时间vl；而边代表活动，它也有最早开始时间e和最迟开始时间l；
  • 怎么求事件的最早和最迟开始时间：最早开始时间直接等于前驱事件最早开始时间ve加上其到达的活动持续时间的最大值;最晚开始时间，根据栈，进行逆序拓扑序列，然后等于后驱事件最迟开始时间vl和其活动持续时间的最小值；
const int maxn = 105;
struct node{
    int v, w;
}; 
vector<node> G[maxn];
int indegree[maxn] = {0};
stack<int> topOrder;
int ve[maxn], vl[maxn];
int n , m;
bool topSort(){
    queue<int> q;
    for(int i = 1; i <= n; i++){
        if(indegree[i] == 0){
            q.push(i);
        } 
    }
    while(!q.empty()){
        int now = q.front();
        topOrder.push(now);
        q.pop();
        for(int i = 0; i < G[now].size(); i++){
            int v = G[now][i].v, w = G[now][i].w;
            indegree[v]--;
            if(indegree[v] == 0){
                q.push(v);
            }
            if(ve[now] + w > ve[v]){
                ve[v] = ve[now] + w;
            }
        }
    }
    if(topOrder.size() == n) return true;
    else return false;
}
  • 他们之间的关系，活动的最早开始时间和前驱事件的最早开始时间ve是一样的，而最迟开始时间为后驱事件的最迟开始时间vl减去活动的持续时间；
void cPath(){
    fill(ve, ve+maxn, 0);
    if(topSort() == false){
        printf("0\n");
        return;
    }
    int ans = -1;
    for(int i = 1; i <= n; i++){
        if(ve[i] > ans) ans = ve[i];
    }
    printf("%d\n", ans);
    fill(vl, vl+maxn, ans);
    while(!topOrder.empty()){
        int u = topOrder.top();
        topOrder.pop();
        for(int i = 0; i < G[u].size(); i++){
            int v = G[u][i].v, w = G[u][i].w;
            if(vl[v] -  w < vl[u]){
                vl[u] = vl[v] - w;
            }
        }
    }
    for(int u = 1; u <= n; u++){
        for(int i = G[u].size()-1; i >= 0 ; i--){
            int v = G[u][i].v, w = G[u][i].w;
            int e = ve[u], l = vl[v] - w;
            if(e == l){
                printf("%d->%d\n", u, v);
            }
        }
    }
    return;
}
int main(){
    cin >> n >> m;
    int a, b, w;
    for(int i = 0; i < m; i++){
        scanf("%d%d%d", &a, &b, &w);
        indegree[b]++;
        G[a].push_back(node{b, w});
    }
    cPath();
    return 0;
}

原文链接: https://www.cnblogs.com/tsruixi/p/13328098.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

    数据结构-图编程知识详细总结C++（图创建、图遍历、最短路径、拓扑排序、关键路径）

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/367422

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年3月2日 下午5:46
下一篇 2023年3月2日 下午5:46

相关推荐