C++如何使用数组实现邻接矩阵（图论）-C++-PHP中文网

优先选 std::vector——它支持动态大小、自动初始化、边界安全（配合 .at()），且避免大图栈溢出；原生数组 intn 易栈溢出，手动 new 易内存泄漏，仅适用于极小确定规模图。

c++如何使用数组实现邻接矩阵（图论）

邻接矩阵用什么数组类型最合适

二维 std::vector<:vector>></:vector> 或原生 int[N][N] 都能用，但实际写图算法时，**优先选 std::vector<:vector>></:vector>**——它支持动态大小、自动初始化、边界安全（配合 .at()），且不会因栈溢出崩在大图上（比如 N=10000 时，int[10000][10000] 直接栈溢出）。

常见错误是写成 int* adj[N] 或手动 new int*[N]：既容易内存泄漏，又难管理。除非你明确控制内存且图极小（N

初始化建议统一设为一个“无效值”，比如无向图用 -1 表示无边，带权图用 INT_MAX 表示无穷大（需 #include <climits></climits>）：

const int INF = INT_MAX;
int n = 5;
std::vector<:vector>> g(n, std::vector<int>(n, INF));
// 对角线自环可设为 0（依题意）
for (int i = 0; i <h3>添加边时怎么处理有向/无向和重边</h3>
<p>邻接矩阵本质是“点对点映射”，<code>g[u][v]</code> 就是 u → v 的边权。关键在赋值逻辑：</p>
<ul>
<li>有向边 u→v：只改 <code>g[u][v] = weight</code>
</li>
<li>无向边 u-v：必须同步改 <code>g[u][v] = g[v][u] = weight</code>
</li>
<li>重边（多条 u→v）：如果要保留最短边，用 <code>g[u][v] = std::min(g[u][v], weight)</code>；如果要累加（如流量），用 <code>g[u][v] += weight</code>
</li>
</ul>
<p>别忘了检查下标越界——哪怕用了 <code>vector</code>，<code>g[u][v]</code> 在 u 或 v ≥ n 时仍是未定义行为。上线前加断言更稳：</p>
<pre class="brush:php;toolbar:false;">
assert(u >= 0 && u = 0 && v <h3>遍历邻接矩阵比邻接表慢吗</h3><p>是的，**时间复杂度固定是 O(N²)**，不管图稀疏还是稠密。这意味着：当 N=10000 时，光初始化就要 1e8 次赋值，遍历所有边更是 1e8 次访问——现代 CPU 能扛住，但远不如邻接表遍历实际边数（O(V+E)）高效。</p><div class="aritcle_card flexRow artxards">
											<div class="artcardd flexRow">
												<a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill5502" title="C++ Code Review Master"><img
														src="https://img.php.cn/upload/skill/000/000/081/179051228971575.jpg" alt="C++ Code Review Master" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
												<div class="aritcle_card_info flexColumn">
													<a rel="nofollow" href="/xiazai/skill5502" title="C++ Code Review Master" class="overflowclass">C++ Code Review Master</a>
													<p class="overflowclass">组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。</p>
												</div>
												<a rel="nofollow" href="/xiazai/skill5502" title="C++ Code Review Master" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
												</a>
											</div>
										</div><p>所以邻接矩阵只适合以下场景：</p>

N ≤ 1000，且需要频繁查“u 和 v 是否有边”（O(1)）
算法本身依赖全局矩阵操作，比如 Floyd-Warshall（求多源最短路）、求图的幂（判断可达性）、矩阵快速幂优化 DP
图非常稠密（E ≈ N²），此时邻接表的指针开销反而不划算

如果你只是做 DFS/BFS/Prim，却硬套邻接矩阵，性能会明显掉一截——不是语法错，是模型选错了。

读入图数据时怎么避免覆盖或漏填

常见错误是把边循环写成 for (int i = 0; i 却忘了顶点编号是否从 0 开始。比如题目给的是 1-indexed 边（u=1, v=2），而你直接 <code>g[u][v] = w，就会访问 g[1][2] 而跳过 g[0][0] ——结果第一行第一列永远是初始值，图不完整。

稳妥做法：统一转 0-indexed，并校验输入范围：

int u, v, w;
cin >> u >> v >> w;
u--; v--; // 转 0-indexed
if (u = n || v = n) continue; // 安全跳过非法输入
g[u][v] = w;
if (!directed) g[v][u] = w;

另外注意：有些题中边权可能是负数（如 Bellman-Ford），别用 unsigned int 存——符号位一丢，负权就变巨大正数，算法直接失效。

邻接矩阵看着简单，真正卡住人的从来不是声明那行代码，而是下标偏移、初始化值语义、以及“该不该用它”的判断——尤其是当测试数据突然从 N=100 涨到 N=5000 时，栈溢出或超时往往来得毫无征兆。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！