邻接矩阵删除顶点

Question

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

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

假设无向图是

A-B

将A、B存入数组列表

矩阵应该是

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

请问删除顶点怎么办？

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

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

是的，我将实现 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-delete，只需删除删除节点的行和列，并对剩余节点重新编号。

邻接矩阵删除顶点

Adjacency matrix deleting vertex

java

algorithm

graph

adjacency-matrix