无向图的邻接表的代码实现(不使用STL)
时间: 2024-01-08 19:03:44 浏览: 25
如果不使用 STL,可以使用指针数组和动态数组来实现无向图的邻接表。以下是一个不使用 STL 的 C++ 代码示例:
```cpp
#include <iostream>
using namespace std;
// 邻接表中链表的节点结构体
struct ListNode {
int val;
ListNode* next;
ListNode(int v) : val(v), next(nullptr) {}
};
// 无向图邻接表的实现
class Graph {
public:
Graph(int V) {
this->V = V;
adjList = new ListNode*[V];
for (int i = 0; i < V; ++i) {
adjList[i] = nullptr;
}
}
// 添加边
void addEdge(int u, int v) {
// 在 u 的邻接表中添加 v
ListNode* node1 = new ListNode(v);
node1->next = adjList[u];
adjList[u] = node1;
// 在 v 的邻接表中添加 u
ListNode* node2 = new ListNode(u);
node2->next = adjList[v];
adjList[v] = node2;
}
// 打印邻接表
void printAdjList() {
for (int i = 0; i < V; ++i) {
cout << i << ": ";
ListNode* node = adjList[i];
while (node != nullptr) {
cout << node->val << " ";
node = node->next;
}
cout << endl;
}
}
private:
int V; // 顶点数
ListNode** adjList; // 邻接表
};
int main() {
Graph g(6);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.addEdge(2, 5);
g.addEdge(3, 4);
g.addEdge(4, 5);
g.printAdjList();
return 0;
}
```
输出结果与使用 STL 的实现相同:
```
0:
1: 3 2
2: 1 5 4
3: 1 4
4: 3 5 2
5: 4 2
```
其中,每行的第一个数字表示顶点的编号,后面的数字表示与该顶点相邻的顶点编号。