无向图的邻接表表示求度
时间: 2023-11-27 16:48:25 浏览: 93
无向图的邻接表表示求度可以通过遍历邻接表中每个节点的链表来实现。具体步骤如下:
1. 定义一个变量degree,用于记录度数。
2. 遍历邻接表中与该节点相连的所有节点,每遍历一个节点,degree加1。
3. 遍历完所有相连节点后,degree即为该节点的度数。
下面是一个C++的示例代码:
```cpp
int getDegree(vector<vector<int>>& graph, int node) {
int degree = 0;
for (int i = 0; i < graph[node].size(); i++) {
degree++;
}
return degree;
}
```
其中,graph是邻接表,node是要求度数的节点。
相关问题
无向图的邻接表的代码实现
无向图的邻接表可以使用一个数组来表示,数组中的每个元素都是一个链表,链表中存储了与该顶点相邻的所有顶点。可以使用 STL 中的 vector 和 list 来实现。以下是一个简单的 C++ 代码示例:
```cpp
#include <iostream>
#include <vector>
#include <list>
using namespace std;
// 无向图邻接表的实现
class Graph {
public:
Graph(int V) {
this->V = V;
adjList.resize(V);
}
// 添加边
void addEdge(int u, int v) {
adjList[u].push_back(v);
adjList[v].push_back(u);
}
// 打印邻接表
void printAdjList() {
for (int i = 0; i < V; ++i) {
cout << i << ": ";
for (auto v : adjList[i]) {
cout << v << " ";
}
cout << endl;
}
}
private:
int V; // 顶点数
vector<list<int>> adjList; // 邻接表
};
int main() {
Graph g(6);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.addEdge(2, 5);
g.addEdge(3, 4);
g.addEdge(4, 5);
g.printAdjList();
return 0;
}
```
输出结果为:
```
0:
1: 2 3
2: 1 4 5
3: 1 4
4: 2 3 5
5: 2 4
```
其中,每行的第一个数字表示顶点的编号,后面的数字表示与该顶点相邻的顶点编号。
有向图邻接矩阵表示法
有向图邻接矩阵表示法是一种常见的图的表示方法,它使用一个二维数组来表示有向图中各个节点之间的关系。
具体来说,如果有一个有向图 G=(V,E),其中 V={v1,v2,...,vn} 表示节点集合,E 表示边的集合,那么可以使用一个 n×n 的二维数组 A 来表示这个图,其中 A[i][j] 表示从节点 i 到节点 j 是否有一条边。如果有边,那么 A[i][j] 的值为 1;否则,A[i][j] 的值为 0。
更进一步地,如果有向图中的边有权重,那么可以将 A[i][j] 的值改为边的权重。
有向图邻接矩阵表示法的优点是可以快速地判断两个节点之间是否有边,时间复杂度为 O(1)。缺点是如果图比较稀疏,即节点数远大于边数,那么邻接矩阵会占用大量的空间,造成浪费。此外,邻接矩阵表示法也不适合表示带有环的图。