首页设计算法，将一个无向图的邻接矩阵转换为邻接表用简单的C++代码实现

设计算法，将一个无向图的邻接矩阵转换为邻接表用简单的C++代码实现

时间: 2024-12-15 15:19:50 浏览: 40

在C++中，我们可以创建一个邻接表数据结构来存储无向图。这里是一个基本的邻接表实现，包括邻接表的创建以及从邻接矩阵转换： ```cpp #include <vector> // 邻接表节点 struct AdjListNode { int vertex; // 邻接顶点 AdjListNode* next; // 指向下一个邻接顶点的指针 }; class Graph { private: std::vector<AdjListNode*> adjList; // 用vector存储邻接表 public: void addEdge(int src, int dest) { // 在源顶点对应的列表中添加目的地 for (AdjListNode* node = adjList[src]; node; node = node->next) { if (node->vertex == dest) return; // 如果已经存在这条边，直接返回 } AdjListNode* newNode = new AdjListNode{dest, nullptr}; newNode->next = adjList[src]; adjList[src] = newNode; // 反向添加，因为无向图是双向连接的 addEdge(dest, src); } // 示例：假设adjMat是一个二维数组，表示邻接矩阵 void convertToAdjList(int** adjMat, int vertices) { for (int i = 0; i < vertices; ++i) { for (int j = 0; j < vertices; ++j) { if (adjMat[i][j] != 0) { addEdge(i, j); } } } } }; int main() { int vertices = 5; int** adjMat = new int*[vertices]; // 创建邻接矩阵 // 初始化adjMat... Graph g; g.convertToAdjList(adjMat, vertices); delete[] adjMat; // 别忘了释放内存 return 0; } ``` 这段代码首先定义了一个邻接表节点结构，然后在一个`Graph`类中实现了添加边和转换邻接矩阵的功能。`convertToAdjList`函数遍历邻接矩阵，将非零值对应的顶点加入到邻接表中。

阅读全文