33DAI：批量导入三三文档

2026-05-20T18:24:05Z

批量导入三三文档

←上一版本		2026年5月20日 (三) 18:24的版本
第90行：		第90行：
	[[Category:搜索]]		[[Category:搜索]]
	[[Category:三三文档]]		[[Category:三三文档]]

33DAI：导入1个版本

2026-05-20T18:12:21Z

导入1个版本

←上一版本		2026年5月20日 (三) 18:12的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:50:33Z

批量导入三三文档

新页面

== 简单图上搜索 ==

在图（Graph）上进行 DFS/BFS，用于遍历连通分量、检测环、求拓扑序等。

=== 图的存储 ===

详见 [[11-图论/01-图论基础|图论基础]]。

=== 图上 DFS ===

<syntaxhighlight lang="cpp">
vector<int> g[MAXN];
bool vis[MAXN];

void dfs(int u)
{
vis[u] = true;
cout << u << " "; // 访问节点
for (int v : g[u])
if (!vis[v])
dfs(v);
}
</syntaxhighlight>

=== 图上 BFS ===

<syntaxhighlight lang="cpp">
void bfs(int start)
{
queue<int> q;
q.push(start);
vis[start] = true;

while (!q.empty())
{
int u = q.front();
q.pop();
cout << u << " "; // 访问节点

for (int v : g[u])
if (!vis[v])
{
vis[v] = true;
q.push(v);
}
}
}
</syntaxhighlight>

=== 连通分量计数 ===

<syntaxhighlight lang="cpp">
int cnt = 0;
for (int i = 1; i <= n; i++)
if (!vis[i])
{
cnt++;
dfs(i); // 或 bfs(i)
}
cout << cnt << "\n";
</syntaxhighlight>

=== 检测环 ===

在 DFS 中记录当前路径上的节点：

<syntaxhighlight lang="cpp">
bool on_path[MAXN]; // 当前 DFS 路径上的节点

bool has_cycle(int u)
{
vis[u] = true;
on_path[u] = true;
for (int v : g[u])
{
if (!vis[v])
{
if (has_cycle(v))
return true;
}
else if (on_path[v]) // 当前路径上的节点，说明有环
return true;
}
on_path[u] = false;
return false;
}
</syntaxhighlight>

[[Category:搜索]]
[[Category:三三文档]]

10-搜索/03-简单图上搜索 - 版本历史

33DAI：​批量导入三三文档

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档