当前位置：首页 > news >正文

从0开始的算法（数据结构和算法）基础（七）

news 来源：原创 2024/9/20 7:14:20

图

       图（graph） 是一种非线性数据结构，由顶点（vertex) 和边 (Edge) 组成。他们之间的相关性没有那么高，链表的线性关系，树状图的派生关系。自由度较高就代表复杂度比较高。
       顶点 (Vertex)：图中的基本单位，通常用来表示对象一个节点
       边 (Edge)：连接两个顶点的线，可以是有向（Directed）或无向（Undirected）。

图论

图论是数学和计算机科学中的一个重要分支，专门研究图的性质和结构。图是一种非线性数据结构，由顶点（也称为节点）和边（连接顶点的线）组成。图论在许多实际应用中扮演着关键角色，如网络设计、社交网络分析和路线规划等。

社交关系：用户之间的朋友关系。
交通网络：城市之间的道路连接。

2. 图的类型

图可以根据不同的特性进行分类：

无向图：边没有方向，两个顶点之间的关系是双向的。例如：A和B是朋友关系。
有向图：边有方向，表示从一个顶点到另一个顶点的单向关系。例如：用户A关注用户B。
加权图：每条边都有一个权重，通常表示成本、距离或时间。
无环图（DAG）：没有回路的图，通常在任务依赖关系中使用。

二、图的表示方法

图的表示方法主要有两种：邻接矩阵和邻接表。

1. 邻接矩阵

邻接矩阵是一个二维数组，其中的元素表示图中顶点之间的连接情况。对于稀疏图会浪费空间。
在图论中，边的添加和删除、顶点的添加和删除是基本的操作。使用邻接矩阵表示图时，这些操作的时间复杂度和具体实现方法如下：

（1）邻接矩阵的结构

假设我们有一个图，使用邻接矩阵 adjMat 来表示。该矩阵的大小为 ( V \times V )，其中 ( V ) 是图中顶点的数量。矩阵的元素 adjMat[i][j] 表示从顶点 ( i ) 到顶点 ( j ) 的边的权重（若无边则为0或无穷大）。

（2）添加/删除边

添加边：在邻接矩阵中修改指定的边，只需更新 adjMat[i][j] 和 adjMat[j][i]。时间复杂度为 ( O(1) )。

// 添加边
void addEdge(int[][] adjMat, int u, int v, int weight) {adjMat[u][v] = weight;adjMat[v][u] = weight; // 无向图
}

删除边：同样，只需将 adjMat[i][j] 和 adjMat[j][i] 设为无穷大（或0）。时间复杂度为 ( O(1) )。

// 删除边
void removeEdge(int[][] adjMat, int u, int v) {adjMat[u][v] = Integer.MAX_VALUE; // 或0adjMat[v][u] = Integer.MAX_VALUE; // 无向图
}

（3)添加顶点

添加顶点：在邻接矩阵的尾部添加一行一列，并将所有新元素初始化为无穷大（或0）。时间复杂度为 ( O(V²) )。

// 添加顶点
int[][] addVertex(int[][] adjMat, int V) {int[][] newAdjMat = new int[V + 1][V + 1];for (int i = 0; i < V; i++) {for (int j = 0; j < V; j++) {newAdjMat[i][j] = adjMat[i][j];}}// 初始化新行和新列for (int i = 0; i < V + 1; i++) {newAdjMat[V][i] = Integer.MAX_VALUE; // 或0newAdjMat[i][V] = Integer.MAX_VALUE; // 或0}return newAdjMat;
}

（4）删除顶点

删除顶点：在邻接矩阵中删除一行和一列。若删除的是首行首列，需要将其他元素向左上移动。时间复杂度为 ( O(V^2) )。

// 删除顶点
int[][] removeVertex(int[][] adjMat, int V, int vertex) {int[][] newAdjMat = new int[V - 1][V - 1];int newRow = 0, newCol;for (int i = 0; i < V; i++) {if (i == vertex) continue; // 跳过删除的顶点newCol = 0;for (int j = 0; j < V; j++) {if (j == vertex) continue; // 跳过删除的顶点newAdjMat[newRow][newCol] = adjMat[i][j];newCol++;}newRow++;}return newAdjMat;
}

（5）初始化

初始化：传入 ( V ) 个顶点，初始化长度为 ( V ) 的顶点列表 vertices，使用 ( O(V) ) 时间；初始化大小为 ( V \times V ) 的邻接矩阵 adjMat，使用 ( O(V^2) ) 时间。

// 初始化
int[][] initializeGraph(int V) {int[][] adjMat = new int[V][V];for (int i = 0; i < V; i++) {for (int j = 0; j < V; j++) {if (i == j) {adjMat[i][j] = 0; // 自环权重为0} else {adjMat[i][j] = Integer.MAX_VALUE; // 或0}}}return adjMat;
}

2. 邻接表

邻接表为每个顶点维护一个列表，列出与其直接相连的顶点。对于大型稀疏图，这种表示方法更加节省空间。

三、图的基本算法

1. 深度优先搜索（DFS）

深度优先搜索是一种用于遍历或搜索图的算法。它从某个顶点开始，尽可能深入到每个分支，然后回溯。

Java实现：

import java.util.*;class Graph {private Map<String, List<String>> graph;public Graph() {graph = new HashMap<>();}public void addEdge(String u, String v) {graph.putIfAbsent(u, new ArrayList<>());graph.putIfAbsent(v, new ArrayList<>());graph.get(u).add(v);graph.get(v).add(u);  // 无向图}public void dfs(String start) {Set<String> visited = new HashSet<>();dfsHelper(start, visited);}private void dfsHelper(String vertex, Set<String> visited) {visited.add(vertex);System.out.print(vertex + " ");for (String neighbor : graph.get(vertex)) {if (!visited.contains(neighbor)) {dfsHelper(neighbor, visited);}}}
}// 使用示例
public class Main {public static void main(String[] args) {Graph g = new Graph();g.addEdge("A", "B");g.addEdge("A", "C");g.addEdge("B", "D");g.addEdge("C", "D");System.out.println("DFS Traversal:");g.dfs("A");}
}

2. 广度优先搜索（BFS）

广度优先搜索是一种图的遍历方法，从某个顶点开始，逐层访问其邻接顶点。

Java实现：

import java.util.*;class Graph {private Map<String, List<String>> graph;public Graph() {graph = new HashMap<>();}public void addEdge(String u, String v) {graph.putIfAbsent(u, new ArrayList<>());graph.putIfAbsent(v, new ArrayList<>());graph.get(u).add(v);graph.get(v).add(u);  // 无向图}public void bfs(String start) {Set<String> visited = new HashSet<>();Queue<String> queue = new LinkedList<>();visited.add(start);queue.add(start);while (!queue.isEmpty()) {String vertex = queue.poll();System.out.print(vertex + " ");for (String neighbor : graph.get(vertex)) {if (!visited.contains(neighbor)) {visited.add(neighbor);queue.add(neighbor);}}}}
}// 使用示例
public class Main {public static void main(String[] args) {Graph g = new Graph();g.addEdge("A", "B");g.addEdge("A", "C");g.addEdge("B", "D");g.addEdge("C", "D");System.out.println("\nBFS Traversal:");g.bfs("A");}
}

3. Dijkstra算法

Dijkstra算法用于加权图，找到从源顶点到其他顶点的最短路径。

Java实现：

import java.util.*;class Graph {private Map<String, Map<String, Integer>> graph;public Graph() {graph = new HashMap<>();}public void addEdge(String u, String v, int weight) {graph.putIfAbsent(u, new HashMap<>());graph.putIfAbsent(v, new HashMap<>());graph.get(u).put(v, weight);graph.get(v).put(u, weight);  // 无向图}public Map<String, Integer> dijkstra(String start) {Map<String, Integer> distances = new HashMap<>();PriorityQueue<Node> minHeap = new PriorityQueue<>(Comparator.comparingInt(node -> node.distance));for (String vertex : graph.keySet()) {distances.put(vertex, Integer.MAX_VALUE);}distances.put(start, 0);minHeap.add(new Node(start, 0));while (!minHeap.isEmpty()) {Node current = minHeap.poll();for (Map.Entry<String, Integer> entry : graph.get(current.vertex).entrySet()) {String neighbor = entry.getKey();int weight = entry.getValue();int distance = current.distance + weight;if (distance < distances.get(neighbor)) {distances.put(neighbor, distance);minHeap.add(new Node(neighbor, distance));}}}return distances;}private static class Node {String vertex;int distance;Node(String vertex, int distance) {this.vertex = vertex;this.distance = distance;}}
}// 使用示例
public class Main {public static void main(String[] args) {Graph g = new Graph();g.addEdge("A", "B", 1);g.addEdge("A", "C", 4);g.addEdge("B", "C", 2);g.addEdge("B", "D", 5);g.addEdge("C", "D", 1);Map<String, Integer> result = g.dijkstra("A");System.out.println("\nDijkstra's shortest path from A:");for (Map.Entry<String, Integer> entry : result.entrySet()) {System.out.println("Distance to " + entry.getKey() + ": " + entry.getValue());}}
}

4. Kruskal算法

Kruskal算法用于求解最小生成树。

Java实现：

import java.util.*;class UnionFind {private Map<String, String> parent = new HashMap<>();private Map<String, Integer> rank = new HashMap<>();public void add(String u) {parent.put(u, u);rank.put(u, 0);}public String find(String u) {if (!u.equals(parent.get(u))) {parent.put(u, find(parent.get(u)));  // 路径压缩}return parent.get(u);}public void union(String u, String v) {String rootU = find(u);String rootV = find(v);if (!rootU.equals(rootV)) {if (rank.get(rootU) > rank.get(rootV)) {parent.put(rootV, rootU);} else if (rank.get(rootU) < rank.get(rootV)) {parent.put(rootU, rootV);} else {parent.put(rootV, rootU);rank.put(rootU, rank.get(rootU) + 1);}}}
}class Graph {private List<Edge> edges = new ArrayList<>();public void addEdge(String u, String v, int weight) {edges.add(new Edge(u, v, weight));}public List<Edge> kruskal() {edges.sort(Comparator.comparingInt(edge -> edge.weight));UnionFind uf = new UnionFind();List<Edge> mst = new ArrayList<>();for (Edge edge : edges) {uf.add(edge.u);uf.add(edge.v);}for (Edge edge : edges) {if (uf.find(edge.u) != uf.find(edge.v)) {uf.union(edge.u, edge.v);mst.add(edge);}}return mst;}private static class Edge {String u;String v;int weight;Edge(String u, String v, int weight) {this.u = u;this.v = v;this.weight = weight;}}
}// 使用示例
public class Main {public static void main(String[] args) {Graph g = new Graph();g.addEdge("A", "B", 1);g.addEdge("A", "C", 3);g.addEdge("B", "C", 1);g.addEdge("B", "D", 4);g.addEdge("C", "D", 1);List<Graph.Edge> mst = g.kruskal();System.out.println("\nKruskal's Minimum Spanning Tree:");for (Graph.Edge edge : mst) {System.out.println(edge.u + " -- " + edge.v + " == " + edge.weight);}}
}