数据结构---图（Graph）

        图（Graph）是一种非常灵活且强大的数据结构，用于表示实体之间的复杂关系。在图结构中，数据由一组节点（或称为顶点）和连接这些节点的边组成。图可以用于表示社交网络、交通网络、网络路由等场景。

1. 基本概念

• 节点（Vertex）：图中的一个点，代表一个对象或实体。

• 边（Edge）：连接两个节点的线，代表节点之间的关系。

• 邻接（Adjacency）：如果两个节点之间有边相连，则称这两个节点是邻接的。

• 路径（Path）：一系列相连的边，从一个节点开始，经过若干个中间节点，到达另一个节点。

• 环（Cycle）：起点和终点是同一个节点的路径。

• 连通图（Connected Graph）：图中任意两个节点之间都存在路径。

• 强连通图（Strongly Connected Graph）：有向图中，任意两个节点之间都存在有向路径。

• 树（Tree）：一种特殊的图，没有环，且任意两个节点之间只有一条路径。

2. 表示方法

2.1 邻接矩阵（Adjacency Matrix）：

• 使用一个二维数组来表示图，数组的行和列代表节点，元素值表示节点之间是否有边。

• 适用于稠密图，即边的数量接近节点数量平方的图。

2.2 邻接表（Adjacency List）：

• 使用一个链表数组来表示图，每个链表包含与该节点相连的所有节点。

• 适用于稀疏图，即边的数量远小于节点数量平方的图。

3. 遍历算法

3.1 深度优先搜索（Depth-First Search, DFS）：

• 类似于树的前序遍历，使用栈（递归或显式栈）来实现。

• 从任意节点开始，尽可能深地搜索图的分支。

public class GraphDFS {private int V; // 节点数private LinkedList<Integer> adj[]; // 邻接表// 构造函数@SuppressWarnings("unchecked")public GraphDFS(int v) {V = v;adj = new LinkedList[v];for (int i = 0; i < v; ++i)adj[i] = new LinkedList();}// 添加边public void addEdge(int v, int w) {adj[v].add(w); // 添加w到v的邻接表}// DFS算法public void DFS(int v) {boolean visited[] = new boolean[V];// 调用递归的DFS函数DFSUtil(v, visited);}// 递归的DFS函数void DFSUtil(int v, boolean visited[]) {// 标记当前节点为已访问visited[v] = true;System.out.print(v + " ");// 递归访问所有未访问的邻接节点for (int i = 0; i < adj[v].size(); i++) {int n = adj[v].get(i);if (!visited[n])DFSUtil(n, visited);}}// 测试DFS算法public static void main(String[] args) {GraphDFS g = new GraphDFS(4);g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 2);g.addEdge(2, 0);g.addEdge(2, 3);g.addEdge(3, 3);System.out.println("DFS starting from vertex 2 : ");g.DFS(2);}
}

3.2 广度优先搜索（Breadth-First Search, BFS）：

• 类似于树的层序遍历，使用队列来实现。

• 从任意节点开始，逐层遍历图中的节点。

import java.util.*;public class GraphBFS {private int V; // 节点数private LinkedList<Integer> adj[]; // 邻接表// 构造函数@SuppressWarnings("unchecked")public GraphBFS(int v) {V = v;adj = new LinkedList[v];for (int i = 0; i < v; ++i)adj[i] = new LinkedList();}// 添加边public void addEdge(int v, int w) {adj[v].add(w); // 添加w到v的邻接表}// BFS算法public void BFS(int s) {boolean visited[] = new boolean[V];// 创建一个队列用于BFSQueue<Integer> queue = new LinkedList<>();// 标记起始节点为已访问并入队visited[s] = true;queue.add(s);while (queue.size() != 0) {// 出队一个节点s = queue.poll();System.out.print(s + " ");// 访问其所有未访问的邻接节点for (int i = 0; i < adj[s].size(); ++i) {int n = adj[s].get(i);if (!visited[n]) {visited[n] = true;queue.add(n);}}}}// 测试BFS算法public static void main(String[] args) {GraphBFS g = new GraphBFS(4);g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 2);g.addEdge(2, 0);g.addEdge(2, 3);g.addEdge(3, 3);System.out.println("BFS starting from vertex 2 : ");g.BFS(2);}
}

4. 算法应用

1. 最短路径问题：

   1. Dijkstra算法：适用于带有非负权重的图。

   2. Bellman-Ford算法：适用于带有负权重的图。

   3. Floyd-Warshall算法：计算图中所有节点对的最短路径。

2. 最小生成树问题：

   1. Kruskal算法：贪心算法，适用于边的集合是无序的。

   2. Prim算法：贪心算法，适用于节点的集合是无序的。

3. 网络流问题：

   1. Ford-Fulkerson方法：计算网络中的最大流。

   2. Edmonds-Karp算法：使用BFS来实现Ford-Fulkerson方法。