查看“︁10-搜索/03-简单图上搜索”︁的源代码


== 简单图上搜索 ==

在图（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:三三文档]]