采用邻接矩阵表示法创建无向网的算法

在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); // 操作邻接表... } ```

### 邻接矩阵表示法创建无向网的算法实现 邻接矩阵是一种常用的图存储结构，适用于稠密图。对于无向网而言，其边具有权重属性，因此可以通过二维数组来记录节点之间的连接关系及其对应的权值。 #### 算法描述 在一个大小为 \(n \times n\) 的邻接矩阵中，如果顶点 \(i\) 和顶点 \(j\) 存在一条带权值 \(w\) 的边，则令矩阵中的位置 \((i, j)\) 和 \((j, i)\) 均等于 \(w\)[^1]；如果没有边相连，则通常设置该位置的值为无穷大（∞），或者特定的最大数值以表示不可达状态[^2]。 以下是基于 Python 编写的采用邻接矩阵表示法创建无向网的具体代码示例： ```python import sys class UndirectedWeightedGraph: def __init__(self, vertices_count): self.vertices = vertices_count # 初始化邻接矩阵，默认值设为最大整数模拟“无限距离” self.graph = [[sys.maxsize for _ in range(vertices_count)] for _ in range(vertices_count)] # 设置对角线元素为自己到自己的路径长度为0 for i in range(self.vertices): self.graph[i][i] = 0 def add_edge(self, u, v, weight): """ 添加加权边 """ if 0 <= u < self.vertices and 0 <= v < self.vertices: self.graph[u][v] = weight self.graph[v][u] = weight # 因为是无向图所以要双向赋值 else: raise IndexError("Vertex index out of bounds") def display_graph(self): """ 显示当前图形的邻接矩阵 """ for row in self.graph: print(row) # 测试代码 if __name__ == "__main__": graph = UndirectedWeightedGraph(4) graph.add_edge(0, 1, 5) graph.add_edge(1, 2, 3) graph.add_edge(2, 3, 6) graph.display_graph() ``` 此段程序定义了一个类 `UndirectedWeightedGraph` 来管理无向加权图的数据以及操作方法。其中初始化函数设置了默认情况下任意两点间不存在直接连通的情况下的极大成本作为初始条件，并通过成员函数 `add_edge()` 完成具体边的加入工作[^3]。 #### 关于效率考量 需要注意的是，在实际应用过程中，当处理稀疏图时，使用邻接表可能更为节省空间资源。然而，对于某些特殊场景比如动态规划求解最短路等问题来说，由于涉及频繁访问整个行或列数据的操作，此时利用邻接矩阵反而能够带来性能上的优势[^4]。