数据结构:图

/**
 * 邻接矩阵表示的图结构（对应C语言的MGraph）
 */
public class MGraph {
    // 顶点数最大值（对应C的MaxVertexNum宏）
    public static final int MAX_VERTEX_NUM = 100;
    
    // 顶点表：存储顶点数据（原C的VertexType Vex[]，此处用char数组对应原char类型顶点）
    private char[] vertexArray;
    // 邻接矩阵：存储边的权值（原C的EdgeType Edge[][]，此处用int二维数组对应原int权值）
    private int[][] adjacencyMatrix;
    // 当前图的顶点数（对应原vexnum）
    private int vertexCount;
    // 当前图的弧（边）数（对应原arcnum）
    private int arcCount;

    /**
     * 默认构造方法：初始化空图
     */
    public MGraph() {
        this.vertexArray = new char[MAX_VERTEX_NUM];
        this.adjacencyMatrix = new int[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
        this.vertexCount = 0;
        this.arcCount = 0;
        
        // 可选：初始化邻接矩阵为"无连接"状态（Java默认int为0，已满足）
    }

    // ---------------------- 可选扩展方法（非原结构必需，但常用） ----------------------
    /**
     * 添加顶点
     * @param vertex 顶点数据（char类型，对应原VertexType）
     * @return 是否添加成功（顶点数未超过最大值）
     */
    public boolean addVertex(char vertex) {
        if (vertexCount >= MAX_VERTEX_NUM) return false;
        vertexArray[vertexCount++] = vertex;
        return true;
    }

    /**
     * 添加边（无向图）
     * @param v1 顶点1的索引（从0开始）
     * @param v2 顶点2的索引（从0开始）
     * @param weight 边的权值（对应原EdgeType）
     */
    public void addEdge(int v1, int v2, int weight) {
        if (v1 < 0 || v1 >= vertexCount || v2 < 0 || v2 >= vertexCount) return;
        // 无向图：对称赋值
        adjacencyMatrix[v1][v2] = weight;
        adjacencyMatrix[v2][v1] = weight;
        arcCount++; // 无向图每条边算1条弧
    }

    /**
     * 添加边（有向图）
     * @param from 源顶点索引
     * @param to 目标顶点索引
     * @param weight 边的权值
     */
    public void addDirectedEdge(int from, int to, int weight) {
        if (from < 0 || from >= vertexCount || to < 0 || to >= vertexCount) return;
        adjacencyMatrix[from][to] = weight;
        arcCount++; // 有向图每条边算1条弧
    }
}

// 边表结点
class EdgeNode {
    private int adjvex;       // 该弧所指向的顶点的下标或者位置
    private int weight;       // 权值，对于非网图可以不需要
    private EdgeNode next;    // 指向下一个邻接点

    // 构造方法
    public EdgeNode(int adjvex, int weight) {
        this.adjvex = adjvex;
        this.weight = weight;
        this.next = null;
    }
}

// 顶点表结点
class VertexNode {
    private char data;        // 顶点域，存储顶点信息
    private EdgeNode firstedge;  // 边表头指针

    // 构造方法
    public VertexNode(char data) {
        this.data = data;
        this.firstedge = null;
    }
}

// 邻接表表示的图
public class AdjacencyListGraph {
    private static final int MAXVEX = 100;  // 图中顶点数目的最大值
    private VertexNode[] adjList;           // 顶点表数组
    private int numVertexes;                // 图中当前顶点数
    private int numEdges;                   // 图中当前边数

    // 构造方法
    public AdjacencyListGraph() {
        adjList = new VertexNode[MAXVEX];
        numVertexes = 0;
        numEdges = 0;
    }
}

/**
 * 弧结点（Arc Node）
 * 存储有向边的信息
 */
class ArcNode {
    int tailVex;    // 弧尾顶点下标（起点）
    int headVex;    // 弧头顶点下标（终点）
    ArcNode hLink;  // 指向同一弧头的下一条弧（入边链）
    ArcNode tLink;  // 指向同一弧尾的下一条弧（出边链）
    int weight;     // 弧权值（可选）

    public ArcNode(int tailVex, int headVex, int weight) {
        this.tailVex = tailVex;
        this.headVex = headVex;
        this.weight = weight;
        this.hLink = null;
        this.tLink = null;
    }
}

/**
 * 顶点结点（Vertex Node）
 * 存储顶点信息及其关联的弧
 */
class VertexNode {
    char data;          // 顶点数据
    ArcNode firstIn;    // 指向第一条入弧
    ArcNode firstOut;   // 指向第一条出弧

    public VertexNode(char data) {
        this.data = data;
        this.firstIn = null;
        this.firstOut = null;
    }
}

/**
 * 十字链表图结构
 */
public class OrthogonalListGraph {
    private VertexNode[] vertexList;  // 顶点表
    private int vertexCount;          // 顶点数
    private int arcCount;            // 弧数
    private static final int MAX_VERTEX = 100; // 最大顶点数

    public OrthogonalListGraph() {
        vertexList = new VertexNode[MAX_VERTEX];
        vertexCount = 0;
        arcCount = 0;
    }
}

// 边的实体类，存储一条边的起点、终点和权值
class Edge {
    // 边的起点下标
    int begin;
    // 边的终点下标
    int end;
    // 边的权值
    int weight;

    public Edge(int begin, int end, int weight) {
        this.begin = begin;
        this.end = end;
        this.weight = weight;
    }
}

// 边集数组表示的图结构
public class EdgeSetArrayGraph {
    // 存储顶点信息的数组
    private char[] vertexArray;
    // 存储边信息的数组
    private Edge[] edgeArray;
    // 图中顶点的数量
    private int vertexNum;
    // 图中边的数量
    private int edgeNum;

    public EdgeSetArrayGraph(char[] vertexArray, Edge[] edgeArray) {
        this.vertexArray = vertexArray;
        this.edgeArray = edgeArray;
        this.vertexNum = vertexArray.length;
        this.edgeNum = edgeArray.length;
    }
}

public class GraphTraversal {
    private boolean[] visited; // 访问标记数组：visited[v]为true表示顶点v已访问
    // 深度优先遍历（从顶点v出发）
    public void dfs(MGraph G, int v) {
        visit(G, v);         // 访问当前顶点
        visited[v] = true;   // 标记为已访问
        // 遍历当前顶点的所有邻接点
        int w = G.firstNeighbor(v);
        while (w != -1) {
            if (!visited[w]) { // 若邻接点w未访问过，递归访问w
                dfs(G, w);
            }
            w = G.nextNeighbor(v, w); // 取w的下一个邻接点
        }
    }

    // 遍历整个图（对所有未访问的顶点调用dfs）
    public void dfstraverse(MGraph G) {
        // 初始化访问标记数组
        visited = new boolean[G.getVexnum()];
        for (int i = 0; i < G.getVexnum(); i++) {
            visited[i] = false;
        }
        // 对每个顶点，若未访问则启动DFS
        for (int v = 0; v < G.getVexnum(); v++) {
            if (!visited[v]) {
                dfs(G, v);
            }
        }
    }
}

public class MGraphBFS {
    private int vexnum;          // 顶点数
    private int arcnum;          // 边数
    private int[][] arcs;        // 邻接矩阵
    private String[] vexs;       // 顶点值数组
    private boolean[] visited;   // 访问标记数组

    // 构造方法
    public MGraphBFS(int vexnum, int arcnum, String[] vexs, int[][] arcs) {
        this.vexnum = vexnum;
        this.arcnum = arcnum;
        this.vexs = vexs;
        this.arcs = arcs;
        this.visited = new boolean[vexnum];
    }

    /**
     * 广度优先遍历入口方法
     */
    public void BFSTraverse() {
        // 初始化访问标记数组
        for (int i = 0; i < vexnum; i++) {
            visited[i] = false;
        }
        
        // 使用队列辅助BFS遍历
        Queue<Integer> queue = new LinkedList<>();
        
        // 遍历所有顶点
        for (int i = 0; i < vexnum; i++) {
            if (!visited[i]) {
                // 访问当前顶点并标记
                visit(i);
                visited[i] = true;
                queue.offer(i);  // 入队
                
                // BFS核心：处理队列中的顶点
                while (!queue.isEmpty()) {
                    int v = queue.poll();  // 出队
                    
                    // 遍历v的所有邻接点
                    for (int w = firstNeighbor(v); w >= 0; w = nextNeighbor(v, w)) {
                        if (!visited[w]) {
                            visit(w);
                            visited[w] = true;
                            queue.offer(w);  // 邻接点入队
                        }
                    }
                }
            }
        }
    }

    /**
     * 获取顶点v的第一个邻接点
     * @param v 顶点下标
     * @return 邻接点下标（无则返回-1）
     */
    private int firstNeighbor(int v) {
        for (int w = 0; w < vexnum; w++) {
            if (arcs[v][w] != 0) {  // 存在边
                return w;
            }
        }
        return -1;
    }

    /**
     * 获取顶点v在邻接点w之后的下一个邻接点
     * @param v 顶点下标
     * @param w 当前邻接点下标
     * @return 下一个邻接点下标（无则返回-1）
     */
    private int nextNeighbor(int v, int w) {
        for (int nextW = w + 1; nextW < vexnum; nextW++) {
            if (arcs[v][nextW] != 0) {  // 存在边
                return nextW;
            }
        }
        return -1;
    }
}

public class PrimAlgorithm {
    // 表示无穷大（用于初始化不连通的边）
    private static final int INF = Integer.MAX_VALUE;
    /**
     * 普里姆算法构建最小生成树
     * @param graph 邻接矩阵表示的带权无向图
     * @param vertexCount 顶点数量
     */
    public void prim(int[][] graph, int vertexCount) {
        // 存储最小生成树的顶点
        int[] parent = new int[vertexCount];
        // 存储顶点到最小生成树的最小权值
        int[] key = new int[vertexCount];
        // 标记顶点是否已加入最小生成树
        boolean[] mstSet = new boolean[vertexCount];

        // 初始化所有key值为无穷大
        Arrays.fill(key, INF);
        // 选择第一个顶点作为起始点，key值设为0
        key[0] = 0;
        // 第一个顶点的父节点设为-1（没有父节点）
        parent[0] = -1;

        // 构建最小生成树，需要vertexCount-1条边
        for (int count = 0; count < vertexCount - 1; count++) {
            // 选择距离最小生成树最近的顶点
            int u = minKey(key, mstSet, vertexCount);
            // 将选择的顶点标记为已加入最小生成树
            mstSet[u] = true;

            // 更新与u相邻的顶点的key值和父节点
            for (int v = 0; v < vertexCount; v++) {
                // 条件：v未加入MST，u和v之间有边，且边的权值小于当前key[v]
                if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
                    parent[v] = u;
                    key[v] = graph[u][v];
                }
            }
        }
    }

    /**
     * 找到key值最小且未加入MST的顶点
     */
    private int minKey(int[] key, boolean[] mstSet, int vertexCount) {
        int min = INF;
        int minIndex = -1;

        for (int v = 0; v < vertexCount; v++) {
            if (!mstSet[v] && key[v] < min) {
                min = key[v];
                minIndex = v;
            }
        }
        return minIndex;
    }
}

public class KruskalMST {
    /**
     * Kruskal算法实现
     * @param edges 所有边的集合
     * @param vertexCount 顶点总数
     * @return 最小生成树的边集合
     */
    public static List<Edge> kruskal(List<Edge> edges, int vertexCount) {
        // 1. 按边权升序排序
        Collections.sort(edges);
        
        // 2. 初始化并查集
        UnionFind uf = new UnionFind(vertexCount);
        List<Edge> mst = new ArrayList<>(); // 存储最小生成树的边
        
        // 3. 遍历所有边（从小到大）
        for (Edge edge : edges) {
            int rootSrc = uf.find(edge.src);
            int rootDest = uf.find(edge.dest);
            
            // 4. 若边的两端不在同一集合（不构成环）
            if (rootSrc != rootDest) {
                mst.add(edge);          // 加入生成树
                uf.union(rootSrc, rootDest); // 合并集合
                
                // 5. 提前终止：已选边数 = 顶点数-1
                if (mst.size() == vertexCount - 1) break;
            }
        }
        return mst;
    }
}

public class Dijkstra {
    /**
     * 迪杰斯特拉算法求单源最短路径
     * @param graph 图实例
     * @param src 源点下标
     */
    public static void dijkstra(Graph graph, int src) {
        int V = graph.V;
        int[] dist = new int[V];       // 存储源点到各顶点的最短距离
        int[] prev = new int[V];       // 存储最短路径的前驱顶点（用于回溯路径）
        Arrays.fill(dist, Integer.MAX_VALUE);  // 初始化为无穷大
        Arrays.fill(prev, -1);         // 前驱初始化为-1（无前驱）

        dist[src] = 0;  // 源点到自身距离为0

        // 优先队列：按边的权值（距离）升序排列（最小堆）
        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
        pq.add(new Edge(src, 0));  // 将源点加入队列

        while (!pq.isEmpty()) {
            Edge uEdge = pq.poll();  // 取出当前距离最小的顶点
            int u = uEdge.dest;

            // 若队列中取出的距离大于当前记录的最短距离，跳过（避免重复处理）
            if (dist[u] < uEdge.weight) continue;

            // 遍历u的所有邻接顶点v
            for (Edge vEdge : graph.adj.get(u)) {
                int v = vEdge.dest;
                int newDist = dist[u] + vEdge.weight;  // 从u到v的新距离

                // 若新距离更短，更新dist[v]和前驱，并加入队列
                if (newDist < dist[v]) {
                    dist[v] = newDist;
                    prev[v] = u;
                    pq.add(new Edge(v, newDist));
                }
            }
        }

        // 输出结果：每个顶点的最短距离和路径
        printResult(dist, prev, src);
    }
}

public class FloydWarshall {
    private static final int INF = Integer.MAX_VALUE; // 无穷大（表示无直接路径）

    /**
     * Floyd算法实现
     * @param graph 邻接矩阵（graph[i][j]表示顶点i到j的直接距离）
     */
    public static void floyd(int[][] graph) {
        int n = graph.length;
        // 初始化距离矩阵和路径矩阵
        int[][] dist = new int[n][n];
        int[][] next = new int[n][n]; // 记录路径中i的下一个节点

        // 1. 初始化矩阵
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = graph[i][j];
                next[i][j] = (graph[i][j] != INF && i != j) ? j : -1;
            }
        }

        // 2. 动态规划：以k为中间点更新所有路径
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                if (dist[i][k] == INF) continue; // 跳过无效路径
                for (int j = 0; j < n; j++) {
                    // 避免整数溢出
                    if (dist[k][j] != INF && dist[i][k] != INF) {
                        int newDist = dist[i][k] + dist[k][j];
                        if (newDist < dist[i][j]) {
                            dist[i][j] = newDist;
                            next[i][j] = next[i][k]; // 更新路径
                        }
                    }
                }
            }
        }

        // 3. 检测负权回路
        for (int i = 0; i < n; i++) {
            if (dist[i][i] < 0) {
                throw new RuntimeException("存在负权回路！");
            }
        }
    }
}

public class TopologicalSort {
    /**
     * 拓扑排序算法（返回是否成功，存在回路则失败）
     * @param G 图实例
     * @return 排序成功返回true，存在回路返回false
     */
    public static boolean topologicalSort(Graph G) {
        int[] indegree = G.computeIndegree(); // 1. 计算所有顶点的入度
        Deque<Integer> stack = new ArrayDeque<>(); // 2. 初始化栈（存储入度为0的顶点）
        int count = 0; // 3. 计数：已输出的顶点数

        // 步骤1：将所有入度为0的顶点压入栈
        for (int i = 0; i < G.vexnum; i++) {
            if (indegree[i] == 0) {
                stack.push(i);
            }
        }

        // 步骤2：循环处理栈中的顶点（入度为0的顶点）
        while (!stack.isEmpty()) {
            int u = stack.pop(); // 弹出入度为0的顶点
            System.out.print(u + " "); // 输出该顶点
            count++;

            // 遍历顶点u的所有邻接顶点v，更新其入度
            for (EdgeNode e : G.vertices[u].adjList) {
                int v = e.adjvex;
                indegree[v]--; // v的入度减1（因为u已处理）
                if (indegree[v] == 0) { // 若v的入度变为0，压入栈
                    stack.push(v);
                }
            }
        }

        // 步骤3：检查是否存在回路（若输出的顶点数少于总顶点数，说明有回路）
        if (count < G.vexnum) {
            System.out.println("图中存在回路，拓扑排序失败！");
            return false;
        } else {
            System.out.println("拓扑排序成功！");
            return true;
        }
    }
}