加权图是在图论中一种更为复杂的图结构，它扩展了无向图和有向图的概念，通过给图中的边附加一个数值来表示边的某种属性，如成本、距离、容量或相似度等。这个数值被称为边的“权重”。
定义
加权图可以被形式化地定义为一个三元组 ( 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));
}
}
}
解析
Edge类定义了边的目的地和权重。Node类定义了顶点的邻居列表、是否访问过、当前距离和前驱节点。DijkstraAlgorithm类实现了加权图的添加节点和边的功能，以及Dijkstra算法的执行。- 主方法中创建图、添加节点和边，执行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 node
return 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));
}
}
