邊沒有用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，該數組用于bfs int 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 10 1 2 2 1 3 5 2 3 4 2 4 6 3 4 2 2 5 10 4 6 1 5 6 3 5 7 5 6 7 9

輸出

2 -> 1 = 2 2 -> 3 = 4 2 -> 4 = 6 2 -> 5 = 10 2 -> 6 = 7 2 -> 7 = 15

總結

以上是生活随笔為你收集整理的链式前向星模板 建图+dfs+bfs+dijkstra的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。