0001 /* 0002 * 基于邻接边表实现图结构 0003 */ 0004 0005 package dsa; 0006 0007 public class Graph_List implements Graph { 0008 //变量 0009 protected List E;//容器:存放图中所有边 0010 protected List V;//容器:存放图中所有顶点 0011 0012 //构造方法 0013 public Graph_List() { E = new List_DLNode(); V = new List_DLNode(); } 0014 0015 //取图的边表、顶点表 0016 protected List getE() { return E; } 0017 protected List getV() { return V; } 0018 0019 //取图中顶点、边的数目 0020 public int vNumber() { return V.getSize(); } 0021 public int eNumber() { return E.getSize(); } 0022 0023 //取图中所有顶点、顶点位置的迭代器 0024 public Iterator vertices() { return V.elements(); } 0025 public Iterator vPositions() { return V.positions(); } 0026 0027 //返回图中所有边、边位置的迭代器 0028 public Iterator edges() { return E.elements(); } 0029 public Iterator ePositions() { return E.positions(); } 0030 0031 //检测是否有某条边从顶点u指向v 0032 public boolean areAdjacent(Vertex u, Vertex v) 0033 { return (null != edgeFromTo(u, v)); } 0034 //取从顶点u指向v的边,若不存在,则返回null 0035 public Edge edgeFromTo(Vertex u, Vertex v) { 0036 for (Iterator it = u.outEdges(); it.hasNext();) {//逐一检查 0037 Edge e = (Edge)it.getNext();//以u为尾的每一条边e 0038 if (v == e.getVPosInV(1).getElem())//若e是(u, v),则 0039 return e;//返回该边 0040 } 0041 return null;//若不存在这样的(u, v),则返回null 0042 } 0043 0044 //将顶点v从顶点集中删除,并返回之 0045 public Vertex remove(Vertex v) { 0046 while (0 < v.outDeg())//将以v为尾的所有边 0047 remove((Edge)(((Vertex_List)v).outEdges.first()).getElem());//逐一删除 0048 while (0 < v.inDeg())//将以v为头的所有边 0049 remove((Edge)(((Vertex_List)v).inEdges.first()).getElem());//逐一删除 0050 return (Vertex)V.remove(v.getVPosInV());//在顶点表中删除v 0051 } 0052 //将边e从边集中删除,并返回之 0053 public Edge remove(Edge e) { 0054 ((Vertex_List)e.getVPosInV(0).getElem()).outEdges.remove(e.getEPosInI(0));//从起点的出边表中删除e 0055 ((Vertex_List)e.getVPosInV(1).getElem()).inEdges.remove(e.getEPosInI(1));//从终点的入边表中删除e 0056 return (Edge)E.remove(e.getEPosInE());//从边表中删除e 0057 } 0058 0059 //在顶点集V中插入新顶点v,并返回其位置 0060 public Position insert(Vertex v) { return V.insertLast(v); } 0061 //在边集E中插入新边e,并返回其位置 0062 public Position insert(Edge e) { return E.insertLast(e); } 0063 }