package algorithm;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Locale;public class GraphByAdjacencyMatrix {private final List<Integer> mVertex = new ArrayList<>();private final List<List<Integer>> mAdjMatrix = new ArrayList<>();/*** 初始化图** @param vertex 顶点列表* @param edges 相邻顶点关系（边）*/public void init(List<Integer> vertex, List<int[]> edges) {mVertex.addAll(vertex);int size = size();for (int i = 0; i < size; i++) {List<Integer> col = new ArrayList<>();for (int j = 0; j < size; j++) {col.add(0);}mAdjMatrix.add(col);}for (int i = 0; i < edges.size(); i++) {int[] edge = edges.get(i);checkEdgeValid(edge, i);mAdjMatrix.get(edge[0]).set(edge[1], 1);mAdjMatrix.get(edge[1]).set(edge[0], 1);}}/*** 添加顶点** @param val 顶点值*/public void addVertex(int val) {List<Integer> row = new ArrayList<>();for (int j = 0; j < size(); j++) {row.add(0);}mVertex.add(val);mAdjMatrix.add(row);for (List<Integer> col : mAdjMatrix) {col.add(0);}}/*** 删除顶点** @param val 顶点值*/public void deleteVertex(int val) {int index = mVertex.indexOf(val);if (index == -1) {System.out.println("can't delete a Non-existent vertices");return;}mVertex.remove(index);mAdjMatrix.remove(index);for (List<Integer> row : mAdjMatrix) {row.remove(index);}}/*** 添加相邻顶点关系（边）** @param edge 边*/public void addEdge(int[] edge) {checkEdgeValid(edge, -1);mAdjMatrix.get(edge[0]).set(edge[1], 1);mAdjMatrix.get(edge[1]).set(edge[0], 1);}/*** 删除相邻顶点关系（边）** @param edge 边*/public void deleteEdge(int[] edge) {checkEdgeValid(edge, -1);mAdjMatrix.get(edge[0]).set(edge[1], 0);mAdjMatrix.get(edge[1]).set(edge[0], 0);}public void print() {System.out.println("\n------------------print graph-------------------");System.out.printf(Locale.ENGLISH, "\n\t%s%s%n"," ".repeat(4), getArrayPrintString(mVertex, " ", " ", " "));System.out.printf(Locale.ENGLISH, "\n");for (int i = 0; i < mAdjMatrix.size(); i++) {List<Integer> row = mAdjMatrix.get(i);Integer vertex = mVertex.get(i);System.out.printf(Locale.ENGLISH, "\t%s%s%n", String.format("%3d:", vertex),getArrayPrintString(row, "[", ", ", "]"));}}private String getArrayPrintString(List<Integer> array, String symbolLeft, String symbolMid, String symbolRight) {StringBuilder sb = new StringBuilder(symbolLeft);for (int i = 0; i < array.size(); i++) {sb.append(String.format("%3d", array.get(i)));if (i < array.size() - 1)sb.append(symbolMid);}sb.append(symbolRight);return sb.toString();}private void checkEdgeValid(int[] edge, int indexAtEdges) {if (edge.length != 2) {String errMessage = indexAtEdges != -1 ? String.format(Locale.ENGLISH,"invalid edge at edges[%s]!", indexAtEdges) : "invalid edge!";throw new IllegalArgumentException(errMessage);}int indexOfVertex1 = edge[0];int indexOfVertex2 = edge[1];if (indexOfVertex1 >= size() || indexOfVertex2 >= size() || indexOfVertex1 == indexOfVertex2) {throw new IllegalArgumentException(String.format(Locale.ENGLISH,"invalid edge:[%s,%s]", indexOfVertex1, indexOfVertex2));}}private int size() {return mVertex.size();}public static void main(String[] args) {GraphByAdjacencyMatrix graph = new GraphByAdjacencyMatrix();List<Integer> vertex = new ArrayList<>();vertex.add(23);vertex.add(11);vertex.add(54);vertex.add(6);vertex.add(16);vertex.add(32);vertex.add(41);List<int[]> edges = new ArrayList<>();edges.add(new int[]{0, 1});edges.add(new int[]{0, 4});edges.add(new int[]{0, 3});edges.add(new int[]{1, 4});edges.add(new int[]{1, 2});edges.add(new int[]{1, 6});edges.add(new int[]{2, 6});edges.add(new int[]{3, 5});edges.add(new int[]{4, 5});edges.add(new int[]{5, 6});graph.init(vertex, edges);System.out.println("\n\ninitiate graph");graph.print();graph.addVertex(89);System.out.println("\n\nafter add vertex 89");graph.print();graph.addEdge(new int[]{5,7});graph.addEdge(new int[]{6,7});System.out.println("\n\nafter add edge [5,7],[6,7]");graph.print();graph.deleteVertex(16);System.out.println("\n\nafter delete vertex 16");graph.print();graph.addEdge(new int[]{1,5});graph.addEdge(new int[]{4,5});System.out.println("\n\nafter delete edge [1,5],[4,5]");graph.print();}
}
