图论：图的存储和遍历

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

前言
图论
- 一、图的存储
二、最短路径

前言

提示：这里可以添加本文要记录的大概内容：

例如：随着人工智能的不断发展，机器学习这门技术也越来越重要，很多人都开启了学习机器学习，本文就介绍了机器学习的基础内容。

提示：以下是本篇文章正文内容，下面案例可供参考

图论一、图的存储

1.邻接矩阵（二维数组存储）
2.邻接表：链表存储，将连在同一个表头节点的相邻节点，把相邻顶点依次存放于表头结点所指向的单向链表中。

#include
using namespace std;
int n, m; //n个点， m条边
int main() {
        cin >> n >> m;
        vector > > edg(n + 1, vector >{}); //创建二维数组来存储
        for (int i = 1; i <= n; i++) {
               int s, e, v;
               cin >> s >> e >> v;
               edg[s].push_back(pair(e, v));
        }
        for (int i = 1; i <= n; i++) {
               cout << i << " : ";
               for (int j = 0; j < edg[i].size(); j++) {
                       cout << "{" << edg[i][j].first << "," << edg[i][j].second << "}";
               }
               cout << endl;
        }
        return 0;
}

2.链式前项星：只存储边的终点、边的权值和以i为起点的最后一条边的编号

#include
using namespace std;
int n, m, head[100];
struct edge {//定义结构体用来存储边的终点e 边的权值v 与当前边同一起点的边的存储位置next
        int e, v, next;
};
edge edg[500];//建立边集
int main() {
        memset(head, -1, sizeof(head));//初始化 head 数组 head[i] 以i为起点的最后一条边的编号
        cin >> n >> m;
        for (int i = 1; i <= m; i++) {
               int s, e, v;
               cin >> s >> e >> v;
               edg[i].e = e;
               edg[i].v = v;
               edg[i].next = head[s];
               head[s] = i;
        }
        for (int i = 1; i <= n; i++) {
               cout << i << " : ";
               for (int j = head[i]; j != -1; j = edg[j].next) {
                       cout << "{" << edg[j].e << "," << edg[j].v << "}";
               }
               cout << endl;
        }
        return 0;
}

二、最短路径

1.Floyd多源最短路（任意起点到任意终点的最短距离，邻接矩阵存储的图首选Floyd算法）

#include
using namespace std;
int n, m, s, arr[100][100];
int main() {
        memset(arr, 0x3f, sizeof(arr));
        cin >> n >> m >> s;
        for (int i = 1; i <= n; i++) {// 点到自己的距离初始化为0
               arr[i][i] = 0;
        }
        for (int i = 0; i < m; i++) {
               int s, e, v;
               cin >> s >> e >> v;
               arr[s][e] = min(arr[s][e], v);
               arr[e][s] = min(arr[e][s], v);
        }
        for (int i = 1; i <= n; i++) {//Floyd
               for (int j = 1; j <= n; j++) {
                       for (int k = 1; k <= n; k++) {
                              arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k]);
                       }
               }
        }
        for (int i = 1; i <= n; i++) {
               if (arr[s][i] != 0x3f3f3f3f) {
                       cout << s << " -> " << i << " = " << arr[s][i] << endl;
               }
               else {
                       cout << -1 << endl;
               }
        }
        return 0;
}

Dijkstra 单源最短路

#include
using namespace std;
int n, m, s, head[100];
struct edge { //构造边的存储结构
        int e, v, next;
};
edge edg[100];
struct node {  //构造点 存储该点和起点到该点的距离
        int now, val;
        bool operator< (const node& b) const {
               return this->val > b.val;
        }
};
priority_queue que;
int ans[100], edg_cnt;
void add_edg(int s, int e, int v) {          //链式前项星存储边
        edg[edg_cnt].e = e;
        edg[edg_cnt].v = v;
        edg[edg_cnt].next = head[s];
        head[s] = edg_cnt++;
}
void dijkstra(priority_queue &que) {
        while (!que.empty()) {
               node temp = que.top();
               que.pop();
               if (temp.val != ans[temp.now]) {//如果某一点的值与ans不相等说明已经有更小的值已经存入ans数组中
                       continue;
               }
               for (int i = head[temp.now]; i != -1; i = edg[i].next) {
                       int e = edg[i].e, v = edg[i].v;
                       if (ans[e] > ans[temp.now] + v) {//更新某一点的ans值
                              ans[e] = ans[temp.now] + v;
                              node temp;
                              temp.now = e, temp.val = ans[e];//该点入队寻找与该点相连的点
                              que.push(temp);
                       }
               }
        }
}
int main() {
        memset(head, -1, sizeof(head));
        memset(ans, 0x3f, sizeof(ans));
        cin >> n >> m >> s;
        for (int i = 1; i <= m; i++) {//存边
               int a, b, c;
               cin >> a >> b >> c;
               add_edg(a, b, c);//双向图正反各存一次
               add_edg(b, a, c);
        }
        node temp;
        temp.now = s;
        temp.val = 0;
        ans[s] = 0;
        que.push(temp);//起点入队列
        dijkstra(que);
        for (int i = 1; i <= n; i++) {
               if(ans[i] != 0x3f3f3f3f) {//如果某一点值没有改变说明与起点不连通
                       cout << s << " -> " << i << " = " << ans[i] <
                       cout << -1 << endl;
               }
        }
        return 0;
}

Bellman-Ford ：遍历边更新起点到该点的距离但不一定是最短距离，最坏情况下n个点需要遍历 n - 1 轮。

#include
using namespace std;
int n, m, s, head[100], ans[100];
struct edge {
        int e, v, s;
};
edge edg[500];
int edg_cnt;
void add_edg(int s, int e, int v) {
        edg[edg_cnt].s = s;
        edg[edg_cnt].e = e;
        edg[edg_cnt++].v = v;
}
int main() {
        memset(head, -1, sizeof(head));
        memset(ans, 0x3f, sizeof(ans));
        cin >> n >> m >> s;
        for (int i = 0; i < m; i++) {
               int a, b, c;
               cin >> a >> b >> c;
               add_edg(a, b, c);
               add_edg(b, a, c);
        }
        ans[s] = 0;
        for (int i = 1; i <= n; i++) {
               int f = 0;
               for (int j = 0; j < edg_cnt; j++) {
                       if (ans[edg[j].e] > ans[edg[j].s] + edg[j].v) {
                              ans[edg[j].e] = ans[edg[j].s] + edg[j].v;
                              f == 1;
                       }
               }
               if (f == 0) {
                       break;
               }
        }
        for (int i = 1; i <= n; i++) {
               if (ans[i] != 0x3f3f3f3f) {
                       cout << s << " -> " << i << " = " << ans[i] << endl;
               }
               else {
                       cout << -1 << endl;
               }
        }
        return 0;
}

基于队列优化的bellman-ford算法：只有当上一轮的点更新过了，这一轮才会更新以该点为起点的边。

#include
using namespace std;
int n, m, s, head[100], ans[100], mark[100];
struct edge {
        int e, v, next;
};
edge edg[500];
int edg_cnt;
void add_edg(int s, int e, int v) {
        edg[edg_cnt].e = e;
        edg[edg_cnt].v = v;
        edg[edg_cnt].next = head[s];
        head[s] = edg_cnt++;
}
int main() {
        memset(head, -1, sizeof(head));
        memset(ans, 0x3f, sizeof(ans));
        cin >> n >> m >> s;
        for (int i = 1; i <= m; i++) {
               int a, b, c;
               cin >> a >> b >> c;
               add_edg(a, b, c);
               add_edg(b, a, c);
        }
        ans[s] = 0;
        queue que;
        que.push(s);
        while (!que.empty()) {
               int temp = que.front();
               que.pop();
               mark[temp] = 0;
               for (int i = head[temp]; i != -1; i = edg[i].next) {
                       int e = edg[i].e, v = edg[i].v;
                       if (ans[e] > ans[temp] + v) {
                              ans[e] = ans[temp] + v;
                              if (mark[e] == 0) {
                                      que.push(e);
                                      mark[e] = 1;
                              }
                       }
               }
        }
        for (int i = 1; i <= n; i++) {
               if (ans[i] != 0x3f3f3f3f) {
                       cout << s << " -> " << i << " = " << ans[i] << endl;
               }
               else {
                       cout << -1 << endl;
               }
        }
        return 0;
}

题目描述
有一个邮递员要送东西，邮局在节点 1。他总共要送 n−1 样东西，其目的地分别是节点 2 到节点 n。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 m 条道路。这个邮递员每次只能带一样东西，并且运送每件物品过后必须返回邮局。求送完这 n−1 样东西并且最终回到邮局最少需要的时间。
输入
5 10
2 3 5
1 5 5
3 5 6
1 2 8
1 3 8
5 3 4
4 1 8
4 5 3
3 5 6
5 4 2

#include
using namespace std;
int n, m, head1[50], head2[50], ans1[50], ans2[50];
int ans;
struct edge {
        int e, v, next;
};
edge edg1[100], edg2[100];
void add_edg(edge *edg, int *head, int cnt, int s, int e, int v) {
        edg[cnt].e = e;
        edg[cnt].v = v;
        edg[cnt].next = head[s];
        head[s] = cnt;
}
void bellman_ford(edge* edg, int* head, int* ans) {
        queue que;
        que.push(1);
        int mark[50] = { 0 };
        while (!que.empty()) {
               int temp = que.front();
               que.pop();
               mark[temp] = 0;
               for (int i = head[temp]; i != -1; i = edg[i].next) {
                       int e = edg[i].e, v = edg[i].v;
                       if (ans[e] > ans[temp] + v) {
                              ans[e] = ans[temp] + v;
                              if (mark[e] == 0) {
                                      que.push(e);
                                      mark[e] = 1;
                              }
                       }
               }
               
        }
}
int main() {
        memset(head1, -1, sizeof(head1));
        memset(head2, -1, sizeof(head2));
        memset(ans1, 0x3f, sizeof(ans1));
        memset(ans2, 0x3f, sizeof(ans2));
        cin >> n >> m;
        for (int i = 0; i < m; i++) {
               int a, b, c;
               cin >> a >> b >> c;
               add_edg(edg1, head1, i, a, b, c);//正向存边 计算从起点到 i 点的距离
               add_edg(edg2, head2, i, b, a, c);//反向存边 计算从起点到 i 点的距离 相当于从 i 点到起点的距离
        }
        ans1[1] = 0;
        ans2[1] = 0;
        bellman_ford(edg1, head1, ans1);
        bellman_ford(edg2, head2, ans2);
        for (int i = 1; i <= n; i++) {
               ans += ans1[i] + ans2[i];
        }
        cout << ans << endl;
        return 0;
}

广度优先遍历（BFS）

#include 
using namespace std;
struct node {
        int x, y, step;
};
int n, m, sx, sy, ex, ey, cnt;
int dir[8][2] = { 0,1,1,0,0,-1,-1,0,1,1,1,-1,-1,1,-1,-1};
char mmap[100][100];
int main() {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
               for (int j = 1; j <= m; j++) {
                       cin >> mmap[i][j];
                       if (mmap[i][j] == 'S') {
                              sx = i, sy = j;
                       }
                       if (mmap[i][j] == 'T') {
                              ex = i, ey = j;
                       }
               }
        }
        queue que;
        node temp;
        temp.x = sx, temp.y = sy, temp.step = 0;
        que.push(temp);
        while (!que.empty()) {
               node temp = que.front();
               que.pop();
               for (int i = 0; i < 8; i++) {
                       int x = temp.x + dir[i][0];
                       int y = temp.y + dir[i][1];
                       if (mmap[x][y] == 'T') {
                              cout << temp.step + 1 << endl;
                              return 0;
                       }
                       if (mmap[x][y] == '.') {
                              mmap[x][y] = 'x';
                              node temp1;
                              temp1.x = x, temp1.y = y, temp1.step = temp.step + 1;
                              que.push(temp1);
                       }
               }
        }
        cout << -1 << endl;
        return 0;
}

启发式搜索 A*
A*算法基本思想：引入当前节点i的估计函数f, 当前节点 i 的估计函数定义为： f(i) = g(i) + h(i) ，其中g(i) 是从起点到当前节点 i 的实际代价，h(i) 是从节点 i 到终点的最小代价估计。

#include 
using namespace std;
int n, m, sx, sy, ex, ey, cnt;
struct node {
        int x, y, step;
        double h;
        bool operator < (const node b) const {
               return this->step + this->h > b.step + b.h;
        }
};
double func(int x, int y) {
        int a = ex - x, b = ey - y;
        return sqrt(a * a + b * b);
}
int dir[8][2] = { 0,1,1,0,0,-1,-1,0,1,1,1,-1,-1,1,-1,-1};//方向数组
char mmap[100][100];//地图数组
int prex[100][100], prey[100][100];//存储某一位置x, y的前置值(从哪来的）
void p() { //打印
        cout << "----------" << endl;
        for (int i = 1; i <= n; i++) {
               for (int j = 1; j <= m; j++) {
                       cout << mmap[i][j];
                       if (mmap[i][j] == 'x') {
                              mmap[i][j] = 'X';
                       }
               }
               cout << endl;
        }
        cout << "++++++++++" << endl;
}
void fin(int x, int y) { //通过存储的前置数组找路
        if (mmap[x][y] == 'S') {
               return;
        }
        mmap[x][y] = 'O';//路径上的值标记为O
        fin(prex[x][y], prey[x][y]);
}
void astar(priority_queue& que) {
        while (!que.empty()) {
               node temp = que.top();
               que.pop();
               for (int i = 0; i < 8; i++) {
                       int x = temp.x + dir[i][0];
                       int y = temp.y + dir[i][1];
                       if (mmap[x][y] == 'T') {
                              cout << temp.step + 1 << endl;
                              fin(temp.x, temp.y);//借助存储的路径函数找到路径
                              p();//打印规划好的路径
                              return ;
                       }
                       if (mmap[x][y] == '.') {
                              mmap[x][y] = 'x';
                              node temp1;
                              temp1.x = x, temp1.y = y, temp1.step = temp.step + 1,  temp1.h = func(x, y);
                              que.push(temp1);
                              prex[x][y] = temp.x;//记录 x,y 从哪来的
                              prey[x][y] = temp.y;
                              cnt++;
                              if (cnt % 5 == 0) {
                                      p();
                              }
                       }
               }
        }
}
int main() {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
               for (int j = 1; j <= m; j++) {
                       cin >> mmap[i][j];
                       if (mmap[i][j] == 'S') {
                              sx = i, sy = j;
                       }
                       if (mmap[i][j] == 'T') {
                              ex = i, ey = j;
                       }
               }
        }
        priority_queue que;
        node temp;
        double s = func(sx, sy);
        temp.x = sx, temp.y = sy, temp.step = 0, temp.h = s;
        que.push(temp);
        astar(que);
        return 0;
}

图论：图的存储和遍历

C/C++/C#相关栏目本月热门文章