用邻接表的方式建立图并求其度(代码)
时间: 2023-11-11 21:13:38 浏览: 32
好的,以下是用邻接表的方式建立图并求其度的代码示例(以C++为例):
```c++
#include <iostream>
#include <vector>
using namespace std;
// 定义邻接表节点
struct AdjListNode {
int dest; // 目标顶点
struct AdjListNode* next; // 指向下一个邻接点的指针
};
// 定义邻接表
struct AdjList {
struct AdjListNode* head; // 指向邻接表中第一个节点的指针
};
// 定义图
class Graph {
private:
int V; // 顶点数
vector<AdjList> adj; // 邻接表数组
public:
Graph(int v) {
V = v;
adj.resize(V); // 初始化邻接表数组
for (int i = 0; i < V; ++i) {
adj[i].head = NULL; // 初始化邻接表中的头节点指针
}
}
// 添加边
void addEdge(int src, int dest) {
// 添加从src到dest的边
AdjListNode* newNode = new AdjListNode;
newNode->dest = dest;
newNode->next = adj[src].head;
adj[src].head = newNode;
// 添加从dest到src的边
newNode = new AdjListNode;
newNode->dest = src;
newNode->next = adj[dest].head;
adj[dest].head = newNode;
}
// 求顶点的度
int getDegree(int v) {
int degree = 0;
AdjListNode* cur = adj[v].head;
while (cur) {
++degree;
cur = cur->next;
}
return degree;
}
};
// 测试
int main() {
// 创建图
Graph g(5);
g.addEdge(0, 1);
g.addEdge(0, 4);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 3);
g.addEdge(3, 4);
// 求顶点的度
for (int i = 0; i < 5; ++i) {
cout << "Vertex " << i << " has degree " << g.getDegree(i) << endl;
}
return 0;
}
```
在上面的代码中,我们首先定义了邻接表节点和邻接表结构体,然后定义了Graph类来表示图。在Graph类中,我们使用了一个vector来存储邻接表数组,其中每个元素是一个邻接表结构体。在添加边时,我们同时添加了两条边,因为无向图中的边是双向的。在求顶点的度时,我们遍历了该顶点的邻接表,并统计了节点的个数。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)