数据结构第12节 有向图

有向图（Directed Graph 或 Digraph）是一种图数据结构，其中的边具有方向性。这意味着在一个有向图中，边可以被视为箭头，箭头从一个顶点指向另一个顶点，表示从起点到终点的单向关系。有向图的这种特性使得它在许多现实问题的建模中非常有用，例如网络流分析、计算机网络、基因调控网络、网页链接结构等。

有向图的基本概念：

1. 顶点（Vertex）：有向图中的基本单元，可以表示实体或状态。
2. 边（Edge）或弧（Arc）：连接两个顶点的有向线段，表示从一个顶点到另一个顶点的关系。边由一对顶点组成，通常写作 <u, v> 或 (u, v)，其中 u 是边的起点（尾部）而 v 是终点（头部）。
3. 邻接：如果存在一条从顶点 u 指向顶点 v 的边，则称 v 是 u 的邻接顶点，同时 u 是 v 的前驱顶点。
4. 出度（Out-degree）：一个顶点的出度是所有以该顶点为起点的边的数量。
5. 入度（In-degree）：一个顶点的入度是所有以该顶点为终点的边的数量。
6. 路径：在有向图中，从顶点 u 到顶点 v 的路径是由一系列顶点组成的序列 u, v1, v2, …, v，其中每对连续顶点之间都存在一条指向序列前进方向的边。
7. 环（Cycle）：如果存在一条路径从顶点 u 开始，经过一系列顶点后又回到顶点 u，则称有向图中存在环。
8. 强连通图：如果一个有向图中任意两个顶点都可以相互到达，则称这个有向图为强连通的。
9. 有向无环图（DAG）：如果一个有向图中不存在环，则称这个有向图为有向无环图。

有向图的表示：

1. 邻接矩阵：一个二维数组，其中 adj[u][v] 表示是否存在从顶点 u 到顶点 v 的边。对于有向图，邻接矩阵通常不是对称的。
2. 邻接表：对于每个顶点，邻接表是一个链表或数组，其中包含所有与该顶点直接相连的顶点。邻接表对于稀疏图（边的数量远小于顶点数量的平方）更节省空间。

有向图的应用算法：

1. 拓扑排序：在有向无环图（DAG）中，对顶点进行排序，使得对于每条边 (u, v)，顶点 u 在排序中出现在顶点 v 之前。
2. 最短路径算法：例如 Dijkstra 算法和 Bellman-Ford 算法，用于寻找图中两点间最短路径。
3. 强连通分量算法：例如 Kosaraju’s 算法和 Tarjan’s 算法，用于识别有向图中的强连通分量。
4. 流网络算法：例如 Ford-Fulkerson 算法，用于求解网络的最大流问题。

有向图在计算机科学和其他领域中有广泛的应用，掌握其基本概念和相关算法对于解决实际问题是至关重要的。

有向图在游戏开发中扮演着重要的角色，特别是在涉及路径寻找、任务规划、NPC行为、游戏地图生成等方面。有向图是由顶点（节点）和边组成的数据结构，其中边是有方向的，这意味着从一个顶点到另一个顶点的路径可能与反方向的路径不同。

在Java中，我们可以使用邻接表或者邻接矩阵的方式来表示有向图。下面我将使用邻接表的方式，结合一个简单的游戏场景来讲解有向图的应用。

游戏场景描述

想象一下，你正在开发一个角色扮演游戏，游戏中有一个由村庄、森林、山脉、城堡等组成的大陆。玩家可以从村庄出发，探索这个世界，完成各种任务。我们的目标是使用有向图来表示游戏世界中的各个地点以及它们之间的连接关系。

Java实现

import java.util.*;

public class GameWorld {
    private Map<String, List<String>> graph;

    public GameWorld() {
        graph = new HashMap<>();
    }

    // 添加地点
    public void addLocation(String location) {
        graph.put(location, new ArrayList<>());
    }

    // 添加边，即两个地点之间的连接
    public void addConnection(String from, String to) {
        List<String> connections = graph.get(from);
        if (!connections.contains(to)) {
            connections.add(to);
        }
    }

    // 获取地点的所有可前往的地点
    public List<String> getConnections(String location) {
        return graph.get(location);
    }

    // 深度优先遍历示例，可以用于探索游戏世界
    public void dfs(String start) {
        Set<String> visited = new HashSet<>();
        dfsHelper(start, visited);
    }

    private void dfsHelper(String current, Set<String> visited) {
        System.out.println("Visited " + current);
        visited.add(current);

        for (String neighbor : graph.get(current)) {
            if (!visited.contains(neighbor)) {
                dfsHelper(neighbor, visited);
            }
        }
    }

    // 测试代码
    public static void main(String[] args) {
        GameWorld world = new GameWorld();
        world.addLocation("Village");
        world.addLocation("Forest");
        world.addLocation("Mountain");
        world.addLocation("Castle");

        world.addConnection("Village", "Forest");
        world.addConnection("Forest", "Mountain");
        world.addConnection("Mountain", "Castle");
        world.addConnection("Castle", "Village");

        world.dfs("Village");
    }
}

游戏应用实例

在这个游戏中，我们创建了一个有向图表示游戏世界。我们首先添加了四个地点：“Village”、“Forest”、“Mountain”和“Castle”。然后，我们添加了连接，表示从一个地点到另一个地点的路径。最后，我们使用深度优先搜索算法来遍历整个游戏世界，模拟玩家的探索过程。

通过这种方式，我们可以在游戏中实现复杂的路径寻找和任务规划。例如，我们可以使用图算法来确定从一个地点到另一个地点的最短路径，或者规划一系列任务的最优顺序。有向图为我们提供了一种强大的工具，可以用来表示和处理游戏世界中的复杂关系。

为了进一步扩展游戏并深入利用有向图的概念，我们可以添加更多的功能，比如：

1. 双向边：允许玩家从一个地点往返另一个地点。
2. 边的权重：代表移动到下一个地点所需的时间或消耗的能量。
3. 动态变化的图：游戏世界中的某些路径可能因为天气、时间或其他因素而暂时不可用。
4. 任务系统：基于图的连通性，设计任务流程和奖励机制。

接下来，我们将通过更新之前的代码来实现这些功能。

import java.util.*;

public class GameWorld {
    private Map<String, List<Edge>> graph;
    
    public GameWorld() {
        graph = new HashMap<>();
    }
    
    public void addLocation(String location) {
        graph.put(location, new ArrayList<>());
    }
    
    public void addConnection(String from, String to, int weight) {
        Edge edge = new Edge(to, weight);
        List<Edge> connections = graph.get(from);
        if (!connections.contains(edge)) {
            connections.add(edge);
        }
    }
    
    public List<Edge> getConnections(String location) {
        return graph.get(location);
    }
    
    public void dfs(String start) {
        Set<String> visited = new HashSet<>();
        dfsHelper(start, visited);
    }
    
    private void dfsHelper(String current, Set<String> visited) {
        System.out.println("Visited " + current);
        visited.add(current);
        
        for (Edge edge : graph.get(current)) {
            if (!visited.contains(edge.to)) {
                dfsHelper(edge.to, visited);
            }
        }
    }
    
    // 新增方法：获取到达目的地的总权重
    public int getTotalWeight(String start, String end) {
        return getTotalWeightHelper(start, end, 0, new HashSet<>());
    }
    
    private int getTotalWeightHelper(String current, String end, int weight, Set<String> visited) {
        if (current.equals(end)) {
            return weight;
        }
        visited.add(current);
        int minWeight = Integer.MAX_VALUE;
        for (Edge edge : graph.get(current)) {
            if (!visited.contains(edge.to)) {
                int newWeight = getTotalWeightHelper(edge.to, end, weight + edge.weight, visited);
                if (newWeight != Integer.MAX_VALUE) {
                    minWeight = Math.min(minWeight, newWeight);
                }
            }
        }
        visited.remove(current);
        return minWeight;
    }
    
    // 边类
    private static class Edge {
        String to;
        int weight;
        
        Edge(String to, int weight) {
            this.to = to;
            this.weight = weight;
        }
        
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Edge edge = (Edge) o;
            return weight == edge.weight && Objects.equals(to, edge.to);
        }
        
        @Override
        public int hashCode() {
            return Objects.hash(to, weight);
        }
    }
    
    // 测试代码
    public static void main(String[] args) {
        GameWorld world = new GameWorld();
        world.addLocation("Village");
        world.addLocation("Forest");
        world.addLocation("Mountain");
        world.addLocation("Castle");
        world.addLocation("Lake");
        
        world.addConnection("Village", "Forest", 2);
        world.addConnection("Forest", "Mountain", 3);
        world.addConnection("Mountain", "Castle", 4);
        world.addConnection("Castle", "Village", 5);
        world.addConnection("Village", "Lake", 1);
        
        world.dfs("Village");
        System.out.println("Total Weight from Village to Castle: " + world.getTotalWeight("Village", "Castle"));
    }
}

扩展说明

在这个扩展版本中，我们增加了Edge类来表示带权重的边，这允许我们计算从一个地点到另一个地点的总消耗。我们还添加了一个getTotalWeight方法，它使用递归深度优先搜索来找到从起点到终点的最短路径，并返回这条路径上的总权重。

通过这种方式，我们可以为游戏增加更多真实感和策略性，例如，玩家需要权衡时间成本和资源消耗，选择最佳的旅行路线。此外，我们还可以在此基础上添加更多复杂的功能，如动态障碍物、动态边权重（例如，随天气变化的路径难度），以及更高级的任务和奖励系统。

这种设计不仅增强了游戏的可玩性和沉浸感，同时也展示了有向图在游戏开发中的强大应用潜力。通过不断迭代和改进，我们能够构建出更加丰富和多变的游戏世界。

为了进一步扩展这个游戏，我们可以考虑引入更复杂的元素，如角色状态、动态事件、NPC交互和物品系统。以下是针对这些新增功能的代码实现：

import java.util.*;

public class GameWorld {
    private Map<String, List<Edge>> graph;
    private Map<String, Location> locations;
    private Player player;

    public GameWorld() {
        graph = new HashMap<>();
        locations = new HashMap<>();
        player = new Player();
    }

    public void addLocation(String name, String description) {
        Location location = new Location(name, description);
        locations.put(name, location);
        graph.put(name, new ArrayList<>());
    }

    public void addConnection(String from, String to, int distance) {
        Edge edge = new Edge(to, distance);
        List<Edge> connections = graph.get(from);
        if (!connections.contains(edge)) {
            connections.add(edge);
        }
    }

    public List<Edge> getConnections(String location) {
        return graph.get(location);
    }

    public void movePlayer(String destination) {
        player.setCurrentLocation(destination);
    }

    public Location getPlayerLocation() {
        return player.getCurrentLocation();
    }

    public void interactWithNPC(String npcName) {
        Location currentLocation = player.getCurrentLocation();
        NPC npc = currentLocation.getNPC(npcName);
        if (npc != null) {
            npc.interact(player);
        } else {
            System.out.println("No such NPC in the current location.");
        }
    }

    public void addItemToInventory(String itemName) {
        Item item = new Item(itemName);
        player.addItemToInventory(item);
    }

    public void removeItemFromInventory(String itemName) {
        player.removeItemFromInventory(itemName);
    }

    public void printInventory() {
        player.printInventory();
    }

    public static void main(String[] args) {
        GameWorld world = new GameWorld();
        world.addLocation("Village", "A small village surrounded by dense forests.");
        world.addLocation("Forest", "A dark and mysterious forest with hidden paths.");
        world.addLocation("Mountain", "A steep mountain with breathtaking views.");
        world.addLocation("Castle", "An ancient castle with a rich history.");

        world.addConnection("Village", "Forest", 2);
        world.addConnection("Forest", "Mountain", 3);
        world.addConnection("Mountain", "Castle", 4);
        world.addConnection("Castle", "Village", 5);

        world.player.setCurrentLocation("Village");
        world.addItemToInventory("Map");
        world.addItemToInventory("Compass");

        world.movePlayer("Forest");
        world.interactWithNPC("Old Hermit");
        world.movePlayer("Mountain");
        world.interactWithNPC("Mountain Guide");
        world.movePlayer("Castle");
        world.interactWithNPC("King");

        world.printInventory();
    }
}

class Player {
    private Location currentLocation;
    private List<Item> inventory;

    public Player() {
        inventory = new ArrayList<>();
    }

    public void setCurrentLocation(String locationName) {
        currentLocation = GameWorld.this.locations.get(locationName);
    }

    public Location getCurrentLocation() {
        return currentLocation;
    }

    public void addItemToInventory(Item item) {
        inventory.add(item);
    }

    public void removeItemFromInventory(String itemName) {
        inventory.removeIf(item -> item.getName().equals(itemName));
    }

    public void printInventory() {
        System.out.println("Inventory:");
        for (Item item : inventory) {
            System.out.println("- " + item.getName());
        }
    }
}

class Location {
    private String name;
    private String description;
    private List<NPC> npcs;

    public Location(String name, String description) {
        this.name = name;
        this.description = description;
        npcs = new ArrayList<>();
    }

    public void addNPC(NPC npc) {
        npcs.add(npc);
    }

    public NPC getNPC(String name) {
        for (NPC npc : npcs) {
            if (npc.getName().equals(name)) {
                return npc;
            }
        }
        return null;
    }
}

class NPC {
    private String name;
    private String greeting;

    public NPC(String name, String greeting) {
        this.name = name;
        this.greeting = greeting;
    }

    public void interact(Player player) {
        System.out.println(greeting);
        // Additional interaction logic can be added here.
    }

    public String getName() {
        return name;
    }
}

class Item {
    private String name;

    public Item(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }
}

class Edge {
    private String to;
    private int distance;

    public Edge(String to, int distance) {
        this.to = to;
        this.distance = distance;
    }

    public String getTo() {
        return to;
    }

    public int getDistance() {
        return distance;
    }
}

扩展功能说明：

1. 角色状态：我们引入了Player类，用于管理玩家的状态，如当前位置和背包物品。
2. 动态事件：虽然在这个简单示例中没有具体实现，但我们可以通过在NPC类中添加更多交互逻辑，以及在Location类中添加随机事件来实现动态事件。
3. NPC交互：我们添加了NPC类，玩家可以与之互动。目前的交互仅限于打印问候语，但可以进一步扩展，如交易、接受任务等。
4. 物品系统：Item类用于表示玩家可以收集的物品。Player类中的inventory属性用于存储这些物品。

通过这些扩展，游戏变得更加丰富和有趣。玩家可以在游戏世界中探索、与NPC互动、收集物品，并根据自己的选择影响游戏进程。这不仅提高了游戏的可玩性，也为开发者提供了更多创造性的空间，以构建更加复杂和引人入胜的游戏体验。

为了进一步扩展游戏，我们可以增加一些更复杂的功能，如任务系统、战斗机制、技能树和角色成长。以下是在现有游戏框架基础上的扩展代码：

import java.util.*;

public class GameWorld {
    private Map<String, List<Edge>> graph;
    private Map<String, Location> locations;
    private Player player;

    public GameWorld() {
        graph = new HashMap<>();
        locations = new HashMap<>();
        player = new Player();
    }

    // ... 保留之前的方法 ...

    public void acceptQuest(Quest quest) {
        player.acceptQuest(quest);
    }

    public void completeQuest(Quest quest) {
        player.completeQuest(quest);
    }

    public void attackMonster(Monster monster) {
        player.attack(monster);
    }

    public void levelUp() {
        player.levelUp();
    }

    // ... 其他方法 ...

    public static void main(String[] args) {
        GameWorld world = new GameWorld();
        // ... 地图初始化代码 ...

        // 创建NPC并分配任务
        NPC oldHermit = new NPC("Old Hermit", "Greetings, young traveler!");
        Quest hermitQuest = new Quest("FindHerbs", "Collect 5 herbs", 10);
        oldHermit.setQuest(hermitQuest);
        world.locations.get("Forest").addNPC(oldHermit);

        // 创建怪物
        Monster wolf = new Monster("Wolf", 5, 2);
        world.locations.get("Forest").addMonster(wolf);

        // 主循环
        while (true) {
            Location currentLocation = world.getPlayerLocation();
            System.out.println("You are in " + currentLocation.getName() + ".");
            System.out.println(currentLocation.getDescription());

            // 处理NPC交互
            for (NPC npc : currentLocation.getNPCs()) {
                System.out.println("NPC: " + npc.getName());
                world.interactWithNPC(npc.getName());
            }

            // 处理怪物战斗
            for (Monster monster : currentLocation.getMonsters()) {
                System.out.println("Encountered a " + monster.getName() + "!");
                world.attackMonster(monster);
            }

            // 更新玩家状态
            world.player.update();

            // 休息和恢复
            System.out.println("Resting...");
            player.rest();

            // 接受和完成任务
            for (Quest quest : player.getQuests()) {
                if (quest.isCompleted()) {
                    System.out.println("Quest completed: " + quest.getName());
                    world.completeQuest(quest);
                }
            }

            // 级别提升
            if (player.canLevelUp()) {
                world.levelUp();
            }

            // 移动到下一个地点
            List<Edge> connections = world.getConnections(currentLocation.getName());
            if (!connections.isEmpty()) {
                Edge nextEdge = connections.get(new Random().nextInt(connections.size()));
                world.movePlayer(nextEdge.getTo());
            }
        }
    }
}

class Player {
    private Location currentLocation;
    private List<Item> inventory;
    private List<Quest> quests;
    private int level;
    private int experience;
    private int health;
    private int maxHealth;

    public Player() {
        inventory = new ArrayList<>();
        quests = new ArrayList<>();
        level = 1;
        experience = 0;
        health = maxHealth = 100;
    }

    // ... 保留之前的方法 ...

    public void acceptQuest(Quest quest) {
        quests.add(quest);
    }

    public void completeQuest(Quest quest) {
        quests.remove(quest);
        experience += quest.getExperienceReward();
    }

    public void attack(Monster monster) {
        // 攻击逻辑
        int damage = 10; // 假定固定伤害
        monster.takeDamage(damage);
    }

    public void levelUp() {
        level++;
        maxHealth += 10;
        health = maxHealth;
    }

    public boolean canLevelUp() {
        return experience >= level * 100;
    }

    public void rest() {
        health = maxHealth;
    }

    public void update() {
        // 更新玩家状态
    }

    // ... 其他方法 ...
}

// ... 其他类 ...

class Quest {
    private String name;
    private String description;
    private int experienceReward;

    public Quest(String name, String description, int experienceReward) {
        this.name = name;
        this.description = description;
        this.experienceReward = experienceReward;
    }

    public boolean isCompleted() {
        // 判断任务是否完成
        return false;
    }
}

class Monster {
    private String name;
    private int health;
    private int damage;

    public Monster(String name, int health, int damage) {
        this.name = name;
        this.health = health;
        this.damage = damage;
    }

    public void takeDamage(int damage) {
        this.health -= damage;
    }
}

// ... 其他类 ...

新增功能说明：

1. 任务系统：我们引入了Quest类，NPC可以分配任务给玩家。在主循环中，玩家可以接受任务，并在完成后获得经验值奖励。
2. 战斗机制：Monster类表示游戏中的敌人，玩家可以攻击怪物。这里简化了战斗逻辑，但可以进一步扩展，如加入回合制战斗、技能释放等。
3. 角色成长：Player类中包含了级别、经验值、健康等属性，支持角色成长和升级。
4. 主循环：游戏现在有了一个基本的主循环，处理玩家在不同地点之间的移动、与NPC的交互、战斗、任务完成和角色状态更新。

通过这些扩展，游戏变得更加复杂和吸引人。玩家可以享受探索、战斗、任务完成和角色成长的乐趣。当然，这只是一个基础框架，可以根据需要进一步完善和扩展，例如，增加更多的物品、技能、NPC对话、剧情分支等，以构建一个更加丰富多彩的游戏世界。