图的基本操作（基于邻接矩阵

本文是数据结构（Java版）中国工信出版集团一书的读书笔记

图的插入操作包括插入顶点和插入边

1.weight范围：weight 在0到正无穷之间。若越界，则无边，取值是正无穷

2.若I、j满足：0≤I，j<图的顶点数，I≠j，则设权值为weight，i、j越界，抛出异常

3.i==j，自身环，抛出无效参数异常

public void insertEdge(int i,int j,int weight){if(i != j){if(weight<=0 || weight >MAX_WEIGHT){weight = MAX_WEIGHT;this.matrix.set(i,j,weight);}}else throw new IllegalArgumentException("不能插入自身环");
}

插入顶点：

1.若插入元素x，其序号为I，i = n - 1；n为图顶点数。若顶点顺序表容量不足，顺序表将自动扩充容量

2.在图的邻接矩阵中，初始化x所在行、列，主对角线元素值为0，其他元素值为正无穷。若邻接矩阵容量不足，则扩充邻接矩阵容量至2倍，再复制原矩阵元素。        

插入顶点的方法：

public int insertVertex(T x){int i = this.vertexlist.insert(x);//顶点顺序表尾插入x，返回x序号，自动扩容if(i>= this.matrix.getRows()){this.matrix.setRowsColumns(i+1,j+1);}for(int j = 0;j<i;j++){//将新插入结点之前的所有结点与i结点建立联系this.matrix.set(i,j,MAX_WEIGHT);this.matrix.set(j,i,MAX_WEIGHT);}return i;
}

删除一条边的方法：

public void removeEdge(int i,int j){if(i != j){this.matrix.set(i,j,MAX_WEIGHT);}
}public void removeEdge(Triple edge)
{this.removeEdge(edge.row,edge.column);//删除一条边，忽略权值
}

删除顶点的方法：

1.删除顶点顺序表中第I个元素，即I+1~n-1元素向前移动，图的顶点数-1.

2.删除邻接矩阵中与顶点i相关的所有边，即将第I+1~n-1行元素全部向上移动一行。将第I+1~n-1列元素全部向左移动一列

public void removeVertex(int i){int n = this.vertexCount();if(i>=0 && i<n){this.vertexlist.remove(i);for(int j = i+1;j<n;j++){for(int k = 0;k<n;k++){this.matrix.set(j-1,k,this.matrix.get(j,k));}}for(int j = 0;j<n;j++){for(int k = i+1;k<n;k++){this.matrix.set(j,k-1,this.matrix.get(j,k));}}this.matrix.setRowsColumns(n-1,n-1);}else throw new IndexOutOfBoundsException("i="+i);
}