以邻接表作存储结构,编写程序对给定的无向图G(包含n个顶点,编号为0至n-1)进行广度优先遍历,并在遍历的过程中计算图G的连通分量个数及边的数目。
时间: 2024-03-08 17:47:55 浏览: 20
好的,我理解了你的问题。以下是使用邻接表进行广度优先遍历的 C++ 代码,同时计算连通分量个数及边的数目:
```c++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// 邻接表结点
struct AdjListNode {
int dest;
struct AdjListNode* next;
};
// 邻接表头结点
struct AdjList {
struct AdjListNode* head;
};
// 图结构体
struct Graph {
int V; // 顶点个数
struct AdjList* array;
};
// 创建邻接表结点
struct AdjListNode* newAdjListNode(int dest) {
struct AdjListNode* newNode = new AdjListNode;
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
// 创建图
struct Graph* createGraph(int V) {
struct Graph* graph = new Graph;
graph->V = V;
graph->array = new AdjList[V];
for (int i = 0; i < V; ++i) {
graph->array[i].head = NULL;
}
return graph;
}
// 添加边
void addEdge(struct Graph* graph, int src, int dest) {
struct AdjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
newNode = newAdjListNode(src);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}
// 广度优先遍历
void BFS(struct Graph* graph, int s, int& count, int& edges) {
bool* visited = new bool[graph->V];
for (int i = 0; i < graph->V; ++i) {
visited[i] = false;
}
queue<int> q;
visited[s] = true;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
struct AdjListNode* node = graph->array[u].head;
while (node != NULL) {
int v = node->dest;
edges++;
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
node = node->next;
}
}
count++;
for (int i = 0; i < graph->V; ++i) {
if (!visited[i]) {
BFS(graph, i, count, edges);
break;
}
}
}
int main() {
int n, m;
cin >> n >> m;
struct Graph* graph = createGraph(n);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
addEdge(graph, u, v);
}
int count = 0, edges = 0;
BFS(graph, 0, count, edges);
cout << "连通分量个数:" << count << endl;
cout << "边的数目:" << edges / 2 << endl;
return 0;
}
```
其中,`createGraph` 函数用于创建包含 `V` 个顶点的图,`addEdge` 函数用于添加一条 `src` 到 `dest` 的边,`BFS` 函数用于进行广度优先遍历并计算连通分量个数和边的数目。
在 `main` 函数中,我们先输入图的顶点个数 `n` 和边的数目 `m`,然后输入每条边的起点和终点,将它们添加到邻接表中。最后调用 `BFS` 函数进行广度优先遍历,并输出连通分量个数和边的数目。
需要注意的是,在计算边的数目时,由于我们使用了无向图,因此每条边会被计算两次,因此最后要除以 2。