数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究使用邻接表表示图的 C++ 程序
图的邻接表表示法是链表表示法。在此表示法中，我们有一个列表数组。数组大小为 V。其中 V 是顶点数。换句话说，我们可以说我们有一个数组来存储 V 个不同的列表。如果列表头是顶点 u，则表示它将保存 u 的所有相邻顶点。
邻接表表示法的复杂度
对于无向图，此表示法的复杂度为 O(V+2E)；对于有向图，此表示法的复杂度为 O(V+E)。如果边数增加，则所需空间也会增加。
输入
输出
算法
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 日
4K+ 浏览量
广告