判断有向图与无向图是否为树

1. 概述

在图论中，树是一种特殊的图结构。本文将讲解如何判断一个给定的图是否构成树。

我们会介绍树的基本定义，以及在有向图和无向图中如何判断是否构成树。最后，我们会比较两种图结构的判断逻辑，并提供对应的算法实现。

2. 树的定义

一个图若要构成树，必须满足以下条件：

✅ 单根性：树中存在一个唯一的根节点。
✅ 单父性：除了根节点外，其余每个节点都只能有一个父节点。
✅ 连通性：从根节点出发，必须能访问到所有其他节点。

上述条件适用于树的基本结构，但在判断有向图和无向图是否为树时，具体实现方式略有不同。

3. 有向图判断

3.1 判断步骤

要判断有向图是否为树，需依次完成以下步骤：

查找根节点：根节点是没有入边的节点。如果找不到或找到多个根节点，则图不是树。
深度优先遍历（DFS）检查：从根节点开始遍历，确保每个节点只被访问一次，且只有一个父节点。
连通性验证：检查是否所有节点都被访问过。若有遗漏，则图不是树。

3.2 算法实现

boolean checkIfDirectedGraphIsTree(int n, List<int[]> edges) {
    int[] incomingEdges = new int[n + 1];
    for (int[] edge : edges) {
        incomingEdges[edge[1]]++;
    }

    int root = -1;
    int rootCount = 0;
    for (int i = 1; i <= n; i++) {
        if (incomingEdges[i] == 0) {
            root = i;
            rootCount++;
        }
    }

    if (rootCount != 1) return false;

    boolean[] visited = new boolean[n + 1];
    if (!directedDFS(root, visited)) return false;

    for (int i = 1; i <= n; i++) {
        if (!visited[i]) return false;
    }

    return true;
}

3.3 DFS 实现

boolean directedDFS(int u, boolean[] visited) {
    if (visited[u]) return false;
    visited[u] = true;

    for (int child : getNeighbors(u)) {
        if (!directedDFS(child, visited)) return false;
    }

    return true;
}

⚠️ 注意：该算法依赖于图的邻接表示。getNeighbors(u) 应返回节点 u 的所有子节点。

时间复杂度：O(V + E)，其中 V 是节点数，E 是边数。

4. 无向图判断

4.1 判断步骤

判断无向图是否为树的步骤如下：

DFS 检查：从任意节点出发，确保每个节点只有一个父节点（即无环）。
连通性验证：确保所有节点都被访问过。
若满足以上条件，则图是树。

4.2 算法实现

boolean checkIfUndirectedGraphIsTree(int n) {
    boolean[] visited = new boolean[n + 1];
    if (!undirectedDFS(1, -1, visited)) return false;

    for (int i = 1; i <= n; i++) {
        if (!visited[i]) return false;
    }

    return true;
}

4.3 DFS 实现

boolean undirectedDFS(int u, int parent, boolean[] visited) {
    if (visited[u]) return false;
    visited[u] = true;

    for (int neighbor : getNeighbors(u)) {
        if (neighbor != parent) {
            if (!undirectedDFS(neighbor, u, visited)) return false;
        }
    }

    return true;
}

⚠️ 注意：无向图中父子节点是双向的，因此在递归时要跳过父节点，避免误判为环。

时间复杂度：O(V + E)

5. 对比分析

步骤	有向图	无向图
根节点选择	无入边的节点	可从任意节点开始
DFS 检查	节点不能被访问多次	节点不能被访问多次，且需跳过父节点
连通性检查	所有节点必须被访问	所有节点必须被访问
时间复杂度	O(V + E)	O(V + E)

6. 总结

本文介绍了判断一个图是否为树的完整逻辑与实现方式：

树的基本定义是判断的基础。
有向图需要先确定根节点，再进行 DFS 和连通性检查。
无向图则无需指定根节点，但要注意父子边的处理。
两者的时间复杂度均为 O(V + E)，适用于中等规模图的判断。

通过本文提供的算法与对比，可以快速判断任意图是否构成树结构，适用于图算法、数据结构分析等场景。✅

Persistence

REST

Security