10-搜索/03-简单图上搜索

简单图上搜索

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

图的存储

详见 图论基础。

图上 DFS

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);
}

图上 BFS

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);
            }
    }
}

连通分量计数

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

检测环

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

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;
}