C++處理圖存儲的方式分享
更新時間：2022年03月31日 09:04:38 作者：蘇州程序大白
這篇文章主要介紹了C++處理圖存儲的方式分享，文章圍繞鄰接矩陣、鄰接表、鏈式前向的主題展開詳細內(nèi)容，具有一定的參考價值，需要的小伙伴可以參考一下
一、鄰接矩陣
適用：
稠密圖，就是說點數(shù)的平方與邊數(shù)接近的情況，換句話說就是邊特別多。
不適用：
稀疏圖，就是點數(shù)的平方與邊數(shù)差的特別多，邊數(shù)少，但點數(shù)多，就不行了，因為空間占用太大了。
實現(xiàn)代碼：
#include <bits/stdc++.h>
using namespace std;
const int N = 1010; //圖的最大點數(shù)量
int n;
int v[N][N]; ? ? ? ?//鄰接矩陣
/**
?* 測試數(shù)據(jù)
?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; //圖的最大點數(shù)量
struct Edge { ? ? ? //記錄邊的終點，邊權(quán)的結(jié)構(gòu)體
? ? int to; ? ? ? ? //終點
? ? int value; ? ? ?//邊權(quán)
};
int n, m; //表示圖中有n個點，m條邊
vector<Edge> p[N]; ?//使用vector的鄰接表
/**
?* 測試數(shù)據(jù)
?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有一條權(quán)值為l的邊
? ? ? ? cin >> u >> v >> l;
? ? ? ? p[u].push_back({v, l});
? ? }
? ? //輸出
? ? for (int i = 1; i <= n; i++) {
? ? ? ? printf("出發(fā)點：%d ", i);
? ? ? ? for (int j = 0; j < p[i].size(); j++)
? ? ? ? ? ? printf(" 目標點：%d,權(quán)值：%d;", p[i][j].to, p[i][j].value);
? ? ? ? puts("");
? ? }
? ? return 0;
}
三、鏈式前向星
鏈式前向星是鄰接表存圖的第二種方法，它自己還有兩種寫法，比 用向量存圖的那種鄰接表要快 。
它是一種以邊為主的存圖方式，idxidx表示最后一條邊的預(yù)存入的房間號,$head[i$]表示以$i$為起點第一條邊的房間號。
每條邊有三個屬性：
- 從
$head[i]$出發(fā)到哪個結(jié)點的邊？ - 這條邊的邊權(quán)是多少？
- 這條邊的下一條邊是誰？（下一條邊的房間號）
鏈式前向星有三種變形，需要同學(xué)們都掌握，找一種自己最喜歡的背下來，其它兩種要求能看懂，因為其它人寫題解，可能使用了其它方式。
1、AcWing方式（純數(shù)組）
#include <bits/stdc++.h>
using namespace std;
const int N = 1010; ? ? //點數(shù)最大值
int n, m; ? ? ? ? ? ? ? //n個點，m條邊
//idx是新結(jié)點加入的數(shù)據(jù)內(nèi)索引號
//h[N]表示有N條單鏈表的頭,e[M]代表每個節(jié)點的值,ne[M]代表每個節(jié)點的下一個節(jié)點號
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++;
}
/**
?* 測試數(shù)據(jù)
?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,每個頭節(jié)點寫成-1
? ? memset(h, -1, sizeof h);
? ? //m條邊
? ? for (int i = 1; i <= m; i++) {
? ? ? ? int u, v, l; ? ? ? ? ? ? ? ?//點u到點v有一條權(quán)值為l的邊
? ? ? ? cin >> u >> v >> l;
? ? ? ? //加入到鏈式前向星
? ? ? ? add(u, v, l);
? ? }
? ? //遍歷每個結(jié)點
? ? for (int i = 1; i <= n; i++) {
? ? ? ? printf("出發(fā)點：%d ", i);
? ? ? ? for (int j = h[i]; j != -1; j = ne[j])
? ? ? ? ? ? printf(" 目標點：%d,權(quán)值：%d;", e[j], w[j]);
? ? ? ? puts("");
? ? }
? ? return 0;
}
三、Acwing圖的存儲方式
方法：使用一個二維數(shù)組 g 來存邊，其中 g[u][v] 為 1 表示存在 到的邊，為 0 表示不存在。如果是帶邊權(quán)的圖，可以在 g[u][v] 中存儲到的邊的邊權(quán)。
案例：
最短距離Dijkstra
從s到t的最短距離算法流程：
b[]表示當前已經(jīng)確定最短距離的點。
dis[s] = 0, dis[其他] = +∞ for (int i = 1; i <= n; i ++)
t：不在b中的最短距離的點
將t加入b[]
使用t更新其他未被確定的點的距離
代碼實現(xiàn)：
#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、復(fù)雜度
2、應(yīng)用
鄰接矩陣只適用于沒有重邊（或重邊可以忽略）的情況。
其最顯著的優(yōu)點是可以查詢一條邊是否存在。
由于鄰接矩陣在稀疏圖上效率很低（尤其是在點數(shù)較多的圖上，空間無法承受），所以一般只會在稠密圖上使用鄰接矩陣。
3、鄰接表
使用一個支持動態(tài)增加元素的數(shù)據(jù)結(jié)構(gòu)構(gòu)成的數(shù)組，如 vector g[n + 1] 來存邊，其中 g[u] 存儲的是點的所有出邊的相關(guān)信息（終點、邊權(quán)等）。
4、代碼實現(xiàn)
數(shù)據(jù)定義：
h是n個鏈表的鏈表頭, e存的是每一個節(jié)點的值, 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、深度優(yōu)先遍歷
void dfs(int u) {
? ? st[u] = true; ? ?// 標記已經(jīng)被遍歷過了
? ? for (int i = h[u]; i != -1; i = ne[i]) {
? ? ? ? int j = e[i];
? ? ? ? if (!st[j]) dfs(j);
? ? }
}2、廣度優(yōu)先遍歷
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、復(fù)雜度
4、應(yīng)用
存各種圖都很適合，除非有特殊需求（如需要快速查詢一條邊是否存在，且點數(shù)較少，可以使用鄰接矩陣）。
尤其適用于需要對一個點的所有出邊進行排序的場合。
5、實現(xiàn)案例
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10, M = N * 2;
// h是n個鏈表的鏈表頭, e存的是每一個節(jié)點的值, 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 ++;
}
// 深度優(yōu)先遍歷
void dfs(int u) {
? ? cout << u << ' ';
? ? st[u] = true; ? ?// 標記已經(jīng)被遍歷過了
? ? for (int i = h[u]; i != -1; i = ne[i]) {
? ? ? ? int j = e[i];
? ? ? ? if (!st[j]) dfs(j);
? ? }
}
// 廣度優(yōu)先遍歷?
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 << "深度優(yōu)先遍歷：";
? ? dfs(1);
? ? cout << endl;
? ? cout << "廣度優(yōu)先遍歷：";
? ? bfs();?
? ? return 0;
}6、 結(jié)構(gòu)體+數(shù)組
#include <bits/stdc++.h>
using namespace std;
const int N = 1010; ? ? //點數(shù)最大值
int n, m, idx; ? ? ? ? ?//n個點，m條邊,idx是新結(jié)點加入的數(shù)據(jù)內(nèi)索引號
//鏈式前向星
struct Edge {
? ? int to; ? ? //到哪個結(jié)點
? ? int value; ?//邊權(quán)
? ? int next; ? //同起點的下一條邊的編號
} edge[N << 1]; //同起點的邊的集合 N<<1就是2*N，一般的題目，邊的數(shù)量通常是小于2*N的，這個看具體的題目要求
int head[N]; ? ?//以i為起點的邊的集合入口處
//加入一條邊，x起點，y終點，value邊權(quán)
void add_edge(int x, int y, int value) {
? ? edge[++idx].to = y; ? ? ? ? //終點
? ? edge[idx].value = value; ? ?//權(quán)值
? ? edge[idx].next = head[x]; ? //以x為起點上一條邊的編號，也就是與這個邊起點相同的上一條邊的編號
? ? head[x] = idx; ? ? ? ? ? ? ?//更新以x為起點上一條邊的編號
}
/**
?* 測試數(shù)據(jù)
?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有一條權(quán)值為l的邊
? ? ? ? cin >> u >> v >> l;
? ? ? ? //加入到鏈式前向星
? ? ? ? add_edge(u, v, l);
? ? }
? ? //遍歷每個結(jié)點
? ? for (int i = 1; i <= n; i++) {
? ? ? ? printf("出發(fā)點：%d ", i);
? ? ? ? for (int j = head[i]; j; j = edge[j].next) ?//遍歷每個結(jié)點的每一條邊
? ? ? ? ? ? printf(" 目標點：%d,權(quán)值：%d;", edge[j].to, edge[j].value);
? ? ? ? puts("");
? ? }
? ? return 0;
}
7、 結(jié)構(gòu)體+數(shù)組(2)
為什么鏈式前向星有兩種實現(xiàn)方法呢？這其實是看用不用的問題，如果它用了，那么就是在加邊的最后需要++，如果不用，進來就++。
第二個變化就是如果用了，那么就不能用做默認值了，所以需要初始化memset(head,-1 ,sizeof head);
第三個變化就是遍歷時的條件變了，成了j!=-1,而不用的就是j就行了，我個人還是喜歡用不帶的那個，就是上面的。是因為網(wǎng)上好多網(wǎng)友喜歡這種方式，如果我們看其它人的題解時，可能看不懂，所以也要了解一下。
#include <bits/stdc++.h>
using namespace std;
const int N = 1010; ? ? //點數(shù)最大值
int n, m, idx; ? ? ? ? ?//n個點，m條邊,idx是新結(jié)點加入的數(shù)據(jù)內(nèi)索引號
//鏈式前向星
struct Edge {
? ? int to; ? ? //到哪個結(jié)點
? ? int value; ?//邊權(quán)
? ? int next; ? //同起點的下一條邊的編號
} edge[N << 1]; //同起點的邊的集合 N<<1就是2*N，一般的題目，邊的數(shù)量通常是小于2*N的，這個看具體的題目要求
int head[N]; ? ?//以i為起點的邊的集合入口處
//加入一條邊，x起點，y終點，value邊權(quán)
void add_edge(int x, int y, int value) {
? ? edge[idx].to = y; ? ? ? ? ? //終點
? ? edge[idx].value = value; ? ?//權(quán)值
? ? edge[idx].next = head[x]; ? //以x為起點上一條邊的編號，也就是與這個邊起點相同的上一條邊的編號
? ? head[x] = idx++; ? ? ? ? ? ?//更新以x為起點上一條邊的編號
}
/**
?* 測試數(shù)據(jù)
?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數(shù)組
? ? memset(head, -1, sizeof head);
? ? //m條邊
? ? for (int i = 1; i <= m; i++) {
? ? ? ? int u, v, l; ? ? ? ? ? ? ? ?//點u到點v有一條權(quán)值為l的邊
? ? ? ? cin >> u >> v >> l;
? ? ? ? //加入到鏈式前向星
? ? ? ? add_edge(u, v, l);
? ? }
? ? //遍歷每個結(jié)點
? ? for (int i = 1; i <= n; i++) {
? ? ? ? printf("出發(fā)點：%d ", i);
? ? ? ? for (int j = head[i]; j != -1; j = edge[j].next) ?//遍歷每個結(jié)點的每一條邊
? ? ? ? ? ? printf(" 目標點：%d,權(quán)值：%d;", edge[j].to, edge[j].value);
? ? ? ? puts("");
? ? }
? ? return 0;
}到此這篇關(guān)于C++處理圖存儲的方式分享的文章就介紹到這了,更多相關(guān)C++處理圖存儲內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:
相關(guān)文章
本文通過實例代碼給大家介紹了基于Qt實現(xiàn)視頻播放器功能，代碼簡單易懂，對大家的學(xué)習或工作具有一定的參考借鑒價值，需要的朋友參考下吧2021-09-09
這篇文章主要介紹了STL容器之list源碼詳細解讀,相對于vector的連續(xù)線性空間,list就顯得更加復(fù)雜,它每插入或者刪除一個元素,就配置或釋放一個元素空間,需要的朋友可以參考下2024-01-01
最近在研究把?Qt?的打印信息?輸出的到日志文件中,文件存儲嘗試了2種方法,并通過代碼示例和圖文給大家介紹的非常詳細,具有一定的參考價值,需要的朋友可以參考下2024-04-04
C 數(shù)組允許定義可存儲相同類型數(shù)據(jù)項的變量，結(jié)構(gòu)是 C 編程中另一種用戶自定義的可用的數(shù)據(jù)類型，它允許你存儲不同類型的數(shù)據(jù)項，本篇讓我們來了解C 的結(jié)構(gòu)體內(nèi)存對齊2022-06-06
c++將vector迭代器轉(zhuǎn)換為指針的實現(xiàn)方式
這篇文章主要介紹了c++將vector迭代器轉(zhuǎn)換為指針的實現(xiàn)方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11
線段樹在一些acm題目中經(jīng)常見到,這種數(shù)據(jù)結(jié)構(gòu)主要應(yīng)用在計算幾何和地理信息系統(tǒng)中,這篇文章主要給大家介紹了關(guān)于線段樹以及C++實現(xiàn)的相關(guān)資料,需要的朋友可以參考下2021-07-07
大家好，本篇文章主要講的是C語言中結(jié)構(gòu)體實例解析，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下2022-02-02
淺析C語言中strtol()函數(shù)與strtoul()函數(shù)的用法
這篇文章主要介紹了淺析C語言中strtol()函數(shù)與strtoul()函數(shù)的用法,注意其將字符串轉(zhuǎn)換成long型的區(qū)別,需要的朋友可以參考下2015-08-08
scanf的基本用法除了常規(guī)的輸入操作外還有一些特殊的用法,使用這些用法可以很方便的在輸入中讀取想要的數(shù)據(jù),這篇文章主要介紹了scanf的用法,需要的朋友可以參考下2023-12-12
本文介紹了如何使用 C 語言實現(xiàn)一個基本的線程池,線程池的實現(xiàn)包括工作線程、任務(wù)隊列、任務(wù)調(diào)度、線程池的初始化、任務(wù)添加、銷毀等步驟,感興趣的朋友跟隨小編一起看看吧2025-01-01