Java，给定一个带权有向图的邻接矩阵存储结构g，创建对应的邻接表存储结构G

创建邻接表存储结构G的步骤如下：

1. 定义邻接表的结构体，包括顶点结构体和边结构体。

class Vertex {
    int data;  // 顶点数据
    Edge firstEdge;  // 指向第一条依附该顶点的边的指针
}

class Edge {
    int adjvex;  // 该边的邻接点编号
    int weight;  // 该边的权值
    Edge next;  // 指向下一条依附同一顶点的边的指针
}

2. 遍历邻接矩阵g，将每个顶点和与其相邻的顶点存储到邻接表G中。

Vertex[] G = new Vertex[g.n];  // 定义邻接表
int n = g.n;  // 顶点个数

for (int i = 0; i < n; i++) {
    // 初始化每个顶点的数据和第一条边的指针
    G[i] = new Vertex();
    G[i].data = i;
    G[i].firstEdge = null;
    
    for (int j = 0; j < n; j++) {
        if (g.edges[i][j] != 0) {  // 存在一条边
            Edge p = new Edge();  // 创建新的边结构体
            p.adjvex = j;  // 存储邻接点编号
            p.weight = g.edges[i][j];  // 存储权值
            p.next = G[i].firstEdge;  // 将新边插入到顶点的边链表头部
            G[i].firstEdge = p;
        }
    }
}

3. 创建完毕后，邻接表G即为所求。

完整的代码示例如下：

import java.util.Scanner;

class Vertex {
    int data;  // 顶点数据
    Edge firstEdge;  // 指向第一条依附该顶点的边的指针
}

class Edge {
    int adjvex;  // 该边的邻接点编号
    int weight;  // 该边的权值
    Edge next;  // 指向下一条依附同一顶点的边的指针
}

class MGraph {
    int n;  // 顶点个数
    int[][] edges;  // 邻接矩阵
}

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        MGraph g = new MGraph();
        CreateGraph(g, input);

        Vertex[] G = new Vertex[g.n];
        CreateAdjList(g, G);

        input.close();
    }

    public static void CreateGraph(MGraph g, Scanner input) {
        int n = input.nextInt();
        int m = input.nextInt();
        g.n = n;
        g.edges = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                g.edges[i][j] = 0;
            }
        }
        for (int i = 0; i < m; i++) {
            int u = input.nextInt();
            int v = input.nextInt();
            int w = input.nextInt();
            g.edges[u][v] = w;
        }
    }

    public static void CreateAdjList(MGraph g, Vertex[] G) {
        int n = g.n;  // 顶点个数

        for (int i = 0; i < n; i++) {
            // 初始化每个顶点的数据和第一条边的指针
            G[i] = new Vertex();
            G[i].data = i;
            G[i].firstEdge = null;
            
            for (int j = 0; j < n; j++) {
                if (g.edges[i][j] != 0) {  // 存在一条边
                    Edge p = new Edge();  // 创建新的边结构体
                    p.adjvex = j;  // 存储邻接点编号
                    p.weight = g.edges[i][j];  // 存储权值
                    p.next = G[i].firstEdge;  // 将新边插入到顶点的边链表头部
                    G[i].firstEdge = p;
                }
            }
        }
    }
}