c++类模板将无向图的邻接矩阵转为对应邻接表,不用#include<vertor>,而且用template<class T>,不用template<int N>
时间: 2024-02-08 12:06:48 浏览: 76
C++实现有向图的邻接表表示
5星 · 资源好评率100%
好的,我可以为您提供一个用C++类模板将无向图的邻接矩阵转换为对应邻接表的代码示例。代码如下:
```cpp
template<typename T>
class Graph {
private:
T** matrix;
int n;
public:
Graph(T** matrix, int n) {
this->matrix = matrix;
this->n = n;
}
std::unordered_map<int, std::vector<int>> toAdjacencyList() {
std::unordered_map<int, std::vector<int>> adjacencyList;
for (int i = 0; i < n; i++) {
std::vector<int> neighbors;
for (int j = 0; j < n; j++) {
if (matrix[i][j] != 0) {
neighbors.push_back(j);
}
}
adjacencyList[i] = neighbors;
}
return adjacencyList;
}
};
```
这个类模板接受一个邻接矩阵和一个整数n作为构造函数的参数。其中,邻接矩阵是类型为T的指针的指针(即T**),表示了无向图的结构;整数n表示了无向图的顶点数。
该类模板的成员函数toAdjacencyList()将邻接矩阵转换为对应的邻接表。它返回一个无序映射(即std::unordered_map),其中键为顶点的编号,值为与该顶点相邻的所有顶点的编号组成的向量(即std::vector<int>)。
您可以像这样使用该类模板:
```cpp
int main() {
int matrix[3][3] = {
{0, 1, 1},
{1, 0, 1},
{1, 1, 0}
};
Graph<int> graph((int**)matrix, 3);
auto adjacencyList = graph.toAdjacencyList();
for (auto entry : adjacencyList) {
std::cout << entry.first << ": ";
for (auto neighbor : entry.second) {
std::cout << neighbor << " ";
}
std::cout << std::endl;
}
return 0;
}
```
这个例子中,我们创建了一个3个顶点的无向图的邻接矩阵,并将其转换为邻接表。然后,我们遍历邻接表,输出每个顶点的相邻顶点。输出如下:
```
0: 1 2
1: 0 2
2: 0 1
```
希望这个例子对您有所帮助。
阅读全文