package graph;
 
import java.util.Scanner;
 
public class CreateALGraph {
    static final int MaxVnum = 100;  // 頂點(diǎn)數(shù)最大值
 
    public static void main(String[] args) {
        ALGraph G = new ALGraph();
        for (int i = 0; i < G.Vex.length; i++) {
            G.Vex[i] = new VexNode();
        }
        CreateALGraph(G); // 創(chuàng)建有向圖鄰接表
        printg(G); // 輸出鄰接表
    }
 
    static int locatevex(ALGraph G, char x) {
        for (int i = 0; i < G.vexnum; i++) // 查找頂點(diǎn)信息的下標(biāo)
            if (x == G.Vex[i].data)
                return i;
        return -1; // 沒(méi)找到
    }
 
    // 插入一條邊
    static void insertedge(ALGraph G, int i, int j) {
        AdjNode s = new AdjNode();
        s.v = j;
        s.next = G.Vex[i].first;
        G.Vex[i].first = s;
    }
 
    // 輸出鄰接表
    static void printg(ALGraph G) {
        System.out.println("----------鄰接表如下：----------");
 
        for (int i = 0; i < G.vexnum; i++) {
            AdjNode t = G.Vex[i].first;
            System.out.print(G.Vex[i].data + "：  ");
            while (t != null) {
                System.out.print("[" + t.v + "]\t");
                t = t.next;
            }
            System.out.println();
        }
    }
 
    // 創(chuàng)建有向圖鄰接表
    static void CreateALGraph(ALGraph G) {
        int i, j;
        char u, v;
 
        System.out.println("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù):");
        Scanner scanner = new Scanner(System.in);
        G.vexnum = scanner.nextInt();
        G.edgenum = scanner.nextInt();
        System.out.println("請(qǐng)輸入頂點(diǎn)信息:");
 
        for (i = 0; i < G.vexnum; i++)//輸入頂點(diǎn)信息，存入頂點(diǎn)信息數(shù)組
            G.Vex[i].data = scanner.next().charAt(0);
        for (i = 0; i < G.vexnum; i++)
            G.Vex[i].first = null;
        System.out.println("請(qǐng)依次輸入每條邊的兩個(gè)頂點(diǎn)u,v");
 
        while (G.edgenum-- > 0) {
            u = scanner.next().charAt(0);
            v = scanner.next().charAt(0);
            i = locatevex(G, u); // 查找頂點(diǎn) u 的存儲(chǔ)下標(biāo)
            j = locatevex(G, v); // 查找頂點(diǎn) v 的存儲(chǔ)下標(biāo)
            if (i != -1 && j != -1)
                insertedge(G, i, j);
            else {
                System.out.println("輸入頂點(diǎn)信息錯(cuò)！請(qǐng)重新輸入！");
                G.edgenum++; // 本次輸入不算
            }
        }
    }
}
 
// 定義鄰接點(diǎn)類(lèi)型
class AdjNode {
    int v; // 鄰接點(diǎn)下標(biāo)
    AdjNode next; // 指向下一個(gè)鄰接點(diǎn)
}
 
// 定義頂點(diǎn)類(lèi)型
class VexNode {
    char data; // VexType為頂點(diǎn)的數(shù)據(jù)類(lèi)型，根據(jù)需要定義
    AdjNode first; // 指向第一個(gè)鄰接點(diǎn)
}
 
// 定義鄰接表類(lèi)型
class ALGraph {
    VexNode Vex[] = new VexNode[CreateALGraph.MaxVnum];
    int vexnum; // 頂點(diǎn)數(shù)
    int edgenum; // 邊數(shù)
}