图的代码实现（以毗邻矩阵表现）

2. package algorithm;
4. import java.util.ArrayList;
5. import java.util.Arrays;
6. import java.util.List;
7. import java.util.Locale;
9. public class GraphByAdjacencyMatrix {
10.     private final List<Integer> mVertex = new ArrayList<>();
11.     private final List<List<Integer>> mAdjMatrix = new ArrayList<>();
13.     /**
14.      * 初始化图
15.      *
16.      * @param vertex 顶点列表
17.      * @param edges 相邻顶点关系（边）
18.      */
19.     public void init(List<Integer> vertex, List<int[]> edges) {
20.         mVertex.addAll(vertex);
21.         int size = size();
22.         for (int i = 0; i < size; i++) {
23.             List<Integer> col = new ArrayList<>();
24.             for (int j = 0; j < size; j++) {
25.                 col.add(0);
26.             }
27.             mAdjMatrix.add(col);
28.         }
29.         for (int i = 0; i < edges.size(); i++) {
30.             int[] edge = edges.get(i);
31.             checkEdgeValid(edge, i);
32.             mAdjMatrix.get(edge[0]).set(edge[1], 1);
33.             mAdjMatrix.get(edge[1]).set(edge[0], 1);
34.         }
35.     }
37.     /**
38.      * 添加顶点
39.      *
40.      * @param val 顶点值
41.      */
42.     public void addVertex(int val) {
43.         List<Integer> row = new ArrayList<>();
44.         for (int j = 0; j < size(); j++) {
45.             row.add(0);
46.         }
47.         mVertex.add(val);
48.         mAdjMatrix.add(row);
49.         for (List<Integer> col : mAdjMatrix) {
50.             col.add(0);
51.         }
52.     }
54.     /**
55.      * 删除顶点
56.      *
57.      * @param val 顶点值
58.      */
59.     public void deleteVertex(int val) {
60.         int index = mVertex.indexOf(val);
61.         if (index == -1) {
62.             System.out.println("can't delete a Non-existent vertices");
63.             return;
64.         }
65.         mVertex.remove(index);
66.         mAdjMatrix.remove(index);
67.         for (List<Integer> row : mAdjMatrix) {
68.             row.remove(index);
69.         }
70.     }
72.     /**
73.      * 添加相邻顶点关系（边）
74.      *
75.      * @param edge 边
76.      */
77.     public void addEdge(int[] edge) {
78.         checkEdgeValid(edge, -1);
79.         mAdjMatrix.get(edge[0]).set(edge[1], 1);
80.         mAdjMatrix.get(edge[1]).set(edge[0], 1);
81.     }
83.     /**
84.      * 删除相邻顶点关系（边）
85.      *
86.      * @param edge 边
87.      */
88.     public void deleteEdge(int[] edge) {
89.         checkEdgeValid(edge, -1);
90.         mAdjMatrix.get(edge[0]).set(edge[1], 0);
91.         mAdjMatrix.get(edge[1]).set(edge[0], 0);
92.     }
94.     public void print() {
95.         System.out.println("\n------------------print graph-------------------");
96.         System.out.printf(Locale.ENGLISH, "\n\t%s%s%n",
97.                 " ".repeat(4), getArrayPrintString(mVertex, " ", "  ", " "));
98.         System.out.printf(Locale.ENGLISH, "\n");
99.         for (int i = 0; i < mAdjMatrix.size(); i++) {
100.             List<Integer> row = mAdjMatrix.get(i);
101.             Integer vertex = mVertex.get(i);
102.             System.out.printf(Locale.ENGLISH, "\t%s%s%n", String.format("%3d:", vertex),
103.                     getArrayPrintString(row, "[", ", ", "]"));
104.         }
105.     }
107.     private String getArrayPrintString(List<Integer> array, String symbolLeft, String symbolMid, String symbolRight) {
108.         StringBuilder sb = new StringBuilder(symbolLeft);
109.         for (int i = 0; i < array.size(); i++) {
110.             sb.append(String.format("%3d", array.get(i)));
111.             if (i < array.size() - 1)
112.                 sb.append(symbolMid);
113.         }
114.         sb.append(symbolRight);
115.         return sb.toString();
116.     }
118.     private void checkEdgeValid(int[] edge, int indexAtEdges) {
119.         if (edge.length != 2) {
120.             String errMessage = indexAtEdges != -1 ? String.format(Locale.ENGLISH,
121.                     "invalid edge at edges[%s]!", indexAtEdges) : "invalid edge!";
122.             throw new IllegalArgumentException(errMessage);
123.         }
124.         int indexOfVertex1 = edge[0];
125.         int indexOfVertex2 = edge[1];
126.         if (indexOfVertex1 >= size() || indexOfVertex2 >= size() || indexOfVertex1 == indexOfVertex2) {
127.             throw new IllegalArgumentException(String.format(Locale.ENGLISH,
128.                     "invalid edge:[%s,%s]", indexOfVertex1, indexOfVertex2));
129.         }
130.     }
132.     private int size() {
133.         return mVertex.size();
134.     }
136.     public static void main(String[] args) {
137.         GraphByAdjacencyMatrix graph = new GraphByAdjacencyMatrix();
138.         List<Integer> vertex = new ArrayList<>();
139.         vertex.add(23);
140.         vertex.add(11);
141.         vertex.add(54);
142.         vertex.add(6);
143.         vertex.add(16);
144.         vertex.add(32);
145.         vertex.add(41);
146.         List<int[]> edges = new ArrayList<>();
147.         edges.add(new int[]{0, 1});
148.         edges.add(new int[]{0, 4});
149.         edges.add(new int[]{0, 3});
150.         edges.add(new int[]{1, 4});
151.         edges.add(new int[]{1, 2});
152.         edges.add(new int[]{1, 6});
153.         edges.add(new int[]{2, 6});
154.         edges.add(new int[]{3, 5});
155.         edges.add(new int[]{4, 5});
156.         edges.add(new int[]{5, 6});
157.         graph.init(vertex, edges);
158.         System.out.println("\n\ninitiate graph");
159.         graph.print();
161.         graph.addVertex(89);
162.         System.out.println("\n\nafter add vertex 89");
163.         graph.print();
165.         graph.addEdge(new int[]{5,7});
166.         graph.addEdge(new int[]{6,7});
167.         System.out.println("\n\nafter add edge [5,7],[6,7]");
168.         graph.print();
170.         graph.deleteVertex(16);
171.         System.out.println("\n\nafter delete vertex 16");
172.         graph.print();
174.         graph.addEdge(new int[]{1,5});
175.         graph.addEdge(new int[]{4,5});
176.         System.out.println("\n\nafter delete edge [1,5],[4,5]");
177.         graph.print();
178.     }
179. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。