C++處理圖存儲(chǔ)的方式分享
更新時(shí)間：2022年03月31日 09:04:38 作者：蘇州程序大白
這篇文章主要介紹了C++處理圖存儲(chǔ)的方式分享，文章圍繞鄰接矩陣、鄰接表、鏈?zhǔn)角跋虻闹黝}展開詳細(xì)內(nèi)容，具有一定的參考價(jià)值，需要的小伙伴可以參考一下
一、鄰接矩陣
適用：
稠密圖，就是說(shuō)點(diǎn)數(shù)的平方與邊數(shù)接近的情況，換句話說(shuō)就是邊特別多。
不適用：
稀疏圖，就是點(diǎn)數(shù)的平方與邊數(shù)差的特別多，邊數(shù)少，但點(diǎn)數(shù)多，就不行了，因?yàn)榭臻g占用太大了。
實(shí)現(xiàn)代碼：
#include <bits/stdc++.h>
using namespace std;
const int N = 1010; //圖的最大點(diǎn)數(shù)量
int n;
int v[N][N]; ? ? ? ?//鄰接矩陣
/**
?* 測(cè)試數(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];
? ? //下面的代碼將找到與點(diǎn)i有直接連接的每一個(gè)點(diǎn)以及那條邊的長(zhǎng)度
? ? 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; //圖的最大點(diǎn)數(shù)量
struct Edge { ? ? ? //記錄邊的終點(diǎn)，邊權(quán)的結(jié)構(gòu)體
? ? int to; ? ? ? ? //終點(diǎn)
? ? int value; ? ? ?//邊權(quán)
};
int n, m; //表示圖中有n個(gè)點(diǎn)，m條邊
vector<Edge> p[N]; ?//使用vector的鄰接表
/**
?* 測(cè)試數(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; ? ? ? ? ? ? ? ?//點(diǎn)u到點(diǎn)v有一條權(quán)值為l的邊
? ? ? ? cin >> u >> v >> l;
? ? ? ? p[u].push_back({v, l});
? ? }
? ? //輸出
? ? for (int i = 1; i <= n; i++) {
? ? ? ? printf("出發(fā)點(diǎn)：%d ", i);
? ? ? ? for (int j = 0; j < p[i].size(); j++)
? ? ? ? ? ? printf(" 目標(biāo)點(diǎn)：%d,權(quán)值：%d;", p[i][j].to, p[i][j].value);
? ? ? ? puts("");
? ? }
? ? return 0;
}
三、鏈?zhǔn)角跋蛐?/h2>
鏈?zhǔn)角跋蛐鞘青徑颖泶鎴D的第二種方法，它自己還有兩種寫法，比 用向量存圖的那種鄰接表要快 。
它是一種以邊為主的存圖方式，idxidx表示最后一條邊的預(yù)存入的房間號(hào),$head[i$]表示以$i$為起點(diǎn)第一條邊的房間號(hào)。
每條邊有三個(gè)屬性：
- 從
$head[i]$出發(fā)到哪個(gè)結(jié)點(diǎn)的邊？ - 這條邊的邊權(quán)是多少？
- 這條邊的下一條邊是誰(shuí)？（下一條邊的房間號(hào)）
鏈?zhǔn)角跋蛐怯腥N變形，需要同學(xué)們都掌握，找一種自己最喜歡的背下來(lái)，其它兩種要求能看懂，因?yàn)槠渌藢戭}解，可能使用了其它方式。
1、AcWing方式（純數(shù)組）
#include <bits/stdc++.h>
using namespace std;
const int N = 1010; ? ? //點(diǎn)數(shù)最大值
int n, m; ? ? ? ? ? ? ? //n個(gè)點(diǎn)，m條邊
//idx是新結(jié)點(diǎn)加入的數(shù)據(jù)內(nèi)索引號(hào)
//h[N]表示有N條單鏈表的頭,e[M]代表每個(gè)節(jié)點(diǎn)的值,ne[M]代表每個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)號(hào)
int h[N], e[N << 1], ne[N << 1], w[N << 1], idx;
//鏈?zhǔn)角跋蛐?
void add(int a, int b, int l) {
? ? e[idx] = b, ne[idx] = h[a], w[idx] = l, h[a] = idx++;
}
/**
?* 測(cè)試數(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,每個(gè)頭節(jié)點(diǎn)寫成-1
? ? memset(h, -1, sizeof h);
? ? //m條邊
? ? for (int i = 1; i <= m; i++) {
? ? ? ? int u, v, l; ? ? ? ? ? ? ? ?//點(diǎn)u到點(diǎn)v有一條權(quán)值為l的邊
? ? ? ? cin >> u >> v >> l;
? ? ? ? //加入到鏈?zhǔn)角跋蛐?
? ? ? ? add(u, v, l);
? ? }
? ? //遍歷每個(gè)結(jié)點(diǎn)
? ? for (int i = 1; i <= n; i++) {
? ? ? ? printf("出發(fā)點(diǎn)：%d ", i);
? ? ? ? for (int j = h[i]; j != -1; j = ne[j])
? ? ? ? ? ? printf(" 目標(biāo)點(diǎn)：%d,權(quán)值：%d;", e[j], w[j]);
? ? ? ? puts("");
? ? }
? ? return 0;
}
三、Acwing圖的存儲(chǔ)方式
方法：使用一個(gè)二維數(shù)組 g 來(lái)存邊，其中 g[u][v] 為 1 表示存在 到的邊，為 0 表示不存在。如果是帶邊權(quán)的圖，可以在 g[u][v] 中存儲(chǔ)到的邊的邊權(quán)。
案例：
最短距離Dijkstra
從s到t的最短距離算法流程：
b[]表示當(dāng)前已經(jīng)確定最短距離的點(diǎn)。
dis[s] = 0, dis[其他] = +∞ for (int i = 1; i <= n; i ++)
t：不在b中的最短距離的點(diǎn)
將t加入b[]
使用t更新其他未被確定的點(diǎn)的距離
代碼實(shí)現(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)用
鄰接矩陣只適用于沒(méi)有重邊（或重邊可以忽略）的情況。
其最顯著的優(yōu)點(diǎn)是可以查詢一條邊是否存在。
由于鄰接矩陣在稀疏圖上效率很低（尤其是在點(diǎn)數(shù)較多的圖上，空間無(wú)法承受），所以一般只會(huì)在稠密圖上使用鄰接矩陣。
3、鄰接表
使用一個(gè)支持動(dòng)態(tài)增加元素的數(shù)據(jù)結(jié)構(gòu)構(gòu)成的數(shù)組，如 vector g[n + 1] 來(lái)存邊，其中 g[u] 存儲(chǔ)的是點(diǎn)的所有出邊的相關(guān)信息（終點(diǎn)、邊權(quán)等）。
4、代碼實(shí)現(xiàn)
數(shù)據(jù)定義：
h是n個(gè)鏈表的鏈表頭, e存的是每一個(gè)節(jié)點(diǎn)的值, 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; ? ?// 標(biāo)記已經(jīng)被遍歷過(guò)了
? ? 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]; ? ?// 定義隊(duì)列?
? ? 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)用
存各種圖都很適合，除非有特殊需求（如需要快速查詢一條邊是否存在，且點(diǎn)數(shù)較少，可以使用鄰接矩陣）。
尤其適用于需要對(duì)一個(gè)點(diǎn)的所有出邊進(jìn)行排序的場(chǎng)合。
5、實(shí)現(xiàn)案例
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10, M = N * 2;
// h是n個(gè)鏈表的鏈表頭, e存的是每一個(gè)節(jié)點(diǎn)的值, 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; ? ?// 標(biāo)記已經(jīng)被遍歷過(guò)了
? ? 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]; ? ?// 定義隊(duì)列?
? ? 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; ? ? //點(diǎn)數(shù)最大值
int n, m, idx; ? ? ? ? ?//n個(gè)點(diǎn)，m條邊,idx是新結(jié)點(diǎn)加入的數(shù)據(jù)內(nèi)索引號(hào)
//鏈?zhǔn)角跋蛐?
struct Edge {
? ? int to; ? ? //到哪個(gè)結(jié)點(diǎn)
? ? int value; ?//邊權(quán)
? ? int next; ? //同起點(diǎn)的下一條邊的編號(hào)
} edge[N << 1]; //同起點(diǎn)的邊的集合 N<<1就是2*N，一般的題目，邊的數(shù)量通常是小于2*N的，這個(gè)看具體的題目要求
int head[N]; ? ?//以i為起點(diǎn)的邊的集合入口處
//加入一條邊，x起點(diǎn)，y終點(diǎn)，value邊權(quán)
void add_edge(int x, int y, int value) {
? ? edge[++idx].to = y; ? ? ? ? //終點(diǎn)
? ? edge[idx].value = value; ? ?//權(quán)值
? ? edge[idx].next = head[x]; ? //以x為起點(diǎn)上一條邊的編號(hào)，也就是與這個(gè)邊起點(diǎn)相同的上一條邊的編號(hào)
? ? head[x] = idx; ? ? ? ? ? ? ?//更新以x為起點(diǎn)上一條邊的編號(hào)
}
/**
?* 測(cè)試數(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; ? ? ? ? ? ? ? ?//點(diǎn)u到點(diǎn)v有一條權(quán)值為l的邊
? ? ? ? cin >> u >> v >> l;
? ? ? ? //加入到鏈?zhǔn)角跋蛐?
? ? ? ? add_edge(u, v, l);
? ? }
? ? //遍歷每個(gè)結(jié)點(diǎn)
? ? for (int i = 1; i <= n; i++) {
? ? ? ? printf("出發(fā)點(diǎn)：%d ", i);
? ? ? ? for (int j = head[i]; j; j = edge[j].next) ?//遍歷每個(gè)結(jié)點(diǎn)的每一條邊
? ? ? ? ? ? printf(" 目標(biāo)點(diǎn)：%d,權(quán)值：%d;", edge[j].to, edge[j].value);
? ? ? ? puts("");
? ? }
? ? return 0;
}
7、 結(jié)構(gòu)體+數(shù)組(2)
為什么鏈?zhǔn)角跋蛐怯袃煞N實(shí)現(xiàn)方法呢？這其實(shí)是看用不用的問(wèn)題，如果它用了，那么就是在加邊的最后需要++，如果不用，進(jìn)來(lái)就++。
第二個(gè)變化就是如果用了，那么就不能用做默認(rèn)值了，所以需要初始化memset(head,-1 ,sizeof head);
第三個(gè)變化就是遍歷時(shí)的條件變了，成了j!=-1,而不用的就是j就行了，我個(gè)人還是喜歡用不帶的那個(gè)，就是上面的。是因?yàn)榫W(wǎng)上好多網(wǎng)友喜歡這種方式，如果我們看其它人的題解時(shí)，可能看不懂，所以也要了解一下。
#include <bits/stdc++.h>
using namespace std;
const int N = 1010; ? ? //點(diǎn)數(shù)最大值
int n, m, idx; ? ? ? ? ?//n個(gè)點(diǎn)，m條邊,idx是新結(jié)點(diǎn)加入的數(shù)據(jù)內(nèi)索引號(hào)
//鏈?zhǔn)角跋蛐?
struct Edge {
? ? int to; ? ? //到哪個(gè)結(jié)點(diǎn)
? ? int value; ?//邊權(quán)
? ? int next; ? //同起點(diǎn)的下一條邊的編號(hào)
} edge[N << 1]; //同起點(diǎn)的邊的集合 N<<1就是2*N，一般的題目，邊的數(shù)量通常是小于2*N的，這個(gè)看具體的題目要求
int head[N]; ? ?//以i為起點(diǎn)的邊的集合入口處
//加入一條邊，x起點(diǎn)，y終點(diǎn)，value邊權(quán)
void add_edge(int x, int y, int value) {
? ? edge[idx].to = y; ? ? ? ? ? //終點(diǎn)
? ? edge[idx].value = value; ? ?//權(quán)值
? ? edge[idx].next = head[x]; ? //以x為起點(diǎn)上一條邊的編號(hào)，也就是與這個(gè)邊起點(diǎn)相同的上一條邊的編號(hào)
? ? head[x] = idx++; ? ? ? ? ? ?//更新以x為起點(diǎn)上一條邊的編號(hào)
}
/**
?* 測(cè)試數(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; ? ? ? ? ? ? ? ?//點(diǎn)u到點(diǎn)v有一條權(quán)值為l的邊
? ? ? ? cin >> u >> v >> l;
? ? ? ? //加入到鏈?zhǔn)角跋蛐?
? ? ? ? add_edge(u, v, l);
? ? }
? ? //遍歷每個(gè)結(jié)點(diǎn)
? ? for (int i = 1; i <= n; i++) {
? ? ? ? printf("出發(fā)點(diǎn)：%d ", i);
? ? ? ? for (int j = head[i]; j != -1; j = edge[j].next) ?//遍歷每個(gè)結(jié)點(diǎn)的每一條邊
? ? ? ? ? ? printf(" 目標(biāo)點(diǎn)：%d,權(quán)值：%d;", edge[j].to, edge[j].value);
? ? ? ? puts("");
? ? }
? ? return 0;
}到此這篇關(guān)于C++處理圖存儲(chǔ)的方式分享的文章就介紹到這了,更多相關(guān)C++處理圖存儲(chǔ)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:
相關(guān)文章
深入C++拷貝構(gòu)造函數(shù)的總結(jié)詳解
本篇文章是對(duì)C++中拷貝構(gòu)造函數(shù)進(jìn)行了總結(jié)與介紹。需要的朋友參考下2013-05-05
這篇文章主要為大家介紹了C語(yǔ)言常量和字符串，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2021-12-12
基于opencv實(shí)現(xiàn)視頻中的顏色識(shí)別功能
這篇文章主要介紹了基于opencv實(shí)現(xiàn)視頻中的顏色識(shí)別功能,文章詳細(xì)介紹了顏色識(shí)別的原理及opencv中的顏色模型，基于c++代碼實(shí)現(xiàn)顏色識(shí)別功能，需要的朋友可以參考下2022-07-07
Pthread并發(fā)編程之線程基本元素和狀態(tài)的剖析
本篇文章主要給大家介紹pthread并發(fā)編程當(dāng)中關(guān)于線程的基礎(chǔ)概念，并且深入剖析進(jìn)程的相關(guān)屬性和設(shè)置，以及線程在內(nèi)存當(dāng)中的布局形式，幫助大家深刻理解線程2022-11-11
C++示例分析內(nèi)聯(lián)函數(shù)與引用變量及函數(shù)重載的使用
為了消除函數(shù)調(diào)用的時(shí)空開銷，C++ 提供一種提高效率的方法，即在編譯時(shí)將函數(shù)調(diào)用處用函數(shù)體替換，類似于C語(yǔ)言中的宏展開。這種在函數(shù)調(diào)用處直接嵌入函數(shù)體的函數(shù)稱為內(nèi)聯(lián)函數(shù)（Inline Function），又稱內(nèi)嵌函數(shù)或者內(nèi)置函數(shù)2022-08-08
一般而言，每個(gè)C++/C程序通常由頭文件和定義文件組成。頭文件作為一種包含功能函數(shù)、數(shù)據(jù)接口聲明的載體文件，主要用于保存程序的聲明，而定義文件用于保存程序的實(shí)現(xiàn) 。2017-02-02
c++動(dòng)態(tài)庫(kù)調(diào)用的實(shí)現(xiàn)
本文主要介紹了c++動(dòng)態(tài)庫(kù)調(diào)用的實(shí)現(xiàn)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-07-07
這篇文章主要介紹了c語(yǔ)言中形參與實(shí)參的關(guān)系，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-07-07
C語(yǔ)言語(yǔ)句的執(zhí)行默認(rèn)順序執(zhí)行(從上往下依次執(zhí)行),編程語(yǔ)言一般除了默認(rèn)的順序執(zhí)行以外，還提供分支執(zhí)行和循環(huán)執(zhí)行的語(yǔ)法，讓我們一起來(lái)看看2022-05-05
C語(yǔ)言指針基礎(chǔ)知識(shí)實(shí)例講解
這篇文章主要介紹了C語(yǔ)言指針基本知識(shí)實(shí)例講解，文中實(shí)例講解的很清晰，有不太懂的同學(xué)可以研究下2021-02-02