加權圖是在圖論中一種更為復雜的圖結構，它擴展了無向圖和有向圖的概念，通過給圖中的邊附加一個數值來表示邊的某種屬性，如成本、距離、容量或相似度等。這個數值被稱為邊的“權重”。

定義

加權圖可以被形式化地定義為一個三元組 ( 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));}
}