数据结构第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算法。以下是一个简化版的实现：

java">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寻找迷宫出口
java">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代码示例：资源管理加权图
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代码示例：国际象棋中的骑士走法
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));
    }
}

http://www.niftyadmin.cn/n/5543025.html

相关文章

240707_昇思学习打卡-Day19-基于MindSpore通过GPT实现情感分类

240707_昇思学习打卡-Day19-基于MindSpore通过GPT实现情感分类

240707_昇思学习打卡-Day19-基于MindSpore通过GPT实现情感分类 今天基于GPT实现一个情感分类的功能&#xff0c;假设已经安装好了MindSpore环境。 # 该案例在 mindnlp 0.3.1 版本完成适配&#xff0c;如果发现案例跑不通&#xff0c;可以指定mindnlp版本&#xff0c;执行!pip…
阅读更多...
[数据结构] 归并排序快速排序 及非递归实现

[数据结构] 归并排序快速排序 及非递归实现

&#xff08;&#xff09;标题&#xff1a;[数据结构] 归并排序&&快速排序 及非递归实现 水墨不写bug &#xff08;图片来源于网络&#xff09; 目录 (一)快速排序 类比递归谋划非递归 快速排序的非递归实现&#xff1a; &#xff08;二&#xff09;归并排序 归…
阅读更多...
一.7.(2)基本运算电路，包括比例运算电路、加减运算电路、积分运算电路、微分电路等常见电路的分析、计算及应用；(未完待续)

一.7.(2)基本运算电路，包括比例运算电路、加减运算电路、积分运算电路、微分电路等常见电路的分析、计算及应用；(未完待续)

what id the 虚短虚断虚地? 虚短&#xff1a;运放的正相输入端和反相输入端貌似连在一起了&#xff0c;所以两端的电压相等&#xff0c;即UU- 虚断&#xff1a;输入端输入阻抗无穷大 虚地&#xff1a;运放正相输入端接地&#xff0c;导致U&#xff1d;U-&#xff1d;0。 虚…
阅读更多...
vue3【提效】使用 VueUse 高效开发（工具库 @vueuse/core + 新增的组件库 @vueuse/components）

vue3【提效】使用 VueUse 高效开发（工具库 @vueuse/core + 新增的组件库 @vueuse/components）

Vueuse 是一个功能强大的 Vue.js 生态系统工具库&#xff0c;提供了可重用的组件和函数&#xff0c;帮助开发者更轻松地构建复杂的应用程序。 官网 &#xff1a;https://vueuse.org/core/useWindowScroll/ 安装 VueUse npm i vueuse/core vueuse/components&#xff08;可选&a…
阅读更多...
搭建论坛和mysql数据库安装和php安装

搭建论坛和mysql数据库安装和php安装

目录 概念 步骤 安装mysql8.0.30 安装php 安装Discuz 概念 搭建论坛的架构&#xff1a; lnmpDISCUZ l 表示linux操作系统 n 表示nginx前端页面的web服务 m 表示 mysql 数据库 用来保存用户和密码以及论坛的相关内容 p 表示php 动态请求转发的中间件 步骤 &#xff…
阅读更多...
Matlab 中 fftshift 与 ifftshift

Matlab 中 fftshift 与 ifftshift

文章目录 【 1. fftshift、ifftshift 的区别】【 2. fftshift(fft(A)) 作图 】【 3. fftshift(fft(A)) 还原到 A 】Matlab 直接对信号进行 FFT 的结果中，前半部分是正频，后半部分是负频，为了更直观的表示，需要将 负频 部分移到 前面。【 1. fftshift、ifftshift 的区别】 M…
阅读更多...
Upload-Labs靶场闯关

Upload-Labs靶场闯关

文章目录 Pass-01Pass-02Pass-03Pass-04Pass-05Pass-06Pass-07Pass-08Pass-09Pass-10Pass-11Pass-12Pass-13Pass-14Pass-15Pass-16Pass-17Pass-18Pass-19Pass-20 以下是文件上传绕过的各种思路&#xff0c;不过是鄙人做题记下来的一些思路笔记罢了。 GitHub靶场环境下载&#x…
阅读更多...
【Android】自定义换肤框架01之皮肤包制作

【Android】自定义换肤框架01之皮肤包制作

前言 目前为止&#xff0c;市面上主流的安卓换肤方案&#xff0c;其实原理都是差不多的 虽然大多都号称一行代码集成&#xff0c;但其实想要做到完全适配&#xff0c;并不简单 这个系列&#xff0c;就是让大家从零开始&#xff0c;完全掌握这方面知识&#xff0c;这样才能对…
阅读更多...
最新文章

Copyright @ 2022~2023