visited数组是避免死循环、确保顶点仅处理一次的核心机制；必须用外部数组或哈希表而非节点字段，因图结构常由外部数据构建、需多次独立遍历且要保持原始数据纯净。
图遍历中，变量访问状态标记位（通常叫 visited 数组）不是可有可无的辅助手段，而是避免死循环、保证每个顶点只被处理一次的核心机制。它看似简单，但在多线程、动态图、递归深度大或内存受限场景下，极易出错。
标记位为什么必须用数组（或哈希表），不能靠节点自带字段？
很多初学者会想：给每个节点加个 isVisited 成员不就行了？问题在于：
- 图结构常由外部数据构建（如邻接表数组、边列表），节点本身可能只是整数编号或字符串，没有“成员”可改；
- 同一图结构可能被多次遍历（如求连通分量、拓扑排序、环检测），每次都需要干净的初始状态；
- 若节点是第三方对象（如用户结构体、网页URL），修改其字段会污染原始数据，破坏函数纯度和线程安全性。
如何选型：bool 数组 vs. vector vs. unordered_set？
关键看顶点编号是否连续、范围是否已知：
-
顶点编号为 0～n−1 且 n 已知 → 用
vector<bool> visited(n, false)</bool>或 C 风格bool visited[MAX_N]。空间 O(n)，访问 O(1)，最常用也最高效； -
顶点是字符串、UUID 或稀疏编号（如 1001, 2048, 99999） → 用
unordered_set<string></string>或set<int></int>。虽有哈希/红黑树开销，但避免大数组浪费； - 慎用
vector<bool></bool>的特化实现（C++ 标准要求其位压缩），它不支持取地址、迭代器行为异常——调试时容易误判“没标记上”，建议显式用vector<char></char>或vector<int></int>替代。
常见陷阱与绕过技巧
标记位失效往往不是写错了，而是逻辑时机不对：
-
DFS 中标记位置错：必须在递归调用前就设
visited[v] = true，否则同一节点可能被多个邻居重复压栈/入队； - BFS 中重复入队：不是等出队时才标记，而要在入队前检查并标记——否则一个节点可能被多个父节点同时加入队列；
-
多起点遍历漏重置：求所有连通分量时，每进入一个新未访问节点就要启动一次 DFS/BFS，但
visited是全局共用的，无需重置，只需外层循环跳过已访问点； -
带权图/有向图的误导：权重和方向不影响标记逻辑——标记的是“顶点是否来过”，跟边无关；但要注意：有向图中 A→B 可达不代表 B→A 可达，
visited只管当前遍历方向的可达性。
进阶：不用 visited 数组也能安全遍历？
可以，但代价明确：
- 用 set 记录路径（DFS 回溯路径）：仅用于找某条特定路径（如迷宫出口），空间随深度增长，无法替代全局 visited；
- 拓扑序中用状态三值标记（未访问/访问中/已完成）：用于环检测，其中“访问中”状态能捕获回边，比二值 visited 更强；
- 函数式风格：传入已访问集合副本（如 Python 中 frozenset），避免副作用，但每次递归都拷贝，时间空间开销大，仅适合小图或教学演示。
