链式前向星模板 建图+dfs+bfs+dijkstra

边没有用struct封装起来，节点和边的计数起点如果不符合习惯可以稍作修改

建图+DFS+BFS

#include <cstdio>#include <cstring>#include <iostream>using namespace std;typedef long long LL;const int inf = 0x3f3f3f3f;const int maxn = 1005;int n, m, all = -1; // n:点数 m:边数 all:边的编号 (边的编号由0开始，点的编号从1开始)int pre[maxn];// pre[e] e这条边同一出发点的上一条出边int last[maxn];// last[v] 以v为起点构建的最后一条边int to[maxn]; // to[e] e连向的点int que[maxn];// 数组模仿队列，用于存bfs顺序，que 从1开始计数，详见bfs函数bool vis[maxn];// vis[v] v是否被访问过void Build(int x, int y, int w = 1) // 建立x->y的边，权默认1{pre[++all] = last[x];last[x] = all;to[all] = y;cost[all] = w;}void input(){all = -1;memset(last, -1, sizeof(last));cin >> n >> m; // n点 m边for (int i = 1; i <= m; i++){int a,b,w;cin >> a >> b; // 带权则加上 >> wBuild(a, b);Build(b, a); // 无向图}}void dfs(int u) // 调用前需要初始化vis{int ed = last[u], dst; // ed表示边(edge)，dst表示ed连向的点vis[u] = true;cout << u << endl; // dfs的操作，这里是打印while (ed != -1){dst = to[ed];if (!vis[dst]) dfs(dst);ed = pre[ed]; // 遍历上一条边}}void bfs(int u) // 逻辑复杂，需要花时间理解{memset(vis, 0, sizeof(vis));int head = 1, tail = 1, now, ed, dst; // head,tail表示头尾指针，now表示当前节点que[head] = u;vis[u] = true;while (head <= tail){now = que[head];ed = last[now];while (ed != -1) // 遍历now的所有出度{dst = to[ed];if (!vis[dst]) {vis[dst] = true;que[++tail] = dst; }ed = pre[ed];}head++;}for (int i = 1; i <= n; i++) cout << que[i] << endl; // 打印}int main(){input();memset(vis, 0, sizeof(vis));dfs(1);cout << endl;bfs(1);return 0;}

输入，在书上随便找了一张无向图

结果

谁能告诉我链式前向星的英文名是啥 orz

Dijkstra

模板是一样的，在输入的时候做了些改动，加入了权值

#include <cstdio>#include <cstring>#include <iostream>using namespace std;typedef long long LL;const int inf = 0x3f3f3f3f;const int maxn = 1005;int n, m, all = -1; // n:点数 m:边数 all:边的编号 (边的编号由0开始，点的编号从1开始)int pre[maxn];// pre[e] e这条边同一出发点的上一条出边int last[maxn];// last[v] 以v为起点构建的最后一条边int to[maxn]; // to[e] e连向的点int dis[maxn];// dis[v] v到根的距离（边数），根到自己的距离为0，该数组用于bfsint que[maxn];// 数组模仿队列，用于存bfs顺序，que 从1开始计数，详见bfs函数bool vis[maxn];// vis[v] v是否被访问过int cost[maxn];// cost[e] e的权，用于最短路算法void Build(int x, int y, int w = 1) // 建立x->y的边，权默认1{pre[++all] = last[x];last[x] = all;to[all] = y;cost[all] = w;}void input(){all = -1;memset(last, -1, sizeof(last));cin >> n >> m; // n点 m边for (int i = 1; i <= m; i++){int a,b,w;cin >> a >> b >> w;Build(a, b, w);Build(b, a, w); // 无向图}}void dijkstra(int s) // 源点s到所有其他点的最小距离，调用前应初始化vis为0{for(int i = 1; i <= n; i++){if(i == s) dis[i] = 0;else dis[i] = inf;}int now = s; // 当前节点初始化为源点for(int i = 1; i <= n; i++) {vis[now] = 1;int ed = last[now]; // 取当前节点的最后一条边//printf("debug:now=%d ed=%d cost[ed]=%d\n", now, ed, cost[ed]);//debugint dst;while(ed != -1){dst = to[ed]; // ed连向的节点if(!vis[dst]) dis[dst] = min(dis[dst], dis[now] + cost[ed]); // 松弛：更新s到dst的距离为“直通”和“当前距离+ed权值”的较小值ed = pre[ed];//printf("dst=%d dis[dst]=%d\n", dst, dis[dst]);//debug}int Min = inf; int pos = 0;for(int i = 1; i <= n; i++) // 找出所有节点中，离根最近的那个节点的编号记为pos{if(!vis[i]) {//printf("vis[%d]=%d\n", i, vis[i]);//debugif(dis[i] < Min) {Min = dis[i];pos = i;}}}//printf("pos=%d\n", pos);//debugnow = pos;}for (int i = 1; i <= n; i++) // print{if (i == s) continue;cout << s << " -> " << i << " = " << dis[i] << endl;}}int main(){input();memset(vis, 0, sizeof(vis));dijkstra(2);return 0;}

输入数据

7 101 2 21 3 52 3 42 4 63 4 22 5 104 6 15 6 35 7 56 7 9

输出

2 -> 1 = 22 -> 3 = 42 -> 4 = 62 -> 5 = 102 -> 6 = 72 -> 7 = 15