用C＋＋写出邻接矩阵转邻接表

### C++ 实现邻接矩阵转换为邻接表的代码示例 以下是基于用户需求编写的 C++ 代码，展示如何将邻接矩阵转换为邻接表： ```cpp #include <iostream> #include <vector> using namespace std; struct Node { int dest; struct Node* next; }; // 函数声明 Node* newNode(int dest); void convertMatrixToAdjList(vector<vector<int>> matrix, vector<Node*>& adjList); // 创建新节点 Node* newNode(int dest) { Node* node = new Node(); node->dest = dest; node->next = nullptr; return node; } // 将邻接矩阵转换为邻接表 void convertMatrixToAdjList(vector<vector<int>> matrix, vector<Node*>& adjList) { int n = matrix.size(); // 获取顶点数 // 初始化邻接表为空 for (int i = 0; i < n; ++i) { adjList.push_back(nullptr); // 每个顶点对应的链表初始为空 [^1] } // 遍历邻接矩阵 for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (matrix[i][j] != 0) { // 如果存在边 (i,j) Node* newNodePtr = newNode(j); // 创建新的节点指向目标顶点 j newNodePtr->next = adjList[i]; // 新节点插入到链表头部 adjList[i] = newNodePtr; // 更新链表头指针 [^3] } } } } // 打印邻接表 void printAdjList(const vector<Node*>& adjList) { for (size_t i = 0; i < adjList.size(); ++i) { cout << "Vertex " << i << ": "; Node* temp = adjList[i]; while (temp) { cout << "-> " << temp->dest; temp = temp->next; } cout << endl; } } // 主函数测试 int main() { // 定义一个邻接矩阵 vector<vector<int>> matrix = { {0, 1, 0, 0}, {1, 0, 1, 1}, {0, 1, 0, 0}, {0, 1, 0, 0} }; // 转换后的邻接表 vector<Node*> adjList; // 调用转换函数 convertMatrixToAdjList(matrix, adjList); // 打印邻接表 printAdjList(adjList); // 清理内存 for (auto& head : adjList) { Node* current = head; while (current != nullptr) { Node* nextNode = current->next; delete current; current = nextNode; } } return 0; } ``` --- #### 代码解释 1. **数据结构定义** - 使用 `struct Node` 来表示邻接表中的节点。每个节点包含两个成员变量：`dest` 表示目标顶点编号，`next` 是指向下一个节点的指针[^1]。 2. **初始化邻接表** - 在 `convertMatrixToAdjList` 函数中，通过遍历邻接矩阵来构建邻接表。对于每一个非零元素 `matrix[i][j]`，创建一个新的节点并将它插入到对应顶点 `i` 的链表头部[^3]。 3. **打印功能** - 提供了 `printAdjList` 函数用于调试和验证结果。此函数会逐个打印每个顶点及其连接的所有邻居[^4]。 4. **动态内存管理** - 确保程序结束前释放所有分配给节点对象的堆空间，防止内存泄漏。 --- ### 注意事项 - 此实现适用于无向图或有向图。如果是无向图，在更新邻接表时需同时处理 `(i,j)` 和 `(j,i)` 边的关系。 - 可以进一步扩展支持带权重的图，只需在 `struct Node` 中增加一个 `weight` 字段即可[^4]。 ---