1. 背景说明图的结构比较复杂任何两个顶点之间都可能有关系需要对图进行存储。图的常用存储方法有4种邻接矩阵边集数组邻接表/vector链式前向星本文只介绍邻接矩阵。2. 邻接矩阵介绍邻接矩阵是图的最简单的存储方式。表示图的节点之间关系的矩阵。邻接矩阵存储方法分2步1一个一维数组存储图中顶点的信息2一个二维数组N * N存储图中顶点之间的邻接关系。存储图中节点之间邻接关系的二维数组称为邻接矩阵。3. 无向图1. 核心定义与规则邻接矩阵是一个二维数组通常记为M或adjMatrix用于表示图中顶点之间的连接关系。规则对于无向图若顶点vᵢ与vⱼ之间存在一条边则在矩阵中M[i][j]和M[j][i]两个位置的值均为1若没有边则为0。自我连接通常规定对角线上的元素即M[i][i]为0表示顶点不连接到自身除非是带自环的图。示例矩阵对应图中a,b,c,d四个顶点的邻接关系右侧的矩阵精确编码了这些关系M[0][1] M[1][0] 1表示 a-b 有边。M[1][3] M[3][1] 1表示 b-d 有边。矩阵中所有1的位置都对应图中的一条边。3. 关键性质阐释对称性由于是无向图“a连接b”即意味着“b也连接a”。这导致矩阵关于主对角线完全对称。这是判断邻接矩阵是否表示无向图的直观特征。顶点的度在无向图中一个顶点的“度”指与其相连的边的数量。在邻接矩阵中顶点vᵢ的度等于其对应行或列因对称中所有1的个数之和。例如顶点b第2行/列M[1] [1, 0, 1, 1]和为3故顶点b的度为3。出度表示从某节点发出边个条数称为出度。对于无向图而言出度就是当前节点这一行设置标志为1发出边的个数入度表示从抵达某节点边的条数称为入度。对于无向图而言入度就是当前节点这一列设置标志为1抵达边的个数4. 优缺点与应用场景优点直观易懂结构简单便于理解。访问快速可在常数时间O(1)内判断任意两个顶点间是否有边。缺点空间开销大需要V²的存储空间V为顶点数对于边数远小于V²的稀疏图非常浪费。添加/删除顶点成本高需要改变矩阵大小。适用场景适合表示稠密图或对任意两点间关系查询有极高频率要求的场景。构建这个无向图并打印出邻接矩阵代码实例1: /adj_matrix_00_undirected_graph_00.cc// 邻接矩无向图阵构建与打印 #include iostream #include vector #include sstream using namespace std; vectorvectorint AdjMatrixBUild(int n, const vectorpairchar, char edges) { // 初始化邻接矩阵所有初始化设置为0表示所有节点之间没有邻接 vectorvectorint matrix(n, vectorint(n, 0)); for (const auto edge : edges) { int u edge.first - a; // 将对应字符转换成索引 int v edge.second - a; // 将对应字符转换成索引 matrix[u][v] 1; matrix[v][u] 1; // 无向图是对称的所以[u][v] [v][u] 1 } return matrix; } // 打印邻接矩阵 void AdjMatrixPrint(const string nodes, const vectorvectorint matrix) { cout 邻接矩阵 : endl; cout ; for (const char ch : nodes) { cout ch ; } cout endl; for (int i 0; i nodes.size(); i) { cout nodes[i] | ; for (int j 0; j nodes.size(); j) { cout matrix[i][j] ; } cout endl; } cout endl; } int main() { int n 4; // 在c中char[]类型和std::string 是可以相互转换的 // 所以char nodes[] 可以作为std::string类型参数传递给接受string类型参数的函数 // 这是因为c提供了从c风格字串(即char[])到std::string的隐式转换 char nodes[4] {a, b, c, d}; // 构建无向图的边a-b,b-c,c-d,d-a这样一个循环的节点拓扑图 vectorpairchar, char edges { {a, b}, {b, c}, {c, d}, {d, a} }; // 构建邻接矩阵 auto matrix AdjMatrixBUild(n, edges); // 打印邻接矩阵 AdjMatrixPrint(nodes, matrix); return 0; }测试执行结果代码实例2: /adj_matrix_00_undirected_graph_01.cc// 邻接矩无向图阵构建与打印 #include iostream #include vector #include sstream #include string #include map #include unordered_map using namespace std; vectorvectorint AdjMatrixBUild(int n, const string nodes, const vectorpairchar, char edges) { // 建立字符到索引的映射表 unordered_mapchar, int nodeIndexMap; for (int i 0; i n; i) { nodeIndexMap[nodes[i]] i; } // 初始化邻接矩阵所有初始化设置为0表示所有节点之间没有邻接 vectorvectorint matrix(n, vectorint(n, 0)); for (const auto edge : edges) { int cu nodeIndexMap[edge.first]; int cv nodeIndexMap[edge.second]; matrix[cu][cv] 1; matrix[cv][cu] 1; // 无向图是对称的所以[u][v] [v][u] 1 } return matrix; } // 打印邻接矩阵 void AdjMatrixPrint(const string nodes, const vectorvectorint matrix) { cout endl 对应无向图的邻接矩阵 : endl; cout ; for (const char ch : nodes) { cout ch ; } cout endl; for (int i 0; i nodes.size(); i) { cout nodes[i] | ; for (int j 0; j nodes.size(); j) { cout matrix[i][j] ; } cout endl; } cout endl; } // 图的拓扑结构打印将每个节点的邻接点添加到当前节点后再一一打印出来 void GraphTopologyPrint(int n, string nodes, vectorvectorint matrix) { // 打印图的拓扑结构 cout endl 当前图的拓扑结构 : endl; mapchar, vectorchar topoMap; // 构建每个节点的邻居列表 for (int i 0; i n; i) { char node nodes[i]; vectorchar neighbors; for (int j 0; j n; j) { if (matrix[i][j] 1) { neighbors.push_back(nodes[j]); } } topoMap[node] neighbors; } // 打印每个节点及其邻接点 for (const auto entry : topoMap) { cout entry.first - ; for (const auto neighbor : entry.second) { cout neighbor ; } cout endl; } } void NodeDetailsPrint(int n, string nodes, const vectorvectorint matrix) { // 打印每个节点的出发边抵达边初度和入度 cout 节点的详细信息 : endl; for (int i 0; i n; i) { char node nodes[i]; vectorchar outEdges; vectorchar inEdges; // 查找发出边和抵达边,对于无向图而语言发出边和抵达边是对称的也就是说出度和入度是一样的 for (int j 0; j n; j) { // 对于无向图而言出度就是当前节点这一行设置标志为1发出边的个数 if (matrix[i][j] 1) { outEdges.push_back(nodes[j]); } // 对于无向图而言入度就是当前节点这一列设置标志为1抵达边的个数 if (matrix[j][i] 1) { inEdges.push_back(nodes[j]); } } // 计算出度和入度 int outDegree outEdges.size(); int inDegree inEdges.size(); // 打印节点的详细信息 cout 节点 node : endl; cout 出度 : outDegree; cout , 发出边 outEdges.size() ) : ; for (const auto edge : outEdges) { cout edge ; } cout endl ; cout 入度 : inDegree; cout , 抵达边 inEdges.size() ) : ; for (const auto edge : inEdges) { cout edge ; } cout endl; } } int main() { int n 0; cout 输入拓扑图中节点个数 : ; while (cin n) { cout 输入各个节点的的名称(a~z) : ; string nodes(n, \0); for (int i 0; i n; i) { cin nodes[i]; } vectorpairchar, char edges; // 输入各个节点的邻接点 for (int i 0; i n; i) { cout 输入节点 nodes[i] 的邻接点(多个用空格分隔按回车结束) : ; string inputStr; // getline(cin, inputStr); // 读取从当前位置到换行符的内容前导空格和Tab会被读入字符串。直接读取包括空白在内的整行。 // cin ws会先移除输入缓冲区开头的空白字符跳过空白读取整行输入 // ws会先丢弃当前位置之前的空格、Tab、换行符再执行 getline读取内容。这能避免之前输入留下的换行符干扰。 getline(cin ws, inputStr); istringstream iss(inputStr); char neighbor; while (iss neighbor) { if (neighbor a neighbor z) { edges.push_back({nodes[i], neighbor}); } } } // 构建邻接矩阵 auto matrix AdjMatrixBUild(n, nodes, edges); // 打印图的拓扑结构 GraphTopologyPrint(n, nodes, matrix); // 打印邻接矩阵 AdjMatrixPrint(nodes, matrix); // 打印各个节点的详细信息 NodeDetailsPrint(n, nodes, matrix); cout endl 继续输入其他拓扑图中节点个数 : endl; cout 输入节点个数 : ; } return 0; }测试执行结果4. 有向图在有向图中如果 vi到 vj有边则邻接矩阵 M[i][j]1否则 M[i][j]0。顶点数组vex[]{a,b,c,d,e}存储顶点名称的一维数组度信息入度In-degree指向该顶点的边的数量。出度Out-degree从该顶点指出的边的数量。1. 邻接矩阵的定义与规则对于有 n个顶点的有向图其邻接矩阵是一个 n×n的方阵 M。矩阵元素 M[i][j]表示从顶点 vi到顶点 vj的边是否存在M[i][j]1存在一条从 vi指向 vj的有向边。M[i][j]0没有从 vi到 vj的边。注意有向图的邻接矩阵不一定对称因为边的方向性意味着 M[i][j]和 M[j][i]可能不同。顶点数组 vex[]按顺序存储顶点名称如 a, b, c, d, e矩阵的行列索引即对应此顺序。矩阵解读以示例矩阵为例第一行顶点 a[0,1,1,0,1]表示从 a 出发有到 bce共3条边。第二行顶点 b[0,0,1,0,0]表示从 b 出发只有到 c 一条边。依此类推每一行代表该顶点向外的边出边。3. 顶点的入度与出度出度Out-degree顶点 vi的出度等于其对应行中所有 1 的个数之和即从该顶点出发的边数。示例中顶点 b 的出度为 1第2行只有1个1。入度In-degree顶点 vj的入度等于其对应列中所有 1 的个数之和即指向该顶点的边数。示例中顶点 c 的入度为 2第3列有两个1来自 a 和 b。4. 有向图邻接矩阵的特性非对称性由于方向性矩阵通常不对称除非每对顶点间都有双向边。对角线元素通常为 0表示没有自环除非特别定义。空间复杂度O(n2)与无向图相同但存储的信息不同只存单向关系。5. 应用场景适合表示稠密有向图或需要频繁查询特定方向关系的场景如社交网络中的关注关系、网页链接图等。便于计算路径通过矩阵乘法可达性分析、度中心性等指标。代码实例1: /adj_matrix_01_directed_graph_00.cc// 邻接矩有向图阵构建与打印 #include iostream #include vector #include sstream #include string #include map #include unordered_map using namespace std; vectorvectorint AdjMatrixBUild(int n, const string nodes, const vectorpairchar, char edges) { // 建立字符到索引的映射表 unordered_mapchar, int nodeIndexMap; for (int i 0; i n; i) { nodeIndexMap[nodes[i]] i; } // 初始化邻接矩阵所有初始化设置为0表示所有节点之间没有邻接 vectorvectorint matrix(n, vectorint(n, 0)); for (const auto edge : edges) { int cu nodeIndexMap[edge.first]; int cv nodeIndexMap[edge.second]; matrix[cu][cv] 1; // 有向图只需设置单向边 // 注意有向图不需要设置 matrix[cv][cu] 1 } return matrix; } // 打印邻接矩阵 void AdjMatrixPrint(const string nodes, const vectorvectorint matrix) { cout endl 对应有向图的邻接矩阵 : endl; cout ; for (const char ch : nodes) { cout ch ; } cout endl; for (int i 0; i nodes.size(); i) { cout nodes[i] | ; for (int j 0; j nodes.size(); j) { cout matrix[i][j] ; } cout endl; } cout endl; } // 图的拓扑结构打印将每个节点的邻接点添加到当前节点后再一一打印出来 void GraphTopologyPrint(int n, string nodes, vectorvectorint matrix) { // 打印图的拓扑结构 cout endl 当前图的拓扑结构 : endl; mapchar, vectorchar topoMap; // 构建每个节点的邻居列表出边方向 for (int i 0; i n; i) { char node nodes[i]; vectorchar neighbors; for (int j 0; j n; j) { if (matrix[i][j] 1) { neighbors.push_back(nodes[j]); } } topoMap[node] neighbors; } // 打印每个节点及其邻接点 for (const auto entry : topoMap) { cout entry.first - ; for (const auto neighbor : entry.second) { cout neighbor ; } cout endl; } } void NodeDetailsPrint(int n, string nodes, const vectorvectorint matrix) { // 打印每个节点的出发边抵达边出度和入度 cout 节点的详细信息 : endl; for (int i 0; i n; i) { char node nodes[i]; vectorchar outEdges; vectorchar inEdges; // 查找发出边和抵达边 for (int j 0; j n; j) { // 出度当前节点这一行设置标志为1发出边的个数 if (matrix[i][j] 1) { outEdges.push_back(nodes[j]); } // 入度当前节点这一列设置标志为1抵达边的个数 if (matrix[j][i] 1) { inEdges.push_back(nodes[j]); } } // 计算出度和入度 int outDegree outEdges.size(); int inDegree inEdges.size(); // 打印节点的详细信息 cout 节点 node : endl; cout 出度 : outDegree; cout , 发出边 outEdges.size() ) : ; for (const auto edge : outEdges) { cout edge ; } cout endl ; cout 入度 : inDegree; cout , 抵达边 inEdges.size() ) : ; for (const auto edge : inEdges) { cout edge ; } cout endl; } } int main() { int n 0; cout 输入拓扑图中节点个数 : ; while (cin n) { cout 输入各个节点的的名称(a~z) : ; string nodes(n, \0); for (int i 0; i n; i) { cin nodes[i]; } vectorpairchar, char edges; // 输入各个节点的邻接点 for (int i 0; i n; i) { cout 输入节点 nodes[i] 的邻接点(多个用空格分隔按回车结束) : ; string inputStr; // 使用 getline(cin ws, inputStr) 跳过空白并读取整行 getline(cin ws, inputStr); istringstream iss(inputStr); char neighbor; while (iss neighbor) { if (neighbor a neighbor z) { edges.push_back({nodes[i], neighbor}); } } } // 构建邻接矩阵 auto matrix AdjMatrixBUild(n, nodes, edges); // 打印图的拓扑结构 GraphTopologyPrint(n, nodes, matrix); // 打印邻接矩阵 AdjMatrixPrint(nodes, matrix); // 打印各个节点的详细信息 NodeDetailsPrint(n, nodes, matrix); cout endl 继续输入其他拓扑图中节点个数 : endl; cout 输入节点个数 : ; } return 0; }测试运行结果5. 带权图带权图也叫做网“在带权图中如果vi到vj有边则邻接矩阵M[i][j]w{ij}否则可以设置M[i][j]∞。”当然如果正常边权不会出现负数的情况下也可以设置为-1或其他负数。节点数组vex[] {a, b, c, d, e}图中的代码注释“const int inf 0x3f3f3f3f;”通常表示无穷大的值邻接矩阵的示例其中包含具体的权重值以及无穷大符号∞。1. 带权图邻接矩阵的定义与规则对于具有 n个顶点的带权有向图其邻接矩阵是一个 n×n的方阵 M。矩阵元素 M[i][j]表示从顶点 vi到顶点 vj的边的权重若存在从 vi到 vj的有向边则 M[i][j]wij其中 wij是该边的权值。若不存在这样的边则 M[i][j]∞用一个足够大的常数表示如0x3f3f3f3f。特殊情况通常规定 M[i][i]0表示顶点到自身的距离为0 M[i][i]∞表示没有这条边自己不可以与自己有权重除非特别定义自环权重。对于无向带权图矩阵是对称的即 M[i][j]M[j][i]。2. 示例图与矩阵的对应关系图片左侧应展示了一个带权有向图包含5个顶点 a,b,c,d,e边上的数字表示权重。顶点数组 vex[]按顺序存储顶点名称矩阵的行列索引与此顺序对应。4. 带权图邻接矩阵的特性非对称性有向图的邻接矩阵通常不对称因为边的方向性可能导致权重不同或反向无边。对角线元素通常为0表示顶点到自身的距离为0。空间复杂度O(n2)适合稠密图。权重的含义可以表示距离、费用、时间、容量等具体取决于应用场景。5. 应用场景与算法基础最短路径算法如 Floyd-Warshall 算法直接基于邻接矩阵进行动态规划。网络流问题权重可表示边的容量。旅行商问题TSP权重表示城市间的距离。可达性分析通过矩阵乘法可计算经过若干步的路径总权重。代码实例1: /adj_matrix_02_weighted_graph_00.cc构建有全图打印节点拓扑和节点之间的信息// 构建有全图打印节点拓扑和节点之间的信息 #include iostream #include vector #include sstream #include string #include map #include unordered_map #include climits #include iomanip using namespace std; // 定义边的结构体包含起点、终点和权重 struct Edge { char from; char to; int weight; }; // 构建带权图的邻接矩阵 vectorvectorint AdjMatrixBUild(int n, const string nodes, const vectorEdge edges) { // 建立字符到索引的映射表 unordered_mapchar, int nodeIndexMap; for (int i 0; i n; i) { nodeIndexMap[nodes[i]] i; } // 初始化邻接矩阵所有初始化设置为INT_MAX表示没有连接无穷大 vectorvectorint matrix(n, vectorint(n, INT_MAX)); // 设置对角线为0表示节点到自身的距离为0 for (int i 0; i n; i) { matrix[i][i] 0; } // 根据边的信息填充邻接矩阵 for (const auto edge : edges) { int cu nodeIndexMap[edge.from]; int cv nodeIndexMap[edge.to]; matrix[cu][cv] edge.weight; // 注意带权有向图只需要设置单向边不需要对称设置 } return matrix; } // 打印带权邻接矩阵 void AdjMatrixPrint(const string nodes, const vectorvectorint matrix) { cout endl 对应带权有向图的邻接矩阵 : endl; cout ; for (const char ch : nodes) { cout ch ; } cout endl; for (int i 0; i nodes.size(); i) { cout nodes[i] | ; for (int j 0; j nodes.size(); j) { if (matrix[i][j] INT_MAX) { cout ∞ ; } else { cout matrix[i][j] ; } } cout endl; } cout endl; } // 图的拓扑结构打印将每个节点的邻接点及权重添加到当前节点后再一一打印出来 void GraphTopologyPrint(int n, string nodes, const vectorvectorint matrix) { // 打印图的拓扑结构 cout endl 当前带权有向图的拓扑结构 : endl; mapchar, vectorpairchar, int topoMap; // 构建每个节点的邻居列表出边方向包含权重 for (int i 0; i n; i) { char node nodes[i]; vectorpairchar, int neighbors; for (int j 0; j n; j) { if (matrix[i][j] ! INT_MAX i ! j) { // 排除自身 neighbors.push_back({nodes[j], matrix[i][j]}); } } topoMap[node] neighbors; } // 打印每个节点及其邻接点和权重 for (const auto entry : topoMap) { cout entry.first - ; if (entry.second.empty()) { cout 无出边; } else { for (const auto neighbor : entry.second) { cout neighbor.first ( neighbor.second ) ; } } cout endl; } cout endl; } // 打印节点的详细信息包括出度、入度、权重信息 void NodeDetailsPrint(int n, string nodes, const vectorvectorint matrix) { cout 节点的详细信息 : endl; // 统计每个节点的出边和入边并计算总权重 vectorpairint, int totalWeights(n, {0, 0}); // 第一个是总出边权重第二个是总入边权重 for (int i 0; i n; i) { char node nodes[i]; vectorpairchar, int outEdges; // 出边目标节点和权重 vectorpairchar, int inEdges; // 入边源节点和权重 // 查找发出边和抵达边 for (int j 0; j n; j) { // 出度当前节点这一行设置非INT_MAX且不为自身的边 if (matrix[i][j] ! INT_MAX i ! j) { outEdges.push_back({nodes[j], matrix[i][j]}); totalWeights[i].first matrix[i][j]; } // 入度当前节点这一列设置非INT_MAX且不为自身的边 if (matrix[j][i] ! INT_MAX j ! i) { inEdges.push_back({nodes[j], matrix[j][i]}); totalWeights[i].second matrix[j][i]; } } // 计算出度和入度 int outDegree outEdges.size(); int inDegree inEdges.size(); // 打印节点的详细信息 cout 节点 node : endl; // 出度信息 cout 出度 : outDegree; if (outDegree 0) { cout , 发出边( outDegree ) : ; for (const auto edge : outEdges) { cout node → edge.first ( edge.second ) ; } cout , 总出边权重: totalWeights[i].first; } else { cout , 无发出边; } cout endl; // 入度信息 cout 入度 : inDegree; if (inDegree 0) { cout , 抵达边( inDegree ) : ; for (const auto edge : inEdges) { cout edge.first → node ( edge.second ) ; } cout , 总入边权重: totalWeights[i].second; } else { cout , 无抵达边; } cout endl endl; } } // 打印路径权重和最短路径信息带权图的优越性体现 void PathAnalysisPrint(int n, string nodes, const vectorvectorint matrix) { cout 带权图路径分析体现带权图的优越性 endl; // 检查是否存在直接连接 cout 1. 直接连接检查 endl; bool hasDirectConnections false; for (int i 0; i n; i) { for (int j 0; j n; j) { if (i ! j matrix[i][j] ! INT_MAX) { cout nodes[i] → nodes[j] : 权重 matrix[i][j] endl; hasDirectConnections true; } } } if (!hasDirectConnections) { cout 没有直接连接 endl; } cout endl; // 计算所有可能的两步路径 cout 2. 两步路径计算带权图可以计算路径总权重 endl; for (int i 0; i n; i) { for (int j 0; j n; j) { if (i ! j) { // 查找中间节点k使得i→k→j存在 for (int k 0; k n; k) { if (k ! i k ! j matrix[i][k] ! INT_MAX matrix[k][j] ! INT_MAX) { int totalWeight matrix[i][k] matrix[k][j]; cout nodes[i] → nodes[k] → nodes[j] : 总权重 matrix[i][k] matrix[k][j] totalWeight endl; } } } } } cout endl; // 显示带权图的优势可以找到最小权重路径 cout 3. 最小直接连接权重查找 endl; int minWeight INT_MAX; pairint, int minEdge {-1, -1}; for (int i 0; i n; i) { for (int j 0; j n; j) { if (i ! j matrix[i][j] ! INT_MAX matrix[i][j] minWeight) { minWeight matrix[i][j]; minEdge {i, j}; } } } if (minEdge.first ! -1) { cout 最小权重边: nodes[minEdge.first] → nodes[minEdge.second] ( minWeight ) endl; } else { cout 没有找到权重边 endl; } cout endl endl; } int main() { int n 0; cout 输入拓扑图中节点个数 : ; while (cin n) { if (n 0 || n 26) { cout 节点个数应在1-26之间,请重新输入: ; continue; } cout 输入各个节点的名称(a~z) : ; string nodes(n, \0); for (int i 0; i n; i) { cin nodes[i]; } vectorEdge edges; // 输入各个节点的邻接点及权重 for (int i 0; i n; i) { cout 输入节点 nodes[i] 的邻接点及权重(格式:邻接点 权重多个用空格分隔按回车结束) : ; string inputStr; // 使用 getline(cin ws, inputStr) 跳过空白并读取整行 getline(cin ws, inputStr); istringstream iss(inputStr); char neighbor; int weight; while (iss neighbor weight) { if (neighbor a neighbor z) { edges.push_back({nodes[i], neighbor, weight}); } else { cout 警告: 邻接点 neighbor 不是有效的小写字母已跳过 endl; } } } // 构建邻接矩阵 auto matrix AdjMatrixBUild(n, nodes, edges); // 打印图的拓扑结构 GraphTopologyPrint(n, nodes, matrix); // 打印邻接矩阵 AdjMatrixPrint(nodes, matrix); // 打印各个节点的详细信息 NodeDetailsPrint(n, nodes, matrix); // 打印路径分析体现带权图的优越性 PathAnalysisPrint(n, nodes, matrix); cout endl 继续输入其他拓扑图中节点个数 : endl; cout 输入节点个数(输入0退出): ; } cout 程序结束 endl; return 0; }测试运行结果6. 邻接矩阵应用使用邻接矩阵计算最短路径的dijkstra算法代码示例 /path_min_00_dijkstra_00.cc// 使用邻接矩阵计算最短路径的dijkstra算法实现 #include iostream #include algorithm #include stack using namespace std; const int N 1005; const int INF 0x3FFFFFFF; // 无穷大 int G[N][N]; // 邻接矩阵 int dist[N]; // 最短距离 int p[N]; // 前驱节点 int n; // 节点个数 int m; // 节点间边数 bool flag[N]; // false表示v-s集合true表示s集合 void dijkstra(int u) { // 初始化 for (int i 1; i n; i) { dist[i] G[u][i]; flag[i] false; if (dist[i] INF) { p[i] -1; } else { p[i] u; } } dist[u] 0; flag[u] true; // 主循环 for (int i 1; i n; i) { int minDist INF, minNode -1; // 在未访问节点中寻找距离最小的节点 for (int j 1; j n; j) { if (!flag[j] dist[j] minDist) { minDist dist[j]; minNode j; } } // 所有节点已访问或剩余节点不可达 if (minNode -1) return; flag[minNode] true; // 松弛操作更新相邻节点的最短距离 for (int j 1; j n; j) { if (!flag[j] G[minNode][j] ! INF dist[j] dist[minNode] G[minNode][j]) { dist[j] dist[minNode] G[minNode][j]; p[j] minNode; } } } } // 递归打印从源点到目标节点的路径 void printPath(int u) { if (p[u] -1) { cout u; return; } printPath(p[u]); cout - u; } int main() { // 初始化邻接矩阵 fill(G[0], G[0] N*N, INF); cout 输入节点数n和边数m: ; cin n m; cout 输入 m 条边起点 终点 权重: endl; for (int i 0; i m; i) { int u, v, w; cin u v w; G[u][v] w; // 无向图添加反向边如果需要 // G[v][u] w; } int source; cout 输入源点: ; cin source; dijkstra(source); cout \n源点 source 到各节点的最短距离: endl; for (int i 1; i n; i) { cout 源点 source - 节点 i : ; if (dist[i] INF) { cout 不可达; } else { cout 最短距离 : dist[i] \t路径: ; printPath(i); } cout endl; } return 0; }测试数据1输入节点数n和边数m: 5 7输入7条边起点 终点 权重:1 2 41 3 12 3 22 4 53 2 13 4 84 5 3输入源点: 1测试结果测试数据2输入节点数n和边数m: 5 7输入7条边起点 终点 权重:1 2 41 3 12 3 22 4 53 2 13 4 84 5 3输入源点: 27. 总结邻接矩阵优点快速判断两顶点之间是否有边。方便计算各顶点的度。邻接矩阵缺点不便于增删顶点。不便于访问所有邻接点。空间复杂度高。
图论算法基础00：图的存储方式0：邻接矩阵
1. 背景说明图的结构比较复杂任何两个顶点之间都可能有关系需要对图进行存储。图的常用存储方法有4种邻接矩阵边集数组邻接表/vector链式前向星本文只介绍邻接矩阵。2. 邻接矩阵介绍邻接矩阵是图的最简单的存储方式。表示图的节点之间关系的矩阵。邻接矩阵存储方法分2步1一个一维数组存储图中顶点的信息2一个二维数组N * N存储图中顶点之间的邻接关系。存储图中节点之间邻接关系的二维数组称为邻接矩阵。3. 无向图1. 核心定义与规则邻接矩阵是一个二维数组通常记为M或adjMatrix用于表示图中顶点之间的连接关系。规则对于无向图若顶点vᵢ与vⱼ之间存在一条边则在矩阵中M[i][j]和M[j][i]两个位置的值均为1若没有边则为0。自我连接通常规定对角线上的元素即M[i][i]为0表示顶点不连接到自身除非是带自环的图。示例矩阵对应图中a,b,c,d四个顶点的邻接关系右侧的矩阵精确编码了这些关系M[0][1] M[1][0] 1表示 a-b 有边。M[1][3] M[3][1] 1表示 b-d 有边。矩阵中所有1的位置都对应图中的一条边。3. 关键性质阐释对称性由于是无向图“a连接b”即意味着“b也连接a”。这导致矩阵关于主对角线完全对称。这是判断邻接矩阵是否表示无向图的直观特征。顶点的度在无向图中一个顶点的“度”指与其相连的边的数量。在邻接矩阵中顶点vᵢ的度等于其对应行或列因对称中所有1的个数之和。例如顶点b第2行/列M[1] [1, 0, 1, 1]和为3故顶点b的度为3。出度表示从某节点发出边个条数称为出度。对于无向图而言出度就是当前节点这一行设置标志为1发出边的个数入度表示从抵达某节点边的条数称为入度。对于无向图而言入度就是当前节点这一列设置标志为1抵达边的个数4. 优缺点与应用场景优点直观易懂结构简单便于理解。访问快速可在常数时间O(1)内判断任意两个顶点间是否有边。缺点空间开销大需要V²的存储空间V为顶点数对于边数远小于V²的稀疏图非常浪费。添加/删除顶点成本高需要改变矩阵大小。适用场景适合表示稠密图或对任意两点间关系查询有极高频率要求的场景。构建这个无向图并打印出邻接矩阵代码实例1: /adj_matrix_00_undirected_graph_00.cc// 邻接矩无向图阵构建与打印 #include iostream #include vector #include sstream using namespace std; vectorvectorint AdjMatrixBUild(int n, const vectorpairchar, char edges) { // 初始化邻接矩阵所有初始化设置为0表示所有节点之间没有邻接 vectorvectorint matrix(n, vectorint(n, 0)); for (const auto edge : edges) { int u edge.first - a; // 将对应字符转换成索引 int v edge.second - a; // 将对应字符转换成索引 matrix[u][v] 1; matrix[v][u] 1; // 无向图是对称的所以[u][v] [v][u] 1 } return matrix; } // 打印邻接矩阵 void AdjMatrixPrint(const string nodes, const vectorvectorint matrix) { cout 邻接矩阵 : endl; cout ; for (const char ch : nodes) { cout ch ; } cout endl; for (int i 0; i nodes.size(); i) { cout nodes[i] | ; for (int j 0; j nodes.size(); j) { cout matrix[i][j] ; } cout endl; } cout endl; } int main() { int n 4; // 在c中char[]类型和std::string 是可以相互转换的 // 所以char nodes[] 可以作为std::string类型参数传递给接受string类型参数的函数 // 这是因为c提供了从c风格字串(即char[])到std::string的隐式转换 char nodes[4] {a, b, c, d}; // 构建无向图的边a-b,b-c,c-d,d-a这样一个循环的节点拓扑图 vectorpairchar, char edges { {a, b}, {b, c}, {c, d}, {d, a} }; // 构建邻接矩阵 auto matrix AdjMatrixBUild(n, edges); // 打印邻接矩阵 AdjMatrixPrint(nodes, matrix); return 0; }测试执行结果代码实例2: /adj_matrix_00_undirected_graph_01.cc// 邻接矩无向图阵构建与打印 #include iostream #include vector #include sstream #include string #include map #include unordered_map using namespace std; vectorvectorint AdjMatrixBUild(int n, const string nodes, const vectorpairchar, char edges) { // 建立字符到索引的映射表 unordered_mapchar, int nodeIndexMap; for (int i 0; i n; i) { nodeIndexMap[nodes[i]] i; } // 初始化邻接矩阵所有初始化设置为0表示所有节点之间没有邻接 vectorvectorint matrix(n, vectorint(n, 0)); for (const auto edge : edges) { int cu nodeIndexMap[edge.first]; int cv nodeIndexMap[edge.second]; matrix[cu][cv] 1; matrix[cv][cu] 1; // 无向图是对称的所以[u][v] [v][u] 1 } return matrix; } // 打印邻接矩阵 void AdjMatrixPrint(const string nodes, const vectorvectorint matrix) { cout endl 对应无向图的邻接矩阵 : endl; cout ; for (const char ch : nodes) { cout ch ; } cout endl; for (int i 0; i nodes.size(); i) { cout nodes[i] | ; for (int j 0; j nodes.size(); j) { cout matrix[i][j] ; } cout endl; } cout endl; } // 图的拓扑结构打印将每个节点的邻接点添加到当前节点后再一一打印出来 void GraphTopologyPrint(int n, string nodes, vectorvectorint matrix) { // 打印图的拓扑结构 cout endl 当前图的拓扑结构 : endl; mapchar, vectorchar topoMap; // 构建每个节点的邻居列表 for (int i 0; i n; i) { char node nodes[i]; vectorchar neighbors; for (int j 0; j n; j) { if (matrix[i][j] 1) { neighbors.push_back(nodes[j]); } } topoMap[node] neighbors; } // 打印每个节点及其邻接点 for (const auto entry : topoMap) { cout entry.first - ; for (const auto neighbor : entry.second) { cout neighbor ; } cout endl; } } void NodeDetailsPrint(int n, string nodes, const vectorvectorint matrix) { // 打印每个节点的出发边抵达边初度和入度 cout 节点的详细信息 : endl; for (int i 0; i n; i) { char node nodes[i]; vectorchar outEdges; vectorchar inEdges; // 查找发出边和抵达边,对于无向图而语言发出边和抵达边是对称的也就是说出度和入度是一样的 for (int j 0; j n; j) { // 对于无向图而言出度就是当前节点这一行设置标志为1发出边的个数 if (matrix[i][j] 1) { outEdges.push_back(nodes[j]); } // 对于无向图而言入度就是当前节点这一列设置标志为1抵达边的个数 if (matrix[j][i] 1) { inEdges.push_back(nodes[j]); } } // 计算出度和入度 int outDegree outEdges.size(); int inDegree inEdges.size(); // 打印节点的详细信息 cout 节点 node : endl; cout 出度 : outDegree; cout , 发出边 outEdges.size() ) : ; for (const auto edge : outEdges) { cout edge ; } cout endl ; cout 入度 : inDegree; cout , 抵达边 inEdges.size() ) : ; for (const auto edge : inEdges) { cout edge ; } cout endl; } } int main() { int n 0; cout 输入拓扑图中节点个数 : ; while (cin n) { cout 输入各个节点的的名称(a~z) : ; string nodes(n, \0); for (int i 0; i n; i) { cin nodes[i]; } vectorpairchar, char edges; // 输入各个节点的邻接点 for (int i 0; i n; i) { cout 输入节点 nodes[i] 的邻接点(多个用空格分隔按回车结束) : ; string inputStr; // getline(cin, inputStr); // 读取从当前位置到换行符的内容前导空格和Tab会被读入字符串。直接读取包括空白在内的整行。 // cin ws会先移除输入缓冲区开头的空白字符跳过空白读取整行输入 // ws会先丢弃当前位置之前的空格、Tab、换行符再执行 getline读取内容。这能避免之前输入留下的换行符干扰。 getline(cin ws, inputStr); istringstream iss(inputStr); char neighbor; while (iss neighbor) { if (neighbor a neighbor z) { edges.push_back({nodes[i], neighbor}); } } } // 构建邻接矩阵 auto matrix AdjMatrixBUild(n, nodes, edges); // 打印图的拓扑结构 GraphTopologyPrint(n, nodes, matrix); // 打印邻接矩阵 AdjMatrixPrint(nodes, matrix); // 打印各个节点的详细信息 NodeDetailsPrint(n, nodes, matrix); cout endl 继续输入其他拓扑图中节点个数 : endl; cout 输入节点个数 : ; } return 0; }测试执行结果4. 有向图在有向图中如果 vi到 vj有边则邻接矩阵 M[i][j]1否则 M[i][j]0。顶点数组vex[]{a,b,c,d,e}存储顶点名称的一维数组度信息入度In-degree指向该顶点的边的数量。出度Out-degree从该顶点指出的边的数量。1. 邻接矩阵的定义与规则对于有 n个顶点的有向图其邻接矩阵是一个 n×n的方阵 M。矩阵元素 M[i][j]表示从顶点 vi到顶点 vj的边是否存在M[i][j]1存在一条从 vi指向 vj的有向边。M[i][j]0没有从 vi到 vj的边。注意有向图的邻接矩阵不一定对称因为边的方向性意味着 M[i][j]和 M[j][i]可能不同。顶点数组 vex[]按顺序存储顶点名称如 a, b, c, d, e矩阵的行列索引即对应此顺序。矩阵解读以示例矩阵为例第一行顶点 a[0,1,1,0,1]表示从 a 出发有到 bce共3条边。第二行顶点 b[0,0,1,0,0]表示从 b 出发只有到 c 一条边。依此类推每一行代表该顶点向外的边出边。3. 顶点的入度与出度出度Out-degree顶点 vi的出度等于其对应行中所有 1 的个数之和即从该顶点出发的边数。示例中顶点 b 的出度为 1第2行只有1个1。入度In-degree顶点 vj的入度等于其对应列中所有 1 的个数之和即指向该顶点的边数。示例中顶点 c 的入度为 2第3列有两个1来自 a 和 b。4. 有向图邻接矩阵的特性非对称性由于方向性矩阵通常不对称除非每对顶点间都有双向边。对角线元素通常为 0表示没有自环除非特别定义。空间复杂度O(n2)与无向图相同但存储的信息不同只存单向关系。5. 应用场景适合表示稠密有向图或需要频繁查询特定方向关系的场景如社交网络中的关注关系、网页链接图等。便于计算路径通过矩阵乘法可达性分析、度中心性等指标。代码实例1: /adj_matrix_01_directed_graph_00.cc// 邻接矩有向图阵构建与打印 #include iostream #include vector #include sstream #include string #include map #include unordered_map using namespace std; vectorvectorint AdjMatrixBUild(int n, const string nodes, const vectorpairchar, char edges) { // 建立字符到索引的映射表 unordered_mapchar, int nodeIndexMap; for (int i 0; i n; i) { nodeIndexMap[nodes[i]] i; } // 初始化邻接矩阵所有初始化设置为0表示所有节点之间没有邻接 vectorvectorint matrix(n, vectorint(n, 0)); for (const auto edge : edges) { int cu nodeIndexMap[edge.first]; int cv nodeIndexMap[edge.second]; matrix[cu][cv] 1; // 有向图只需设置单向边 // 注意有向图不需要设置 matrix[cv][cu] 1 } return matrix; } // 打印邻接矩阵 void AdjMatrixPrint(const string nodes, const vectorvectorint matrix) { cout endl 对应有向图的邻接矩阵 : endl; cout ; for (const char ch : nodes) { cout ch ; } cout endl; for (int i 0; i nodes.size(); i) { cout nodes[i] | ; for (int j 0; j nodes.size(); j) { cout matrix[i][j] ; } cout endl; } cout endl; } // 图的拓扑结构打印将每个节点的邻接点添加到当前节点后再一一打印出来 void GraphTopologyPrint(int n, string nodes, vectorvectorint matrix) { // 打印图的拓扑结构 cout endl 当前图的拓扑结构 : endl; mapchar, vectorchar topoMap; // 构建每个节点的邻居列表出边方向 for (int i 0; i n; i) { char node nodes[i]; vectorchar neighbors; for (int j 0; j n; j) { if (matrix[i][j] 1) { neighbors.push_back(nodes[j]); } } topoMap[node] neighbors; } // 打印每个节点及其邻接点 for (const auto entry : topoMap) { cout entry.first - ; for (const auto neighbor : entry.second) { cout neighbor ; } cout endl; } } void NodeDetailsPrint(int n, string nodes, const vectorvectorint matrix) { // 打印每个节点的出发边抵达边出度和入度 cout 节点的详细信息 : endl; for (int i 0; i n; i) { char node nodes[i]; vectorchar outEdges; vectorchar inEdges; // 查找发出边和抵达边 for (int j 0; j n; j) { // 出度当前节点这一行设置标志为1发出边的个数 if (matrix[i][j] 1) { outEdges.push_back(nodes[j]); } // 入度当前节点这一列设置标志为1抵达边的个数 if (matrix[j][i] 1) { inEdges.push_back(nodes[j]); } } // 计算出度和入度 int outDegree outEdges.size(); int inDegree inEdges.size(); // 打印节点的详细信息 cout 节点 node : endl; cout 出度 : outDegree; cout , 发出边 outEdges.size() ) : ; for (const auto edge : outEdges) { cout edge ; } cout endl ; cout 入度 : inDegree; cout , 抵达边 inEdges.size() ) : ; for (const auto edge : inEdges) { cout edge ; } cout endl; } } int main() { int n 0; cout 输入拓扑图中节点个数 : ; while (cin n) { cout 输入各个节点的的名称(a~z) : ; string nodes(n, \0); for (int i 0; i n; i) { cin nodes[i]; } vectorpairchar, char edges; // 输入各个节点的邻接点 for (int i 0; i n; i) { cout 输入节点 nodes[i] 的邻接点(多个用空格分隔按回车结束) : ; string inputStr; // 使用 getline(cin ws, inputStr) 跳过空白并读取整行 getline(cin ws, inputStr); istringstream iss(inputStr); char neighbor; while (iss neighbor) { if (neighbor a neighbor z) { edges.push_back({nodes[i], neighbor}); } } } // 构建邻接矩阵 auto matrix AdjMatrixBUild(n, nodes, edges); // 打印图的拓扑结构 GraphTopologyPrint(n, nodes, matrix); // 打印邻接矩阵 AdjMatrixPrint(nodes, matrix); // 打印各个节点的详细信息 NodeDetailsPrint(n, nodes, matrix); cout endl 继续输入其他拓扑图中节点个数 : endl; cout 输入节点个数 : ; } return 0; }测试运行结果5. 带权图带权图也叫做网“在带权图中如果vi到vj有边则邻接矩阵M[i][j]w{ij}否则可以设置M[i][j]∞。”当然如果正常边权不会出现负数的情况下也可以设置为-1或其他负数。节点数组vex[] {a, b, c, d, e}图中的代码注释“const int inf 0x3f3f3f3f;”通常表示无穷大的值邻接矩阵的示例其中包含具体的权重值以及无穷大符号∞。1. 带权图邻接矩阵的定义与规则对于具有 n个顶点的带权有向图其邻接矩阵是一个 n×n的方阵 M。矩阵元素 M[i][j]表示从顶点 vi到顶点 vj的边的权重若存在从 vi到 vj的有向边则 M[i][j]wij其中 wij是该边的权值。若不存在这样的边则 M[i][j]∞用一个足够大的常数表示如0x3f3f3f3f。特殊情况通常规定 M[i][i]0表示顶点到自身的距离为0 M[i][i]∞表示没有这条边自己不可以与自己有权重除非特别定义自环权重。对于无向带权图矩阵是对称的即 M[i][j]M[j][i]。2. 示例图与矩阵的对应关系图片左侧应展示了一个带权有向图包含5个顶点 a,b,c,d,e边上的数字表示权重。顶点数组 vex[]按顺序存储顶点名称矩阵的行列索引与此顺序对应。4. 带权图邻接矩阵的特性非对称性有向图的邻接矩阵通常不对称因为边的方向性可能导致权重不同或反向无边。对角线元素通常为0表示顶点到自身的距离为0。空间复杂度O(n2)适合稠密图。权重的含义可以表示距离、费用、时间、容量等具体取决于应用场景。5. 应用场景与算法基础最短路径算法如 Floyd-Warshall 算法直接基于邻接矩阵进行动态规划。网络流问题权重可表示边的容量。旅行商问题TSP权重表示城市间的距离。可达性分析通过矩阵乘法可计算经过若干步的路径总权重。代码实例1: /adj_matrix_02_weighted_graph_00.cc构建有全图打印节点拓扑和节点之间的信息// 构建有全图打印节点拓扑和节点之间的信息 #include iostream #include vector #include sstream #include string #include map #include unordered_map #include climits #include iomanip using namespace std; // 定义边的结构体包含起点、终点和权重 struct Edge { char from; char to; int weight; }; // 构建带权图的邻接矩阵 vectorvectorint AdjMatrixBUild(int n, const string nodes, const vectorEdge edges) { // 建立字符到索引的映射表 unordered_mapchar, int nodeIndexMap; for (int i 0; i n; i) { nodeIndexMap[nodes[i]] i; } // 初始化邻接矩阵所有初始化设置为INT_MAX表示没有连接无穷大 vectorvectorint matrix(n, vectorint(n, INT_MAX)); // 设置对角线为0表示节点到自身的距离为0 for (int i 0; i n; i) { matrix[i][i] 0; } // 根据边的信息填充邻接矩阵 for (const auto edge : edges) { int cu nodeIndexMap[edge.from]; int cv nodeIndexMap[edge.to]; matrix[cu][cv] edge.weight; // 注意带权有向图只需要设置单向边不需要对称设置 } return matrix; } // 打印带权邻接矩阵 void AdjMatrixPrint(const string nodes, const vectorvectorint matrix) { cout endl 对应带权有向图的邻接矩阵 : endl; cout ; for (const char ch : nodes) { cout ch ; } cout endl; for (int i 0; i nodes.size(); i) { cout nodes[i] | ; for (int j 0; j nodes.size(); j) { if (matrix[i][j] INT_MAX) { cout ∞ ; } else { cout matrix[i][j] ; } } cout endl; } cout endl; } // 图的拓扑结构打印将每个节点的邻接点及权重添加到当前节点后再一一打印出来 void GraphTopologyPrint(int n, string nodes, const vectorvectorint matrix) { // 打印图的拓扑结构 cout endl 当前带权有向图的拓扑结构 : endl; mapchar, vectorpairchar, int topoMap; // 构建每个节点的邻居列表出边方向包含权重 for (int i 0; i n; i) { char node nodes[i]; vectorpairchar, int neighbors; for (int j 0; j n; j) { if (matrix[i][j] ! INT_MAX i ! j) { // 排除自身 neighbors.push_back({nodes[j], matrix[i][j]}); } } topoMap[node] neighbors; } // 打印每个节点及其邻接点和权重 for (const auto entry : topoMap) { cout entry.first - ; if (entry.second.empty()) { cout 无出边; } else { for (const auto neighbor : entry.second) { cout neighbor.first ( neighbor.second ) ; } } cout endl; } cout endl; } // 打印节点的详细信息包括出度、入度、权重信息 void NodeDetailsPrint(int n, string nodes, const vectorvectorint matrix) { cout 节点的详细信息 : endl; // 统计每个节点的出边和入边并计算总权重 vectorpairint, int totalWeights(n, {0, 0}); // 第一个是总出边权重第二个是总入边权重 for (int i 0; i n; i) { char node nodes[i]; vectorpairchar, int outEdges; // 出边目标节点和权重 vectorpairchar, int inEdges; // 入边源节点和权重 // 查找发出边和抵达边 for (int j 0; j n; j) { // 出度当前节点这一行设置非INT_MAX且不为自身的边 if (matrix[i][j] ! INT_MAX i ! j) { outEdges.push_back({nodes[j], matrix[i][j]}); totalWeights[i].first matrix[i][j]; } // 入度当前节点这一列设置非INT_MAX且不为自身的边 if (matrix[j][i] ! INT_MAX j ! i) { inEdges.push_back({nodes[j], matrix[j][i]}); totalWeights[i].second matrix[j][i]; } } // 计算出度和入度 int outDegree outEdges.size(); int inDegree inEdges.size(); // 打印节点的详细信息 cout 节点 node : endl; // 出度信息 cout 出度 : outDegree; if (outDegree 0) { cout , 发出边( outDegree ) : ; for (const auto edge : outEdges) { cout node → edge.first ( edge.second ) ; } cout , 总出边权重: totalWeights[i].first; } else { cout , 无发出边; } cout endl; // 入度信息 cout 入度 : inDegree; if (inDegree 0) { cout , 抵达边( inDegree ) : ; for (const auto edge : inEdges) { cout edge.first → node ( edge.second ) ; } cout , 总入边权重: totalWeights[i].second; } else { cout , 无抵达边; } cout endl endl; } } // 打印路径权重和最短路径信息带权图的优越性体现 void PathAnalysisPrint(int n, string nodes, const vectorvectorint matrix) { cout 带权图路径分析体现带权图的优越性 endl; // 检查是否存在直接连接 cout 1. 直接连接检查 endl; bool hasDirectConnections false; for (int i 0; i n; i) { for (int j 0; j n; j) { if (i ! j matrix[i][j] ! INT_MAX) { cout nodes[i] → nodes[j] : 权重 matrix[i][j] endl; hasDirectConnections true; } } } if (!hasDirectConnections) { cout 没有直接连接 endl; } cout endl; // 计算所有可能的两步路径 cout 2. 两步路径计算带权图可以计算路径总权重 endl; for (int i 0; i n; i) { for (int j 0; j n; j) { if (i ! j) { // 查找中间节点k使得i→k→j存在 for (int k 0; k n; k) { if (k ! i k ! j matrix[i][k] ! INT_MAX matrix[k][j] ! INT_MAX) { int totalWeight matrix[i][k] matrix[k][j]; cout nodes[i] → nodes[k] → nodes[j] : 总权重 matrix[i][k] matrix[k][j] totalWeight endl; } } } } } cout endl; // 显示带权图的优势可以找到最小权重路径 cout 3. 最小直接连接权重查找 endl; int minWeight INT_MAX; pairint, int minEdge {-1, -1}; for (int i 0; i n; i) { for (int j 0; j n; j) { if (i ! j matrix[i][j] ! INT_MAX matrix[i][j] minWeight) { minWeight matrix[i][j]; minEdge {i, j}; } } } if (minEdge.first ! -1) { cout 最小权重边: nodes[minEdge.first] → nodes[minEdge.second] ( minWeight ) endl; } else { cout 没有找到权重边 endl; } cout endl endl; } int main() { int n 0; cout 输入拓扑图中节点个数 : ; while (cin n) { if (n 0 || n 26) { cout 节点个数应在1-26之间,请重新输入: ; continue; } cout 输入各个节点的名称(a~z) : ; string nodes(n, \0); for (int i 0; i n; i) { cin nodes[i]; } vectorEdge edges; // 输入各个节点的邻接点及权重 for (int i 0; i n; i) { cout 输入节点 nodes[i] 的邻接点及权重(格式:邻接点 权重多个用空格分隔按回车结束) : ; string inputStr; // 使用 getline(cin ws, inputStr) 跳过空白并读取整行 getline(cin ws, inputStr); istringstream iss(inputStr); char neighbor; int weight; while (iss neighbor weight) { if (neighbor a neighbor z) { edges.push_back({nodes[i], neighbor, weight}); } else { cout 警告: 邻接点 neighbor 不是有效的小写字母已跳过 endl; } } } // 构建邻接矩阵 auto matrix AdjMatrixBUild(n, nodes, edges); // 打印图的拓扑结构 GraphTopologyPrint(n, nodes, matrix); // 打印邻接矩阵 AdjMatrixPrint(nodes, matrix); // 打印各个节点的详细信息 NodeDetailsPrint(n, nodes, matrix); // 打印路径分析体现带权图的优越性 PathAnalysisPrint(n, nodes, matrix); cout endl 继续输入其他拓扑图中节点个数 : endl; cout 输入节点个数(输入0退出): ; } cout 程序结束 endl; return 0; }测试运行结果6. 邻接矩阵应用使用邻接矩阵计算最短路径的dijkstra算法代码示例 /path_min_00_dijkstra_00.cc// 使用邻接矩阵计算最短路径的dijkstra算法实现 #include iostream #include algorithm #include stack using namespace std; const int N 1005; const int INF 0x3FFFFFFF; // 无穷大 int G[N][N]; // 邻接矩阵 int dist[N]; // 最短距离 int p[N]; // 前驱节点 int n; // 节点个数 int m; // 节点间边数 bool flag[N]; // false表示v-s集合true表示s集合 void dijkstra(int u) { // 初始化 for (int i 1; i n; i) { dist[i] G[u][i]; flag[i] false; if (dist[i] INF) { p[i] -1; } else { p[i] u; } } dist[u] 0; flag[u] true; // 主循环 for (int i 1; i n; i) { int minDist INF, minNode -1; // 在未访问节点中寻找距离最小的节点 for (int j 1; j n; j) { if (!flag[j] dist[j] minDist) { minDist dist[j]; minNode j; } } // 所有节点已访问或剩余节点不可达 if (minNode -1) return; flag[minNode] true; // 松弛操作更新相邻节点的最短距离 for (int j 1; j n; j) { if (!flag[j] G[minNode][j] ! INF dist[j] dist[minNode] G[minNode][j]) { dist[j] dist[minNode] G[minNode][j]; p[j] minNode; } } } } // 递归打印从源点到目标节点的路径 void printPath(int u) { if (p[u] -1) { cout u; return; } printPath(p[u]); cout - u; } int main() { // 初始化邻接矩阵 fill(G[0], G[0] N*N, INF); cout 输入节点数n和边数m: ; cin n m; cout 输入 m 条边起点 终点 权重: endl; for (int i 0; i m; i) { int u, v, w; cin u v w; G[u][v] w; // 无向图添加反向边如果需要 // G[v][u] w; } int source; cout 输入源点: ; cin source; dijkstra(source); cout \n源点 source 到各节点的最短距离: endl; for (int i 1; i n; i) { cout 源点 source - 节点 i : ; if (dist[i] INF) { cout 不可达; } else { cout 最短距离 : dist[i] \t路径: ; printPath(i); } cout endl; } return 0; }测试数据1输入节点数n和边数m: 5 7输入7条边起点 终点 权重:1 2 41 3 12 3 22 4 53 2 13 4 84 5 3输入源点: 1测试结果测试数据2输入节点数n和边数m: 5 7输入7条边起点 终点 权重:1 2 41 3 12 3 22 4 53 2 13 4 84 5 3输入源点: 27. 总结邻接矩阵优点快速判断两顶点之间是否有边。方便计算各顶点的度。邻接矩阵缺点不便于增删顶点。不便于访问所有邻接点。空间复杂度高。
