图

JavaJuice约 931 字大约 3 分钟

图的详细讲解

1. 图的定义与特点

图是一种非线性数据结构，由顶点集合 ( V ) 和边集合 ( E ) 组成，通常表示为 ( G(V, E) )：

顶点（Vertex）：图中的基本单位，例如社交网络中的用户。
边（Edge）：连接顶点的线，表示顶点之间的关系，例如好友关系。

图的主要特点：

关系的复杂性：顶点之间的关系可以是任意的，不局限于层次结构或线性关系。
多样性：
- 有向图：边有方向，例如 A 指向 B。
- 无向图：边无方向，例如 A 和 B 互为邻居。
- 带权图：边有权重，表示关系的强弱或代价。
- 无权图：边仅表示是否存在关系。

2. 图的基本概念

2.1 顶点

图的基本单位。
对应实际问题中的数据元素，如城市、用户等。

2.2 边

顶点之间的连接，表示关系。
有向边：从一个顶点指向另一个顶点，例如微博关注。
无向边：没有方向，例如朋友关系。

2.3 度

一个顶点的边数。
- 无向图：边数为度。
- 有向图：
  - 出度：从顶点出发的边数。
  - 入度：指向顶点的边数。

2.4 图的分类

无向图：边无方向，顶点 A 和 B 的关系对称。
有向图：边有方向，顶点 A 和 B 的关系不对称。
无权图：边仅表示关系存在。
带权图：边有权重，表示关系的强弱或成本。

3. 图的存储方法

3.1 邻接矩阵

使用二维数组存储顶点和边的关系。
优点：查询两个顶点的关系高效，时间复杂度为 ( O(1) )。
缺点：空间浪费，尤其是稀疏图。

示例：无向图邻接矩阵

    A  B  C  D
A   0  1  0  1
B   1  0  1  1
C   0  1  0  1
D   1  1  1  0

3.2 邻接表

每个顶点用一个链表存储其邻接顶点。
优点：节省空间，适合稀疏图。
缺点：查询顶点关系较慢，时间复杂度为 ( O(n) )。

示例：无向图邻接表

A -> B -> D
B -> A -> C -> D
C -> B -> D
D -> A -> B -> C

4. 图的搜索算法

4.1 广度优先搜索（BFS）

思想：从一个顶点开始，按照层次逐层扩展访问所有顶点。
实现：利用队列存储待访问的顶点。
时间复杂度：( O(V + E) )（顶点数 ( V )，边数 ( E )）。

代码示例（邻接表实现 BFS）：

public void bfs(int start, List<List<Integer>> adjList) {
    boolean[] visited = new boolean[adjList.size()];
    Queue<Integer> queue = new LinkedList<>();
    queue.add(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
        int current = queue.poll();
        System.out.print(current + " ");
        for (int neighbor : adjList.get(current)) {
            if (!visited[neighbor]) {
                queue.add(neighbor);
                visited[neighbor] = true;
            }
        }
    }
}

4.2 深度优先搜索（DFS）

思想：从一个顶点出发，尽可能深入访问顶点，直到无路可走后回溯。
实现：递归或使用栈。
时间复杂度：( O(V + E) )。

代码示例（递归实现 DFS）：

public void dfs(int current, boolean[] visited, List<List<Integer>> adjList) {
    visited[current] = true;
    System.out.print(current + " ");
    for (int neighbor : adjList.get(current)) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited, adjList);
        }
    }
}

5. 图的应用场景

社交网络分析：
- 顶点表示用户，边表示关系。
- 例如：找出好友推荐（路径搜索）。
路径规划：
- 交通网络、地图导航。
- 例如：Dijkstra 算法用于最短路径计算。
网络流分析：
- 数据包传输、最大流问题。
任务调度：
- 顶点表示任务，边表示依赖关系。
- 使用拓扑排序处理任务依赖。
搜索引擎：
- 图用于分析网页链接关系（PageRank 算法）。

图是计算机科学中极为重要的数据结构，广泛应用于日常生活和技术领域。