图的基本操作（基于邻接表

public class AdjListGraph<T> extends AbstractGraph<T>{protected LinkedMatrix adjlist;//图的邻接表public AdjListGraph(int length){super(length);//构造长度为length的空顺序表this.adjlist = new LinkedMatrix(length,length);//构造length×length矩阵}//以下是构造方法public AdjListGraph(){this(10);//构造空图，顶点数为0，边数为0，顶点顺序表和邻接矩阵的默认容量是10}public AdjListGraph(T[] vertices)//以顶点集合vertices构造图{this(vertices.length);for(int i = 0;i<vertices.length;i++){this.insertVertex(vertices[i]);}}public AdjListGraph(T[] vertices,Triple[] edges){//以vertices顶点集合和edges边集合this(vertices);for(int j = 0;j<edges.length;j++){this.insertEdge(edges[i]);}}public String toString(){return super.toString()+"出边表：\n"+this.adjlist.toString();}
}

基于邻接表的插入边操作

1.weight范围：0到正无穷。如果weight越界，视为无边，取值是0

2.若I、j满足：0≤I，j<图的顶点数，I≠j，则在邻接表第I条边单链表中查找表示<vi,vj>的结点，根据查找结果和weight取值，分别执行插入、替换、删除操作

3.若I、j越界，抛出序号越界异常。若I==j，表示自身环。抛出无效参数异常

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

插入顶点操作：

public int insertVertex(T x){int i = this.vertexlist.insert(x);if(i>=this.adjlist.getRows()){this.adjlist.setRowsColumns(i+1,i+1);}return i;
}

public void removeEdge(int i,int j){if(i != j)this.adjlist.set(new Triple(i,j,0));//第i条边单链表中删除边结点
}
public void removeEdge(Triple edge){this.removeEdge(edge.row,edge.column);
}

删除顶点：

1.在顶点顺序表中删除第I个元素，图顶点数－1

2.在邻接表中删除所有与顶点vi相关联的边，包括以下操作：

   1>在第I条以外的边单链表中，删除所有以顶点I为终点的边结点

   2>在行指针顺序表中，删除第I个元素，即删除第I条边单链表

   3>在所有边单链表中，将边结点中大于I的顶点序号-1

public void removeVertex(int i){int n = vertexCount();if(i>=0 && i<n){SortedSinglyList<Triple> link = this.adjlist.rowlist.get(i);//获取要删除的边单链表for(Node<Triple> p = link.head.next; p != null;p = p.next){this.removeEdge(p.data.toSymmetry());//删除与p结点对称的边}n--;//顶点数-1this.adjlist.rowlist.remove(i);//删除行指针顺序表的第i条边单链表，其后单链表上移this.adjlist.setRowsColumns(n,n);//设置矩阵行列数，少一行for(int j = 0;j<n;j++){link = this.adjlist.rowlist.get(j);for(Node<Triple> p = link.head.next; p != null; p = p.next){if(p.data.row>i){p.data.row--;}if(p.data.column>i){p.data.column--;}}}this.vertexlist.remove(i);}else throw new IndexOutOfBoundsException("i="+i);
}