数据结构 - 图

图（Graph）是由节点（Vertex）和边（Edge）组成的一种数据结构，用于描述不同事物之间的关系。图的算法涉及到图的遍历、最短路径、最小生成树等多个方面，下面简要介绍几种常见的图相关算法：

1. 图的表示方式：

   • 邻接矩阵：使用二维数组表示节点之间的连接关系，适合稠密图。
   • 邻接表：使用链表或数组列表表示节点和相邻节点的连接关系，适合稀疏图。

2. 图的遍历：

   • 深度优先搜索（DFS）：从起始节点开始，沿着路径直到末端，然后回溯到上一个节点，继续探索未访问的路径。
   • 广度优先搜索（BFS）：从起始节点开始，先访问所有与该节点相邻的节点，然后依次访问这些节点的邻居节点，层层递进，直到所有节点均被访问。

3. 最短路径算法：

   • Dijkstra算法：用于计算带权重图中单源最短路径的算法，通过贪心法和逐步扩展已找到的最短路径集合来实现。
   • Bellman-Ford算法：适用于计算带有负权重边的图的单源最短路径，通过重复减少可能的最短路径集合来实现。

4. 最小生成树算法：

   • Prim算法：基于贪心策略，从一个节点开始逐步扩展，选择连接已包含节点和未包含节点的最小权重边。
   • Kruskal算法：将所有边按权重排序，然后逐个加入到最小生成树中，保证不形成环路。

5. 拓扑排序：

   • 拓扑排序：适用于有向无环图（DAG），一种将图中所有节点线性排序的算法，使得对于每一对有向边 u -> v，均有 u 在排序列表中排在 v 的前面。

6. 关键路径算法：

   • 关键路径法：用于确定项目的最短时间完成路径，依赖于图的拓扑排序和任务的持续时间。

图的算法在实际应用中涵盖了广泛的领域，如网络路由、社交网络分析、推荐系统等。选择合适的图算法取决于图的类型（有向图、无向图、带权重图等）和具体的问题需求。

当谈论图的表示方式时，具体的例子可以帮助更好地理解不同表示方式的应用场景和优缺点。

图的表示方式

1. 邻接矩阵 (Adjacency Matrix)

假设我们有以下简单的无向图：

   A
 /   \
B --- C

使用邻接矩阵表示该图：

• 节点集合：( {A, B, C} )
• 邻接矩阵：

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

在邻接矩阵中：

• ( M[i][j] = 1 ) 表示节点 ( i ) 与节点 ( j ) 之间有边。
• ( M[i][j] = 0 ) 表示节点 ( i ) 与节点 ( j ) 之间无边。

优点：

• 快速判断任意一对节点之间是否有边，时间复杂度 ( O(1) )。
• 适用于稠密图，节省空间。

缺点：

• 对于稀疏图，会浪费大量空间。
• 添加或删除节点的操作复杂度高，为 ( O(V^2) )。

2. 邻接表 (Adjacency List)

继续使用上述无向图的例子，使用邻接表表示该图：

• 邻接表：

A -> B, C
B -> A, C
C -> A, B

在邻接表中：

• 每个节点 ( A, B, C ) 分别指向与其相邻的节点列表。

优点：

• 适用于稀疏图，节省空间。
• 添加或删除节点的操作简单，时间复杂度 ( O(1) ) 或 ( O(d) )，其中 ( d ) 是相邻节点的数量。

缺点：

• 查询任意一对节点之间是否有边的效率较低，需要遍历链表或列表，时间复杂度取决于相邻节点的数量 ( O(d) )。

应用场景选择：

• 如果我们知道图是密集的，即边的数量接近 ( V^2 )，邻接矩阵更为适合，因为可以快速判断边的存在。
• 如果图是稀疏的，即边的数量远小于 ( V^2 )，邻接表更为适合，因为节省空间且支持高效的节点添加和删除操作。

这些例子希望能够帮助理解图的不同表示方式的实际应用和选择。

图的遍历方式

图的遍历是指按照一定规则访问图中所有节点的过程。常见的图遍历算法包括深度优先搜索（DFS）和广度优先搜索（BFS）。这两种算法在图的结构上有不同的特点和应用场景。

1. 深度优先搜索（DFS）

深度优先搜索从图的某个起始节点出发，沿着一条路径尽可能深地访问，直到该路径上所有节点都被访问过，然后回溯到上一个节点，继续探索未访问的路径。

实现过程：

1. 使用递归（或栈）来实现深度优先搜索。

2. 标记访问过的节点，防止重复访问，通常使用布尔数组（visited）。

3. 遍历邻接节点：

   • 对于当前节点，依次访问其未被访问过的邻接节点。
   • 对每个邻接节点，递归调用DFS函数。

示例：

考虑以下无向图的邻接表表示：

A -> B, C
B -> A, C, D
C -> A, B, E
D -> B
E -> C

从节点 A 出发的深度优先搜索过程：

• 访问顺序：A -> B -> C -> E -> D

代码示例（Java）：

import java.util.*;

class Graph {
    private int V; // 节点数
    private LinkedList<Integer> adj[]; // 邻接表

    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    void DFSUtil(int v, boolean visited[]) {
        visited[v] = true;
        System.out.print(v + " ");

        Iterator<Integer> i = adj[v].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }

    void DFS(int v) {
        boolean visited[] = new boolean[V];
        DFSUtil(v, visited);
    }

    public static void main(String args[]) {
        Graph g = new Graph(5);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(1, 3);
        g.addEdge(2, 4);

        System.out.println("从节点 0 开始的 DFS 遍历：");
        g.DFS(0);
    }
}

2. 广度优先搜索（BFS）

广度优先搜索从图的某个起始节点出发，首先访问该节点的所有未访问邻接节点，然后逐层向外扩展，直到所有可达节点都被访问。

实现过程：

1. 使用队列来实现广度优先搜索。

2. 标记访问过的节点，防止重复访问，通常使用布尔数组（visited）。

3. 遍历邻接节点：

   • 对于当前节点，依次访问其未被访问过的邻接节点。
   • 将每个邻接节点加入队列，并标记为已访问。

示例：

继续考虑上述无向图的邻接表表示，从节点 A 出发的广度优先搜索过程：

• 访问顺序：A -> B -> C -> D -> E

代码示例（Java）：

import java.util.*;

class Graph {
    private int V; // 节点数
    private LinkedList<Integer> adj[]; // 邻接表

    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    void BFS(int s) {
        boolean visited[] = new boolean[V];
        LinkedList<Integer> queue = new LinkedList<>();

        visited[s] = true;
        queue.add(s);

        while (queue.size() != 0) {
            s = queue.poll();
            System.out.print(s + " ");

            Iterator<Integer> i = adj[s].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }

    public static void main(String args[]) {
        Graph g = new Graph(5);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(1, 3);
        g.addEdge(2, 4);

        System.out.println("从节点 0 开始的 BFS 遍历：");
        g.BFS(0);
    }
}

总结：

• DFS 适合深度优先搜索，通过递归或栈实现，能够深入到每条路径的最深处。
• BFS 适合广度优先搜索，通过队列实现，逐层扩展，适合寻找最短路径或层级遍历。

这些算法和示例希望能够帮助理解图的遍历及其实现方法。