資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚學
法律學用連結串列表示圖的 C++ 程式
圖的關聯矩陣是圖的另一種表示形式，用於將其儲存到記憶體中。此矩陣不是一個方陣。關聯矩陣的階數是 V x E。其中 V 是頂點數，E 是圖中的邊數。
在此矩陣的每一行中，我們放置頂點，而在每列中放置邊。在此表示形式中，對於邊 e {u, v}，將在列 e 中用 1 來標記 u 和 v 位置。
鄰接矩陣表示的複雜性
計算關聯矩陣表示需要 O(V x E) 量級空間。對於完全圖，邊數將是 V(V-1)/2。因此，關聯矩陣在記憶體中佔用的空間較大。
輸入
輸出
演算法
add_edge(adj_list, u, v)
輸入 − 邊 {u,v} 的 u 和 v 以及鄰接表
輸出 − 圖 G 的鄰接表
Begin Append v into the list at index u Append u into the list at index v End
示例程式碼
#include<iostream>
#include<list>
#include<iterator>
using namespace std;
void displayAdjList(list<int> adj_list[], int v) {
for(int i = 0; i<v; i++) {
cout << i << "--->";
list<int> :: iterator it;
for(it = adj_list[i].begin(); it != adj_list[i].end(); ++it) {
cout << *it << " ";
}
cout << endl;
}
}
void add_edge(list<int> adj_list[], int u, int v) { //add v into the list u, and u into list v
adj_list[u].push_back(v);
adj_list[v].push_back(u);
}
main(int argc, char* argv[]) {
int v = 6; //there are 6 vertices in the graph
//create an array of lists whose size is 6
list<int> adj_list[v];
add_edge(adj_list, 0, 4);
add_edge(adj_list, 0, 3);
add_edge(adj_list, 1, 2);
add_edge(adj_list, 1, 4);
add_edge(adj_list, 1, 5);
add_edge(adj_list, 2, 3);
add_edge(adj_list, 2, 5);
add_edge(adj_list, 5, 3);
add_edge(adj_list, 5, 4);
displayAdjList(adj_list, v);
}輸出
0--->4 3 1--->2 4 5 2--->1 3 5 3--->0 2 5 4--->0 1 5 5--->1 2 3 4
更新於： 2019 年 7 月 30 日
1 千次瀏覽
廣告