リンクリストを使用してグラフを表現するC++プログラム
グラフの接続行列は、メモリに保存するグラフの別の表現です。この行列は正方行列ではありません。接続行列の次数はVxEです。ここで、Vは頂点の数、Eはグラフのエッジの数です。
この行列の各行に頂点を配置し、各列にエッジを配置します。エッジe{u、v}のこの表現では、列eの場所uとvに対して1でマークされます。
隣接行列表現の複雑さ
-
接続行列表現は、計算中に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
-
接続行列を使用してグラフを表現するC++プログラム
グラフの接続行列は、メモリに保存するグラフの別の表現です。この行列は正方行列ではありません。接続行列の次数はVxEです。ここで、Vは頂点の数、Eはグラフのエッジの数です。 この行列の各行に頂点を配置し、各列にエッジを配置します。エッジe{u、v}のこの表現では、列eの場所uとvに対して1でマークされます。 隣接行列表現の複雑さ 接続行列表現は、計算中にO（Vx E）のスペースを取ります。完全グラフの場合、エッジの数はV（V-1）/2になります。したがって、接続行列はメモリ内でより大きなスペースを取ります。 入力 出力 E0 E1 E2
-
隣接行列を使用してグラフを表現するC++プログラム
グラフの隣接行列は、サイズV x Vの正方行列です。Vは、グラフGの頂点の数です。この行列では、各辺にV個の頂点がマークされています。グラフにiからjの頂点までのエッジがある場合、i thの隣接行列に 行とjth 列は1（または加重グラフの場合はゼロ以外の値）になります。それ以外の場合、その場所は0を保持します。 隣接行列表現の複雑さ 隣接行列表現はO（V 2 ）計算中のスペースの量。グラフに最大数のエッジと最小数のエッジがある場合、どちらの場合も必要なスペースは同じになります。 入力 出力 0 1 2 3 4 5