赞
踩
加权图是在图论中一种更为复杂的图结构,它扩展了无向图和有向图的概念,通过给图中的边附加一个数值来表示边的某种属性,如成本、距离、容量或相似度等。这个数值被称为边的“权重”。
加权图可以被形式化地定义为一个三元组 ( G = (V, E, W) ),其中:
加权图可以根据边的方向进一步分类为:
在不同的应用场景中,权重可以有不同的含义:
加权图可以通过以下几种方式表示:
处理加权图的一些常见算法包括:
加权图在多个领域有着广泛的应用,包括:
加权图是理解和建模现实世界中复杂关系的重要工具,其研究不仅限于理论数学,也与计算机科学、工程学、经济学和生物学等领域密切相关。
为了更深入理解加权图,我们可以考虑一个具体案例:在一个城市交通网络中寻找两点之间的最短路径。在这个网络中,边的权重代表两个地点之间的行驶时间(或者距离)。我们将使用Dijkstra算法来解决这个问题,该算法是一种用于查找加权图中单源最短路径的经典算法。
假设我们有一个城市,其中有若干个地点和连接它们的道路。每个地点都是图中的一个顶点,而每条道路则是一条有向或无向的边,且每条边都有一个权重,代表驾驶所需的时间。我们的目标是从某个起点出发,找到到达另一个终点的最短路径。
首先,我们需要定义加权图的数据结构,然后实现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算法的执行。这个Demo展示了如何使用Java实现加权图以及Dijkstra算法的基本框架,实际应用中可能需要根据具体需求进行调整和优化。例如,处理大规模图时,可能需要更高效的数据结构和算法优化,如使用Fibonacci堆代替优先队列。
Demo展示
在迷宫游戏中,玩家需要从起点出发,找到通往终点的路径。这可以通过图论中的搜索算法来实现,例如深度优先搜索(DFS)或广度优先搜索(BFS)。
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."); } }
在策略游戏中,玩家需要收集资源、建设设施,并管理资源分配。这可以通过构建加权图,其中节点代表资源点或设施,边的权重代表资源的流动成本或收益。
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; } }
在棋盘游戏中,玩家需要在棋盘上移动棋子以达成胜利条件。棋盘上的每个位置可以视为图中的一个节点,而合法的移动则构成边。
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)); } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。