網站首頁 編程語言 正文
一、鄰接矩陣
適用：
稠密圖，就是說點數的平方與邊數接近的情況，換句話說就是邊特別多。
不適用：
稀疏圖，就是點數的平方與邊數差的特別多，邊數少，但點數多，就不行了，因為空間占用太大了。
實現代碼：
#include <bits/stdc++.h>
using namespace std;
const int N = 1010; //圖的最大點數量
int n;
int v[N][N]; ? ? ? ?//鄰接矩陣
/**
?* 測試數據
?4
?0 5 2 3
?5 0 0 1
?2 0 0 4
?3 1 4 0
?*/
int main() {
? ? cin >> n;
? ? //讀入到鄰接矩陣
? ? for (int i = 1; i <= n; i++)
? ? ? ? for (int j = 1; j <= n; j++)
? ? ? ? ? ? cin >> v[i][j];
? ? //下面的代碼將找到與點i有直接連接的每一個點以及那條邊的長度
? ? for (int i = 1; i <= n; i++)
? ? ? ? for (int j = 1; j <= n; j++)
? ? ? ? ? ? if (v[i][j]) cout << "edge from point "?
? ? ? ? ? ? ? ? << i << " to point " << j << " with length " << v[i][j] << endl;
? ? return 0;
}
二、鄰接表
#include <bits/stdc++.h>
using namespace std;
const int N = 1010; //圖的最大點數量
struct Edge { ? ? ? //記錄邊的終點，邊權的結構體
? ? int to; ? ? ? ? //終點
? ? int value; ? ? ?//邊權
};
int n, m; //表示圖中有n個點，m條邊
vector<Edge> p[N]; ?//使用vector的鄰接表
/**
?* 測試數據
?4 6
?2 1 1
?1 3 2
?4 1 4
?2 4 6
?4 2 3
?3 4 5
?*/
int main() {
? ? cin >> n >> m;
? ? //m條邊
? ? for (int i = 1; i <= m; i++) {
? ? ? ? int u, v, l; ? ? ? ? ? ? ? ?//點u到點v有一條權值為l的邊
? ? ? ? cin >> u >> v >> l;
? ? ? ? p[u].push_back({v, l});
? ? }
? ? //輸出
? ? for (int i = 1; i <= n; i++) {
? ? ? ? printf("出發點：%d ", i);
? ? ? ? for (int j = 0; j < p[i].size(); j++)
? ? ? ? ? ? printf(" 目標點：%d,權值：%d;", p[i][j].to, p[i][j].value);
? ? ? ? puts("");
? ? }
? ? return 0;
}
三、鏈式前向星
鏈式前向星是鄰接表存圖的第二種方法，它自己還有兩種寫法，比 用向量存圖的那種鄰接表要快 。
它是一種以邊為主的存圖方式，idxidx表示最后一條邊的預存入的房間號,$head[i$]表示以$i$為起點第一條邊的房間號。
每條邊有三個屬性：
- 從
$head[i]$出發到哪個結點的邊？ - 這條邊的邊權是多少？
- 這條邊的下一條邊是誰？（下一條邊的房間號）
鏈式前向星有三種變形，需要同學們都掌握，找一種自己最喜歡的背下來，其它兩種要求能看懂，因為其它人寫題解，可能使用了其它方式。
1、AcWing方式（純數組）
#include <bits/stdc++.h>
using namespace std;
const int N = 1010; ? ? //點數最大值
int n, m; ? ? ? ? ? ? ? //n個點，m條邊
//idx是新結點加入的數據內索引號
//h[N]表示有N條單鏈表的頭,e[M]代表每個節點的值,ne[M]代表每個節點的下一個節點號
int h[N], e[N << 1], ne[N << 1], w[N << 1], idx;
//鏈式前向星
void add(int a, int b, int l) {
? ? e[idx] = b, ne[idx] = h[a], w[idx] = l, h[a] = idx++;
}
/**
?* 測試數據
?4 6
?2 1 1
?1 3 2
?4 1 4
?2 4 6
?4 2 3
?3 4 5
?*/
int main() {
? ? cin >> n >> m;
? ? //初始化為-1,每個頭節點寫成-1
? ? memset(h, -1, sizeof h);
? ? //m條邊
? ? for (int i = 1; i <= m; i++) {
? ? ? ? int u, v, l; ? ? ? ? ? ? ? ?//點u到點v有一條權值為l的邊
? ? ? ? cin >> u >> v >> l;
? ? ? ? //加入到鏈式前向星
? ? ? ? add(u, v, l);
? ? }
? ? //遍歷每個結點
? ? for (int i = 1; i <= n; i++) {
? ? ? ? printf("出發點：%d ", i);
? ? ? ? for (int j = h[i]; j != -1; j = ne[j])
? ? ? ? ? ? printf(" 目標點：%d,權值：%d;", e[j], w[j]);
? ? ? ? puts("");
? ? }
? ? return 0;
}
三、Acwing圖的存儲方式
方法：使用一個二維數組 g 來存邊，其中 g[u][v] 為 1 表示存在 到的邊，為 0 表示不存在。如果是帶邊權的圖，可以在 g[u][v] 中存儲到的邊的邊權。
案例：
最短距離Dijkstra
從s到t的最短距離算法流程：
b[]表示當前已經確定最短距離的點。
dis[s] = 0, dis[其他] = +∞ for (int i = 1; i <= n; i ++)
t：不在b中的最短距離的點
將t加入b[]
使用t更新其他未被確定的點的距離
代碼實現：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510;
int n, m;
int w[N][N];
int dis[N];
bool b[N];
int dijkstra() {
? ? memset(dis, 0x3f, sizeof dis);
? ? dis[1] = 0;
? ? for (int i = 0; i < n; i ++) {
? ? ? ? int k = -1;
? ? ? ? for (int j = 1; j <= n; j ++)
? ? ? ? ? ? if (!b[j] && (k == -1 || dis[k] > dis[j]))
? ? ? ? ? ? ? ? k = j;
? ? ? ? b[k] = true;
? ? ? ? for (int j = 1; j <= n; j ++) {
? ? ? ? ? ? dis[j] = min(dis[j], dis[k] + w[k][j]);
? ? ? ? }
? ? }
? ? if (dis[n] == 0x3f3f3f3f) return -1;
? ? else return dis[n];
}
int main() {
? ? scanf("%d %d", &n, &m);
? ? memset(w, 0x3f, sizeof w);
? ? while (m --) {
? ? ? ? int i, j, k;
? ? ? ? scanf("%d %d %d", &i, &j, &k);
? ? ? ? w[i][j] = min(w[i][j], k);
? ? }
? ? int t = dijkstra();
? ? printf("%d", t);
? ? return 0;
}2、復雜度
2、應用
鄰接矩陣只適用于沒有重邊（或重邊可以忽略）的情況。
其最顯著的優點是可以查詢一條邊是否存在。
由于鄰接矩陣在稀疏圖上效率很低（尤其是在點數較多的圖上，空間無法承受），所以一般只會在稠密圖上使用鄰接矩陣。
3、鄰接表
使用一個支持動態增加元素的數據結構構成的數組，如 vector g[n + 1] 來存邊，其中 g[u] 存儲的是點的所有出邊的相關信息（終點、邊權等）。
4、代碼實現
數據定義：
h是n個鏈表的鏈表頭, e存的是每一個節點的值, ne存的是 next指針是多少。
int h[N], e[M], ne[M], idx; bool st[N];
5、插入邊
插入一條a指向b的邊
void add(int a, int b) {
? ? e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}四、遍歷
1、深度優先遍歷
void dfs(int u) {
? ? st[u] = true; ? ?// 標記已經被遍歷過了
? ? for (int i = h[u]; i != -1; i = ne[i]) {
? ? ? ? int j = e[i];
? ? ? ? if (!st[j]) dfs(j);
? ? }
}2、廣度優先遍歷
void bfs() {
? ? int q[N]; ? ?// 定義隊列?
? ? int hh = 0, tt = 0; ? ?// 頭和尾指針?
? ? memset(st, 0, sizeof st);
? ? q[0] = 1;
? ? while (hh <= tt) {
? ? ? ? int t = q[hh ++];
? ? ? ? st[t] = true;
? ? ? ? cout << t << ' ';
? ? ? ? for (int i = h[t]; i != -1; i = ne[i]) {
? ? ? ? ? ? int j = e[i];
? ? ? ? ? ? if (!st[j]) {
? ? ? ? ? ? ? ? q[++ tt] = j;
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
3、復雜度
4、應用
存各種圖都很適合，除非有特殊需求（如需要快速查詢一條邊是否存在，且點數較少，可以使用鄰接矩陣）。
尤其適用于需要對一個點的所有出邊進行排序的場合。
5、實現案例
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10, M = N * 2;
// h是n個鏈表的鏈表頭, e存的是每一個節點的值, ne存的是 next指針是多少。?
int h[N], e[M], ne[M], idx;
bool st[N];
int n; ? ?// n條邊?
// 插入一條a指向b的邊?
void add(int a, int b) {
? ? e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
// 深度優先遍歷
void dfs(int u) {
? ? cout << u << ' ';
? ? st[u] = true; ? ?// 標記已經被遍歷過了
? ? for (int i = h[u]; i != -1; i = ne[i]) {
? ? ? ? int j = e[i];
? ? ? ? if (!st[j]) dfs(j);
? ? }
}
// 廣度優先遍歷?
void bfs() {
? ? int q[N]; ? ?// 定義隊列?
? ? int hh = 0, tt = 0; ? ?// 頭和尾指針?
? ? memset(st, 0, sizeof st);
? ? q[0] = 1;
? ? while (hh <= tt) {
? ? ? ? int t = q[hh ++];
? ? ? ? st[t] = true;
? ? ? ? cout << t << ' ';
? ? ? ? for (int i = h[t]; i != -1; i = ne[i]) {
? ? ? ? ? ? int j = e[i];
? ? ? ? ? ? if (!st[j]) {
? ? ? ? ? ? ? ? q[++ tt] = j;
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
int main () {
? ? memset(h, -1, sizeof h);
? ? cin >> n;
? ? for (int i = 1; i <= n; i ++) {
? ? ? ? int a, b;
? ? ? ? cin >> a >> b;?
? ? ? ? add(a, b);
? ? ? ? add(b, a);
? ? }
? ? cout << "深度優先遍歷：";
? ? dfs(1);
? ? cout << endl;
? ? cout << "廣度優先遍歷：";
? ? bfs();?
? ? return 0;
}6、 結構體+數組
#include <bits/stdc++.h>
using namespace std;
const int N = 1010; ? ? //點數最大值
int n, m, idx; ? ? ? ? ?//n個點，m條邊,idx是新結點加入的數據內索引號
//鏈式前向星
struct Edge {
? ? int to; ? ? //到哪個結點
? ? int value; ?//邊權
? ? int next; ? //同起點的下一條邊的編號
} edge[N << 1]; //同起點的邊的集合 N<<1就是2*N，一般的題目，邊的數量通常是小于2*N的，這個看具體的題目要求
int head[N]; ? ?//以i為起點的邊的集合入口處
//加入一條邊，x起點，y終點，value邊權
void add_edge(int x, int y, int value) {
? ? edge[++idx].to = y; ? ? ? ? //終點
? ? edge[idx].value = value; ? ?//權值
? ? edge[idx].next = head[x]; ? //以x為起點上一條邊的編號，也就是與這個邊起點相同的上一條邊的編號
? ? head[x] = idx; ? ? ? ? ? ? ?//更新以x為起點上一條邊的編號
}
/**
?* 測試數據
?4 6
?2 1 1
?1 3 2
?4 1 4
?2 4 6
?4 2 3
?3 4 5
?*/
int main() {
? ? cin >> n >> m;
? ? //m條邊
? ? for (int i = 1; i <= m; i++) {
? ? ? ? int u, v, l; ? ? ? ? ? ? ? ?//點u到點v有一條權值為l的邊
? ? ? ? cin >> u >> v >> l;
? ? ? ? //加入到鏈式前向星
? ? ? ? add_edge(u, v, l);
? ? }
? ? //遍歷每個結點
? ? for (int i = 1; i <= n; i++) {
? ? ? ? printf("出發點：%d ", i);
? ? ? ? for (int j = head[i]; j; j = edge[j].next) ?//遍歷每個結點的每一條邊
? ? ? ? ? ? printf(" 目標點：%d,權值：%d;", edge[j].to, edge[j].value);
? ? ? ? puts("");
? ? }
? ? return 0;
}
7、 結構體+數組(2)
為什么鏈式前向星有兩種實現方法呢？這其實是看用不用的問題，如果它用了，那么就是在加邊的最后需要++，如果不用，進來就++。
第二個變化就是如果用了，那么就不能用做默認值了，所以需要初始化memset(head,-1 ,sizeof head);
第三個變化就是遍歷時的條件變了，成了j!=-1,而不用的就是j就行了，我個人還是喜歡用不帶的那個，就是上面的。是因為網上好多網友喜歡這種方式，如果我們看其它人的題解時，可能看不懂，所以也要了解一下。
#include <bits/stdc++.h>
using namespace std;
const int N = 1010; ? ? //點數最大值
int n, m, idx; ? ? ? ? ?//n個點，m條邊,idx是新結點加入的數據內索引號
//鏈式前向星
struct Edge {
? ? int to; ? ? //到哪個結點
? ? int value; ?//邊權
? ? int next; ? //同起點的下一條邊的編號
} edge[N << 1]; //同起點的邊的集合 N<<1就是2*N，一般的題目，邊的數量通常是小于2*N的，這個看具體的題目要求
int head[N]; ? ?//以i為起點的邊的集合入口處
//加入一條邊，x起點，y終點，value邊權
void add_edge(int x, int y, int value) {
? ? edge[idx].to = y; ? ? ? ? ? //終點
? ? edge[idx].value = value; ? ?//權值
? ? edge[idx].next = head[x]; ? //以x為起點上一條邊的編號，也就是與這個邊起點相同的上一條邊的編號
? ? head[x] = idx++; ? ? ? ? ? ?//更新以x為起點上一條邊的編號
}
/**
?* 測試數據
?4 6
?2 1 1
?1 3 2
?4 1 4
?2 4 6
?4 2 3
?3 4 5
?*/
int main() {
? ? cin >> n >> m;
? ? //初始化head數組
? ? memset(head, -1, sizeof head);
? ? //m條邊
? ? for (int i = 1; i <= m; i++) {
? ? ? ? int u, v, l; ? ? ? ? ? ? ? ?//點u到點v有一條權值為l的邊
? ? ? ? cin >> u >> v >> l;
? ? ? ? //加入到鏈式前向星
? ? ? ? add_edge(u, v, l);
? ? }
? ? //遍歷每個結點
? ? for (int i = 1; i <= n; i++) {
? ? ? ? printf("出發點：%d ", i);
? ? ? ? for (int j = head[i]; j != -1; j = edge[j].next) ?//遍歷每個結點的每一條邊
? ? ? ? ? ? printf(" 目標點：%d,權值：%d;", edge[j].to, edge[j].value);
? ? ? ? puts("");
? ? }
? ? return 0;
}原文鏈接：https://blog.csdn.net/weixin_46931877/article/details/123681234
相關推薦
- 2023-03-25 Redis實現UV統計的示例代碼_Redis
- 2022-08-25 python并發場景鎖的使用方法_python
- 2022-04-04 Kotlin中協程的創建過程詳析_Android
- 2022-12-29 Python?Base64編碼和解碼操作_python
- 2022-07-08 Python實現超快窗口截圖功能詳解_python
- 2022-05-04 Python的五個標準數據類型你認識幾個_python
- 2022-09-27 使用Python?matplotlib繪制簡單的柱形圖、折線圖和直線圖_python
- 2022-08-10 Python實現以主程序的形式執行模塊_python
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速