c++类模板设有向图G采用邻接矩阵存储,计算图中出度为零 的顶点个数,写一段完整代码
时间: 2024-03-14 08:43:35 浏览: 111
好的,以下是完整的 C++ 代码:
```cpp
#include <iostream>
#include <vector>
template <typename T>
class DirectedGraph {
private:
std::vector<std::vector<T>> adjacencyMatrix;
int vertexCount;
public:
DirectedGraph(int vertexCount) : vertexCount(vertexCount) {
adjacencyMatrix.resize(vertexCount);
for (int i = 0; i < vertexCount; i++) {
adjacencyMatrix[i].resize(vertexCount);
}
}
void addEdge(int from, int to, T weight = 1) {
adjacencyMatrix[from][to] = weight;
}
int countVerticesWithZeroOutDegree() {
int count = 0;
for (int i = 0; i < vertexCount; i++) {
bool hasOutgoingEdge = false;
for (int j = 0; j < vertexCount; j++) {
if (adjacencyMatrix[i][j] != 0) {
hasOutgoingEdge = true;
break;
}
}
if (!hasOutgoingEdge) {
count++;
}
}
return count;
}
};
int main() {
DirectedGraph<int> G(5);
G.addEdge(0, 1);
G.addEdge(0, 2);
G.addEdge(1, 3);
G.addEdge(2, 4);
G.addEdge(3, 4);
std::cout << "Number of vertices with zero out-degree: " << G.countVerticesWithZeroOutDegree() << std::endl;
return 0;
}
```
在这个类模板中,我们使用邻接矩阵来存储有向图。在 `countVerticesWithZeroOutDegree` 方法中,我们遍历每个顶点,检查它是否有出边。如果它没有出边,则增加一个计数器。最后,我们返回计数器的值,即出度为零的顶点个数。
在 `main` 函数中,我们创建一个有向图 `G`,并添加一些边。然后,我们调用 `countVerticesWithZeroOutDegree` 方法来计算出度为零的顶点个数,并输出结果。
阅读全文