C++處理圖存儲的方式分享
一、鄰接矩陣
適用:
稠密圖,就是說點數(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(" 目標(biāo)點:%d,權(quán)值:%d;", p[i][j].to, p[i][j].value); ? ? ? ? puts(""); ? ? } ? ? return 0; }
三、鏈?zhǔn)角跋蛐?/h2>
鏈?zhǔn)角跋蛐鞘青徑颖泶鎴D的第二種方法,它自己還有兩種寫法,比 用向量存圖的那種鄰接表要快 。
它是一種以邊為主的存圖方式,idxidx
表示最后一條邊的預(yù)存入的房間號,$head[i$]表示以$i$為起點第一條邊的房間號。
每條邊有三個屬性:
- 從
$head[i]$
出發(fā)到哪個結(jié)點的邊? - 這條邊的邊權(quán)是多少?
- 這條邊的下一條邊是誰?(下一條邊的房間號)
鏈?zhǔn)角跋蛐怯腥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; //鏈?zhǔn)角跋蛐? 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; ? ? ? ? //加入到鏈?zhǔn)角跋蛐? ? ? ? ? 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(" 目標(biāo)點:%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[]表示當(dāng)前已經(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; ? ?// 標(biāo)記已經(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ù)較少,可以使用鄰接矩陣)。
尤其適用于需要對一個點的所有出邊進(jìn)行排序的場合。
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; ? ?// 標(biāo)記已經(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)索引號 //鏈?zhǔn)角跋蛐? 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; ? ? ? ? //加入到鏈?zhǔn)角跋蛐? ? ? ? ? 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(" 目標(biāo)點:%d,權(quán)值:%d;", edge[j].to, edge[j].value); ? ? ? ? puts(""); ? ? } ? ? return 0; }
7、 結(jié)構(gòu)體+數(shù)組(2)
為什么鏈?zhǔn)角跋蛐怯袃煞N實現(xiàn)方法呢?這其實是看用不用的問題,如果它用了,那么就是在加邊的最后需要++,如果不用,進(jìn)來就++。
第二個變化就是如果用了,那么就不能用做默認(rè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)索引號 //鏈?zhǔn)角跋蛐? 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; ? ? ? ? //加入到鏈?zhǔn)角跋蛐? ? ? ? ? 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(" 目標(biāo)點:%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)文章
深入C++拷貝構(gòu)造函數(shù)的總結(jié)詳解
本篇文章是對C++中拷貝構(gòu)造函數(shù)進(jìn)行了總結(jié)與介紹。需要的朋友參考下2013-05-05Pthread并發(fā)編程之線程基本元素和狀態(tài)的剖析
本篇文章主要給大家介紹pthread并發(fā)編程當(dāng)中關(guān)于線程的基礎(chǔ)概念,并且深入剖析進(jìn)程的相關(guān)屬性和設(shè)置,以及線程在內(nèi)存當(dāng)中的布局形式,幫助大家深刻理解線程2022-11-11C++示例分析內(nèi)聯(lián)函數(shù)與引用變量及函數(shù)重載的使用
為了消除函數(shù)調(diào)用的時空開銷,C++ 提供一種提高效率的方法,即在編譯時將函數(shù)調(diào)用處用函數(shù)體替換,類似于C語言中的宏展開。這種在函數(shù)調(diào)用處直接嵌入函數(shù)體的函數(shù)稱為內(nèi)聯(lián)函數(shù)(Inline Function),又稱內(nèi)嵌函數(shù)或者內(nèi)置函數(shù)2022-08-08