图结构与高级数据结构的学习笔记一

• 学习内容:

  • 图（Graph）：
    • 图的基本概念、表示方法（邻接矩阵、邻接表）。
    • 图的遍历（深度优先搜索DFS、广度优先搜索BFS）。
  • 最短路径算法：
    • Dijkstra算法、Bellman-Ford算法的理解与实现。
  • 最小生成树（MST）：
    • Kruskal算法、Prim算法的理解与实现。

• 实践:

  • 实现图的基本操作和遍历算法。
  • 用Dijkstra算法解决最短路径问题，理解其在现实世界中的应用。

1. 图的基本概念

• 定义: 图由**顶点（Vertex）和边（Edge）**组成。顶点表示图中的对象，边表示对象之间的关系。
• 分类:
  • 有向图: 边有方向性，表示从一个顶点到另一个顶点的单向连接。
  • 无向图: 边没有方向性，表示两个顶点之间的双向连接。
• 图的度:
  • 出度（Out-degree）: 从某顶点出发的边的数量。
  • 入度（In-degree）: 指向某顶点的边的数量。

2. 图的表示方法

• 邻接矩阵（Adjacency Matrix）:

  • 用一个二维数组表示图。如果顶点 i 到顶点 j 有边，则矩阵中的元素为 1（或边的权重），否则为 0。
  • 优点: 快速检查两个顶点是否有边。
  • 缺点: 对于稀疏图，浪费空间。

• 邻接表（Adjacency List）:

  • 每个顶点有一个链表（或数组），链表中存储与该顶点相邻的顶点。
  • 优点: 节省空间，特别是对于稀疏图。
  • 缺点: 检查两个顶点是否有边比较慢。

3. 图的遍历

• 深度优先搜索（DFS）:

  • 类似于树的先序遍历，沿着每个分支走到底，再回溯到上一个顶点，继续探索其他未访问的分支。
  • 实现: 使用栈（可以通过递归实现）。
  • 时间复杂度: O(V + E)，其中 V 是顶点数，E 是边数。

• 广度优先搜索（BFS）:

  • 类似于树的层序遍历，逐层探索图中的顶点。
  • 实现: 使用队列。
  • 时间复杂度: O(V + E)。

最短路径算法

• Dijkstra算法:

  • 解决单源最短路径问题，即从一个顶点到所有其他顶点的最短路径。
  • 特点: 适用于边权重非负的图。
  • 实现步骤:
    1. 初始化源点的距离为 0，其他顶点的距离为无穷大。
    2. 使用优先队列选择当前距离最小的顶点。
    3. 更新该顶点相邻顶点的最短距离。
    4. 重复直到所有顶点都被处理。
  • 时间复杂度: O(V^2)，使用优先队列优化可降至 O(E + V log V)。

• Bellman-Ford算法:

  • 解决单源最短路径问题，允许边权重为负。
  • 特点: 可以检测负权重环。
  • 实现步骤:
    1. 初始化源点的距离为 0，其他顶点的距离为无穷大。
    2. 进行 V-1 轮松弛操作，更新所有边的最短路径。
    3. 第 V 轮检查是否存在负权重环。
  • 时间复杂度: O(VE)。

最小生成树（MST）算法

• Kruskal算法:

  • 寻找加权无向图的最小生成树。
  • 特点: 基于贪心策略，每次选择权重最小的边，直到构建出最小生成树。
  • 实现步骤:
    1. 将图中的边按权重从小到大排序。
    2. 初始化一个空树，并逐一检查排序后的边，若加入边不会形成环，则将其加入生成树。
    3. 重复直到树中包含所有顶点。
  • 时间复杂度: O(E log E)。

• Prim算法:

  • 寻找加权无向图的最小生成树。
  • 特点: 也是基于贪心策略，从任意顶点出发，每次选择权重最小的连接新顶点的边。
  • 实现步骤:
    1. 从任意顶点开始，将其加入生成树。
    2. 在所有连接生成树的边中选择权重最小的边，并将对应顶点加入生成树。
    3. 重复直到生成树包含所有顶点。
  • 时间复杂度: O(V^2)，使用优先队列优化可降至 O(E + V log V)。

实践

1. 图的基本操作和遍历算法:

   • 实现图的邻接矩阵和邻接表表示方法。
   • 编写DFS和BFS的实现代码，测试图的遍历效果。

2. 最短路径问题:

   • 实现Dijkstra算法，使用该算法求解实际问题，如计算城市间的最短路径。
   • 理解Bellman-Ford算法，并使用其处理可能存在负权重的路径问题。

3. 最小生成树:

   • 使用Kruskal和Prim算法实现最小生成树，应用于网络设计、基础设施规划等实际场景中。

实践代码

1. 图的基本操作和遍历算法

邻接矩阵和邻接表的表示

邻接矩阵表示:

class GraphMatrix {private int[][] adjMatrix;private int numVertices;public GraphMatrix(int numVertices) {this.numVertices = numVertices;adjMatrix = new int[numVertices][numVertices];}public void addEdge(int src, int dest) {adjMatrix[src][dest] = 1;adjMatrix[dest][src] = 1;  // 如果是有向图，这一行可以去掉}public void printMatrix() {for (int i = 0; i < numVertices; i++) {for (int j = 0; j < numVertices; j++) {System.out.print(adjMatrix[i][j] + " ");}System.out.println();}}
}

邻接表表示:

import java.util.LinkedList;class GraphList {private LinkedList<Integer>[] adjList;private int numVertices;public GraphList(int numVertices) {this.numVertices = numVertices;adjList = new LinkedList[numVertices];for (int i = 0; i < numVertices; i++) {adjList[i] = new LinkedList<>();}}public void addEdge(int src, int dest) {adjList[src].add(dest);adjList[dest].add(src);  // 如果是有向图，这一行可以去掉}public void printList() {for (int i = 0; i < numVertices; i++) {System.out.print("Vertex " + i + ":");for (Integer node : adjList[i]) {System.out.print(" -> " + node);}System.out.println();}}
}

DFS 和 BFS 的实现

DFS 实现:

import java.util.*;class DFS {private boolean[] visited;public DFS(int numVertices) {visited = new boolean[numVertices];}public void dfs(int vertex, LinkedList<Integer>[] adjList) {visited[vertex] = true;System.out.print(vertex + " ");for (int adjVertex : adjList[vertex]) {if (!visited[adjVertex]) {dfs(adjVertex, adjList);}}}
}

BFS 实现:

import java.util.*;class BFS {private boolean[] visited;public BFS(int numVertices) {visited = new boolean[numVertices];}public void bfs(int startVertex, LinkedList<Integer>[] adjList) {Queue<Integer> queue = new LinkedList<>();visited[startVertex] = true;queue.add(startVertex);while (!queue.isEmpty()) {int vertex = queue.poll();System.out.print(vertex + " ");for (int adjVertex : adjList[vertex]) {if (!visited[adjVertex]) {visited[adjVertex] = true;queue.add(adjVertex);}}}}
}

测试图的遍历效果

public class Main {public static void main(String[] args) {// 使用邻接表表示图GraphList graph = new GraphList(5);graph.addEdge(0, 1);graph.addEdge(0, 2);graph.addEdge(1, 3);graph.addEdge(1, 4);graph.addEdge(2, 4);System.out.println("邻接表表示:");graph.printList();DFS dfsTraversal = new DFS(5);System.out.print("\nDFS Traversal: ");dfsTraversal.dfs(0, graph.adjList);BFS bfsTraversal = new BFS(5);System.out.print("\nBFS Traversal: ");bfsTraversal.bfs(0, graph.adjList);}
}

2. 最短路径算法

Dijkstra算法实现

import java.util.*;class Dijkstra {private int[] dist;private boolean[] visited;private int numVertices;public Dijkstra(int numVertices) {this.numVertices = numVertices;dist = new int[numVertices];visited = new boolean[numVertices];Arrays.fill(dist, Integer.MAX_VALUE);}public void dijkstra(int[][] graph, int startVertex) {dist[startVertex] = 0;for (int i = 0; i < numVertices; i++) {int u = selectMinVertex();visited[u] = true;for (int v = 0; v < numVertices; v++) {if (!visited[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE&& dist[u] + graph[u][v] < dist[v]) {dist[v] = dist[u] + graph[u][v];}}}printSolution();}private int selectMinVertex() {int minDist = Integer.MAX_VALUE;int vertex = -1;for (int i = 0; i < numVertices; i++) {if (!visited[i] && dist[i] < minDist) {minDist = dist[i];vertex = i;}}return vertex;}private void printSolution() {System.out.println("Vertex\tDistance from Source");for (int i = 0; i < numVertices; i++) {System.out.println(i + "\t\t" + dist[i]);}}
}public class Main {public static void main(String[] args) {int[][] graph = {{0, 10, 0, 5, 0},{0, 0, 1, 2, 0},{0, 0, 0, 0, 4},{0, 3, 9, 0, 2},{7, 0, 6, 0, 0}};Dijkstra dijkstra = new Dijkstra(5);dijkstra.dijkstra(graph, 0); // 从顶点0开始}
}

Bellman-Ford算法实现

class BellmanFord {private int[] dist;private int numVertices;public BellmanFord(int numVertices) {this.numVertices = numVertices;dist = new int[numVertices];Arrays.fill(dist, Integer.MAX_VALUE);}public void bellmanFord(int[][] edges, int startVertex) {dist[startVertex] = 0;for (int i = 0; i < numVertices - 1; i++) {for (int[] edge : edges) {int u = edge[0];int v = edge[1];int weight = edge[2];if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {dist[v] = dist[u] + weight;}}}for (int[] edge : edges) {int u = edge[0];int v = edge[1];int weight = edge[2];if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {System.out.println("图中包含负权重环");return;}}printSolution();}private void printSolution() {System.out.println("Vertex\tDistance from Source");for (int i = 0; i < numVertices; i++) {System.out.println(i + "\t\t" + dist[i]);}}
}public class Main {public static void main(String[] args) {int[][] edges = {{0, 1, -1}, {0, 2, 4},{1, 2, 3}, {1, 3, 2},{1, 4, 2}, {3, 2, 5},{3, 1, 1}, {4, 3, -3}};BellmanFord bellmanFord = new BellmanFord(5);bellmanFord.bellmanFord(edges, 0); // 从顶点0开始}
}

3. 最小生成树

Kruskal算法实现

import java.util.*;class Edge implements Comparable<Edge> {int src, dest, weight;public Edge(int src, int dest, int weight) {this.src = src;this.dest = dest;this.weight = weight;}@Overridepublic int compareTo(Edge other) {return this.weight - other.weight;}
}class Kruskal {private int[] parent;private int numVertices;public Kruskal(int numVertices) {this.numVertices = numVertices;parent = new int[numVertices];for (int i = 0; i < numVertices; i++) {parent[i] = i;}}public void kruskal(List<Edge> edges) {Collections.sort(edges);List<Edge> mst = new ArrayList<>();for (Edge edge : edges) {int srcParent = find(edge.src);int destParent = find(edge.dest);if (srcParent!= destParent) {mst.add(edge);parent[srcParent] = destParent;}}printSolution(mst);}private int find(int vertex) {if (parent[vertex] != vertex) {parent[vertex] = find(parent[vertex]);}return parent[vertex];}private void printSolution(List<Edge> mst) {System.out.println("Edge\tWeight");for (Edge edge : mst) {System.out.println(edge.src + " - " + edge.dest + "\t" + edge.weight);}}
}public class Main {public static void main(String[] args) {List<Edge> edges = new ArrayList<>();edges.add(new Edge(0, 1, 10));edges.add(new Edge(0, 2, 6));edges.add(new Edge(0, 3, 5));edges.add(new Edge(1, 3, 15));edges.add(new Edge(2, 3, 4));Kruskal kruskal = new Kruskal(4);kruskal.kruskal(edges);}
}

Prim算法实现

import java.util.*;class Prim {private int[] key;private boolean[] mstSet;private int[] parent;private int numVertices;public Prim(int numVertices) {this.numVertices = numVertices;key = new int[numVertices];mstSet = new boolean[numVertices];parent = new int[numVertices];Arrays.fill(key, Integer.MAX_VALUE);Arrays.fill(parent, -1);}public void prim(int[][] graph) {key[0] = 0;parent[0] = -1;for (int count = 0; count < numVertices - 1; count++) {int u = selectMinKeyVertex();mstSet[u] = true;for (int v = 0; v < numVertices; v++) {if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {parent[v] = u;key[v] = graph[u][v];}}}printSolution();}private int selectMinKeyVertex() {int minKey = Integer.MAX_VALUE;int vertex = -1;for (int v = 0; v < numVertices; v++) {if (!mstSet[v] && key[v] < minKey) {minKey = key[v];vertex = v;}}return vertex;}private void printSolution() {System.out.println("Edge\tWeight");for (int i = 1; i < numVertices; i++) {System.out.println(parent[i] + " - " + i + "\t" + key[i]);}}
}public class Main {public static void main(String[] args) {int[][] graph = {{0, 2, 0, 6, 0},{2, 0, 3, 8, 5},{0, 3, 0, 0, 7},{6, 8, 0, 0, 9},{0, 5, 7, 9, 0}};Prim prim = new Prim(5);prim.prim(graph);}
}

总结

以上Java代码分别实现了图的邻接矩阵和邻接表表示、DFS和BFS遍历算法、Dijkstra和Bellman-Ford最短路径算法，以及Kruskal和Prim最小生成树算法。