写函数,分别用下面两种方法创建无向网: (1)用邻接矩阵表示法创建无向网(参考教材算法6.1) (2)用邻接表表示法创建无向网(参考教材算法6.2) 在主函数中调用上面的函数创建无向网。C++(数据结构)
时间: 2025-01-04 22:38:21 浏览: 11
在C++中,我们可以分别用邻接矩阵和邻接表的方式来表示无向图。以下是创建这两种表示方法的简单示例。
**1. 邻接矩阵表示法(Adjacency Matrix)**
```cpp
#include <iostream>
#include <vector>
// 定义无向图节点
class Node {
public:
int id;
Node(int i) : id(i) {}
};
// 邻接矩阵
std::vector<std::vector<int>> adjacencyMatrix; // 矩阵大小为n x n,其中n为顶点数
void createAdjMatrixGraph(Node nodes[], int numNodes) {
adjacencyMatrix.resize(numNodes);
for (int i = 0; i < numNodes; ++i) {
adjacencyMatrix[i].resize(numNodes); // 初始化全零
}
// 添加边
for (int u = 0; u < numNodes; ++u) {
for (int v = 0; v < numNodes; ++v) {
if (edgesExist(nodes[u], nodes[v])) { // 假设edgesExist是一个判断边存在的函数
adjacencyMatrix[u][v] = 1;
adjacencyMatrix[v][u] = 1; // 图是无向的,所以双向添加边
}
}
}
}
// 主函数
int main() {
Node nodes[] = {Node(0), Node(1), Node(2)}; // 假设有三个节点
int numNodes = sizeof(nodes) / sizeof(nodes[0]);
createAdjMatrixGraph(nodes, numNodes);
// 打印或操作邻接矩阵...
}
```
**2. 邻接表表示法(Adjacency List)**
```cpp
#include <iostream>
#include <list>
// 邻接表结点
struct Edge {
Node* node;
int weight; // 如果需要考虑权重,可以添加
Edge(Node* n, int w = 1) : node(n), weight(w) {}
};
class Node {
public:
int id;
std::list<Edge> adjacencies;
Node(int i) : id(i) {}
};
void createAdjListGraph(Node nodes[], int numNodes) {
for (int i = 0; i < numNodes; ++i) {
nodes[i].adjacencies.clear();
}
// 添加边
for (int u = 0; u < numNodes; ++u) {
for (int v = 0; v < numNodes; ++v) {
if (edgesExist(nodes[u], nodes[v])) {
nodes[u].adjacencies.push_back(Edge(&nodes[v]));
// 由于图是无向的,也需要在v的邻接列表中添加指向u的边
nodes[v].adjacencies.push_back(Edge(&nodes[u]));
}
}
}
}
int main() {
Node nodes[] = {Node(0), Node(1), Node(2)};
int numNodes = sizeof(nodes) / sizeof(nodes[0]);
createAdjListGraph(nodes, numNodes);
// 操作邻接表...
}
```
阅读全文