图的存储结构(Java)

 1 //1 无向图的邻接矩阵实现 时间复杂度:O(n^2) 空间复杂度:O(n^2)
 2 class Graph
 3 {
 4     public int[][] adjacencyMatrix;  //邻接矩阵
 5     public int vexnum;  //边数
 6     public int arcnum;  //顶点数
 7     public char[] vexs;  //顶点数组
 8     
 9     public Graph(int vexnum, int arcnum)
10     {
11         this.vexnum = vexnum;
12         this.arcnum = arcnum;
13         this.adjacencyMatrix = new int[vexnum][vexnum];
14         this.vexs = new char[vexnum];
15     }
16     
17     public void createUDG()  
18     {
19         //1 创建顶点数组
20         Scanner input = new Scanner(System.in);
21         for(int i = 0; i < this.vexnum; i++)
22             this.vexs[i] = input.next().charAt(0);
23         
24         //2 初始化邻接矩阵
25         for(int j = 0; j < this.vexnum; j++)
26             for(int k = 0; k < this.vexnum; k++)
27                 this.adjacencyMatrix[j][k] = 0;
28         
29         //3 根据顶点创建邻接矩阵
30         for(int p = 0; p < this.arcnum; p++)
31         {
32             char a = input.next().charAt(0);
33             char b = input.next().charAt(0);
34             int i = this.locateVex(a);
35             int j = this.locateVex(b);
36             this.adjacencyMatrix[i][j] = this.adjacencyMatrix[j][i] = 1; //对称阵
37         }
38     }
39     
40     public int locateVex(char vex)
41     {
42         int i;
43         for(i = 0; i < this.vexs.length && vex != this.vexs[i]; i++);
44         return i;
45     }
46 }
47 
48 //2 有向图的邻接矩阵实现 时间复杂度:O(n^2) 空间复杂度:O(n^2)
49 class Graph  
50 {
51     public int[][] adjacencyMatrix;
52     public int vexnum;
53     public int arcnum;
54     public char[] vexs;
55     
56     public Graph(int vexnum, int arcnum)
57     {
58         this.vexnum = vexnum;
59         this.arcnum = arcnum;
60         this.adjacencyMatrix = new int[vexnum][vexnum];
61         this.vexs = new char[vexnum];
62     }
63     
64     public void createDG()
65     {
66         Scanner input = new Scanner(System.in);
67         for(int i = 0; i < this.vexnum; i++)
68             this.vexs[i] = input.next().charAt(0);
69         for(int j = 0; j < this.vexnum; j++)
70             for(int k = 0; k < this.vexnum; k++)
71                 this.adjacencyMatrix[j][k] = 0;
72         for(int p = 0; p < this.arcnum; p++)
73         {
74             char a = input.next().charAt(0);
75             char b = input.next().charAt(0);
76             int i = this.locateVex(a);
77             int j = this.locateVex(b);
78             this.adjacencyMatrix[i][j] = 1;
79         }
80     }
81     
82     public int locateVex(char vex)
83     {
84         int i;
85         for(i = 0; i < this.vexs.length && vex != this.vexs[i]; i++);
86         return i;
87     }
88 }