数据结构第14节 加权图

加权图是在图论中一种更为复杂的图结构，它扩展了无向图和有向图的概念，通过给图中的边附加一个数值来表示边的某种属性，如成本、距离、容量或相似度等。这个数值被称为边的“权重”。

定义

加权图可以被形式化地定义为一个三元组 ( G = (V, E, W) )，其中：

• ( V ) 是顶点的集合。
• ( E ) 是边的集合，每条边连接 ( V ) 中的一对顶点。
• ( W ) 是一个函数，将每条边映射到一个实数上，即 ( W: E \rightarrow \mathbb{R} )。

分类

加权图可以根据边的方向进一步分类为：

• 加权无向图：图中的边没有方向，权重是对称的，即 ( W(u,v) = W(v,u) )。
• 加权有向图：图中的边有方向，权重可能不对称，即 ( W(u,v) ) 可能与 ( W(v,u) ) 不同。

权重的意义

在不同的应用场景中，权重可以有不同的含义：

• 在网络路由中，权重可能是网络链路的延迟或带宽。
• 在交通网络中，权重可能是道路的距离或通行时间。
• 在电子电路中，权重可能是电阻或电容值。
• 在社交网络中，权重可以表示人际关系的强度。

图的表示

加权图可以通过以下几种方式表示：

• 邻接矩阵：对于加权图，邻接矩阵中的非零元素表示边的权重。
• 邻接列表：对于每个顶点，列表中的每个元素除了包含邻接顶点的信息外，还包含边的权重。

常见算法

处理加权图的一些常见算法包括：

• 最短路径算法：如Dijkstra算法和Bellman-Ford算法，用于找到两点间具有最小权重和的路径。
• 最小生成树算法：如Prim算法和Kruskal算法，用于在加权连通图中找到一棵包含所有顶点的最小权重的树。
• 最大流算法：如Ford-Fulkerson算法，用于在有向加权图中找到从源点到汇点的最大流。
• 匹配算法：如匈牙利算法，用于在加权二部图中找到最优匹配。

实际应用

加权图在多个领域有着广泛的应用，包括：

• 物流和运输系统：规划最短路线或最低成本的配送路径。
• 网络通信：优化数据包的传输路径，以减少延迟或提高效率。
• 生物信息学：构建基因或蛋白质网络，分析其相互作用。
• 机器学习：构建基于图的模型，如图神经网络，用于预测和分类任务。

加权图是理解和建模现实世界中复杂关系的重要工具，其研究不仅限于理论数学，也与计算机科学、工程学、经济学和生物学等领域密切相关。

为了更深入理解加权图，我们可以考虑一个具体案例：在一个城市交通网络中寻找两点之间的最短路径。在这个网络中，边的权重代表两个地点之间的行驶时间（或者距离）。我们将使用Dijkstra算法来解决这个问题，该算法是一种用于查找加权图中单源最短路径的经典算法。

背景

假设我们有一个城市，其中有若干个地点和连接它们的道路。每个地点都是图中的一个顶点，而每条道路则是一条有向或无向的边，且每条边都有一个权重，代表驾驶所需的时间。我们的目标是从某个起点出发，找到到达另一个终点的最短路径。

Java源代码实现

首先，我们需要定义加权图的数据结构，然后实现Dijkstra算法。以下是一个简化版的实现：

import java.util.*;class Edge {int dest;int weight;public Edge(int d, int w) {dest = d;weight = w;}
}class Node {List<Edge> neighbors = new ArrayList<>();boolean visited = false;int distance = Integer.MAX_VALUE;Node previous = null;
}public class DijkstraAlgorithm {private List<Node> nodes = new ArrayList<>();public void addNode() {nodes.add(new Node());}public void addEdge(int source, int destination, int weight) {Node srcNode = nodes.get(source);Node destNode = nodes.get(destination);srcNode.neighbors.add(new Edge(destNode, weight));}public void dijkstra(int startNode) {PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingInt(node -> node.distance));Node start = nodes.get(startNode);start.distance = 0;queue.add(start);while (!queue.isEmpty()) {Node current = queue.poll();if (current.visited)continue;for (Edge edge : current.neighbors) {Node neighbor = edge.dest;int tentativeDistance = current.distance + edge.weight;if (tentativeDistance < neighbor.distance) {neighbor.distance = tentativeDistance;neighbor.previous = current;queue.add(neighbor);}}current.visited = true;}}public List<Integer> getPath(int destination) {List<Integer> path = new ArrayList<>();Node current = nodes.get(destination);while (current != null) {path.add(current.hashCode());current = current.previous;}Collections.reverse(path);return path;}public static void main(String[] args) {DijkstraAlgorithm graph = new DijkstraAlgorithm();// 添加节点for (int i = 0; i < 6; i++)graph.addNode();// 添加边graph.addEdge(0, 1, 5);graph.addEdge(0, 2, 3);graph.addEdge(1, 3, 6);graph.addEdge(1, 2, 2);graph.addEdge(2, 4, 4);graph.addEdge(2, 5, 2);graph.addEdge(3, 4, -2); // 负权重边，但Dijkstra不处理负权重环graph.addEdge(4, 5, 1);// 执行Dijkstra算法graph.dijkstra(0);// 输出最短路径System.out.println("Shortest Path to all nodes from node 0:");for (int i = 0; i < graph.nodes.size(); i++) {System.out.println("To node " + i + ": " + graph.getPath(i));}}
}

解析

1. Edge 类定义了边的目的地和权重。
2. Node 类定义了顶点的邻居列表、是否访问过、当前距离和前驱节点。
3. DijkstraAlgorithm 类实现了加权图的添加节点和边的功能，以及Dijkstra算法的执行。
4. 主方法中创建图、添加节点和边，执行Dijkstra算法并打印出从起始点到所有其他点的最短路径。

这个Demo展示了如何使用Java实现加权图以及Dijkstra算法的基本框架，实际应用中可能需要根据具体需求进行调整和优化。例如，处理大规模图时，可能需要更高效的数据结构和算法优化，如使用Fibonacci堆代替优先队列。

Demo展示

1. 迷宫游戏：寻找出口

在迷宫游戏中，玩家需要从起点出发，找到通往终点的路径。这可以通过图论中的搜索算法来实现，例如深度优先搜索（DFS）或广度优先搜索（BFS）。

Java代码示例：使用DFS寻找迷宫出口

import java.util.*;public class MazeGame {private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};private char[][] maze;private boolean[][] visited;public MazeGame(char[][] maze) {this.maze = maze;this.visited = new boolean[maze.length][maze[0].length];}private boolean dfs(int x, int y) {if (x < 0 || x >= maze.length || y < 0 || y >= maze[0].length || maze[x][y] == '#' || visited[x][y]) {return false;}if (maze[x][y] == 'E') {return true;}visited[x][y] = true;for (int[] dir : DIRECTIONS) {if (dfs(x + dir[0], y + dir[1])) {return true;}}return false;}public boolean hasPath() {for (int i = 0; i < maze.length; i++) {for (int j = 0; j < maze[0].length; j++) {if (maze[i][j] == 'S') {return dfs(i, j);}}}return false;}public static void main(String[] args) {char[][] maze = {{'#', '#', '#', '#', 'S', '#', '#'},{'#', '.', '.', '.', '.', '.', '#'},{'#', '#', '#', '#', '#', '.', '#'},{'#', '.', '.', '.', '.', '.', '#'},{'#', '#', '#', '#', '#', 'E', '#'}};MazeGame game = new MazeGame(maze);System.out.println(game.hasPath() ? "There is a path." : "There is no path.");}
}

2. 策略游戏：资源收集与管理

在策略游戏中，玩家需要收集资源、建设设施，并管理资源分配。这可以通过构建加权图，其中节点代表资源点或设施，边的权重代表资源的流动成本或收益。

Java代码示例：资源管理加权图

import java.util.*;public class ResourceManagementGame {private Map<String, List<Pair<String, Integer>>> graph = new HashMap<>();public void addNode(String name) {graph.putIfAbsent(name, new ArrayList<>());}public void addEdge(String source, String target, int weight) {graph.get(source).add(new Pair<>(target, weight));}public int calculateTotalResources(String start, int resources) {Set<String> visited = new HashSet<>();Queue<Pair<String, Integer>> queue = new LinkedList<>();queue.add(new Pair<>(start, resources));while (!queue.isEmpty()) {Pair<String, Integer> current = queue.poll();String node = current.getKey();int resource = current.getValue();if (visited.contains(node)) continue;visited.add(node);resource += processNode(node);for (Pair<String, Integer> next : graph.get(node)) {queue.add(new Pair<>(next.getKey(), resource - next.getValue()));}}return resources;}private int processNode(String node) {// Simulate resource processing at each nodereturn node.equals("mine") ? 10 : 0;}public static void main(String[] args) {ResourceManagementGame game = new ResourceManagementGame();game.addNode("mine");game.addNode("factory");game.addNode("warehouse");game.addEdge("mine", "factory", 2);game.addEdge("factory", "warehouse", 3);game.addEdge("warehouse", "mine", 1);System.out.println("Total resources: " + game.calculateTotalResources("mine", 100));}
}class Pair<K, V> {private K key;private V value;public Pair(K key, V value) {this.key = key;this.value = value;}public K getKey() {return key;}public V getValue() {return value;}
}

3. 棋盘游戏：策略与移动

在棋盘游戏中，玩家需要在棋盘上移动棋子以达成胜利条件。棋盘上的每个位置可以视为图中的一个节点，而合法的移动则构成边。

Java代码示例：国际象棋中的骑士走法

import java.util.*;public class ChessKnightMoves {private static final int[][] MOVES = {{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}};public int minMoves(int startX, int startY, int endX, int endY) {int[][] board = new int[8][8];Queue<int[]> queue = new LinkedList<>();queue.add(new int[]{startX, startY});board[startX][startY] = 1;while (!queue.isEmpty()) {int[] pos = queue.poll();if (pos[0] == endX && pos[1] == endY) {return board[pos[0]][pos[1]] - 1;}for (int[] move : MOVES) {int newX = pos[0] + move[0];int newY = pos[1] + move[1];if (newX >= 0 && newX < 8 && newY >= 0 && newY < 8 && board[newX][newY] == 0) {queue.add(new int[]{newX, newY});board[newX][newY] = board[pos[0]][pos[1]] + 1;}}}return -1;}public static void main(String[] args) {ChessKnightMoves game = new ChessKnightMoves();System.out.println("Minimum moves: " + game.minMoves(0, 0, 7, 7));}
}