java - 邻接矩阵删除顶点

Question

我正在尝试用 Java 实现邻接矩阵。

我正在使用 ArrayList 来存储作为字母标签的顶点。然后我根据 ArrayList 中的顶点索引构建矩阵。

假设无向图是

A-B

将A、B存入数组列表。

矩阵应该是

[[false,true],[true,false]]

请问删除一个顶点应该怎么做？

目前，我删除了顶点的所有边，对于下一步，我有 2 个想法

1. 根据顶点索引在 ArrayList 中将值设置为 null。
2. 根据索引从 ArrayList 中删除顶点，然后更改二维矩阵 boolean 数组。如果是这样，我应该在那里更改什么，删除行和列？

是的，我将实现 bfs 或一些函数，例如计算 2 个顶点之间的短路。

感谢您提供的任何建议和学习资源。

这是我的代码:

    public class AdjMatrix <T extends Object>
    {
        // List to store all vertexs
        private ArrayList<T> vertList;

        // graph in 2d array
        private boolean[][] adjMatrix;

        public AdjMatrix() {
            vertList = new ArrayList<T>();
            adjMatrix = new boolean[4000][4000];
        } 

        public void addVertex(T vertLabel) {
            vertList.add(vertLabel);
        } 

        public void addEdge(T srcLabel, T tarLabel) {
            int srcIndex = vertList.indexOf(srcLabel);
            int tarIndex = vertList.indexOf(tarLabel);
            adjMatrix[srcIndex][tarIndex] = true;
            adjMatrix[tarIndex][srcIndex] = true;
        } 

        public ArrayList<T> neighbours(T vertLabel) {

            ArrayList<T> neighbours = new ArrayList<T>();
            int vertIndex = vertList.indexOf(vertLabel);
            int[] vertEdges = adjMatrix[vertIndex];
            for(int i = 0; i < vertEdges.length; i++){
                if(vertEdges[i]){
                    neighbours.add(vertList.get(i));
                }
            }
            return neighbours;
        } 

        public void removeVertex(T vertLabel) {
            // what should I do there?
            ArrayList<T> neighbours = neighbours(vertLabel);
            for (T neighbour: neighbours
                 ) {
                removeEdge(vertLabel,neighbour);
            }
        }

        public void removeEdge(T srcLabel, T tarLabel) {
            int srcIndex = vertList.indexOf(srcLabel);
            int tarIndex = vertList.indexOf(tarLabel);
            adjMatrix[srcIndex][tarIndex] = false;
            adjMatrix[tarIndex][srcIndex] = false;       
        } 

        public void printVertices(PrintWriter os) {
            String result = "";
            for (T vert :
                    vertList) {
                result += vert + " ";
            }
            os.println(result);
        } 

        public void printEdges(PrintWriter os) {
            for (T vert :
                    vertList) {
                ArrayList<T> neighbours = neighbours(vert);
                for (T neighbour :
                        neighbours) {
                    os.println(vert + " " + neighbour);
                }
            }
        }
    }

Answer 1

“删除”是什么意思？

如果真的要delete-delete，只删除删除节点所在的行和列，其余节点重新编号即可。