个人随笔
目录
图的存储结构之邻接多重表(Java实现)
2020-04-22 23:05:41

图的存储结构优缺点对比

优点 缺点
邻接矩阵 实现简单,能同时求任意顶点的出度和入度 在存储稀疏图时会造成空间浪费
邻接表 使用数组链表实现,不会造成空间浪费 不能同时求出任意顶点的出度和入度, 除非同时构建邻接表和逆邻接表,对边 进行操作时需要操作两次
十字链表 使用数组链表实现,不会造成空间浪费 同时可以求出某个顶点的入度和出度 对边进行操作时需要操作两次
邻接多重表 对边的操作进行了优化,操作边的次数由两次 减少到了一次 删除操作较为复杂

邻接多重表,是在邻接表的基础上改进的,因为十字链表是适合有向图的,所以需要一个数据结构适合无向图,也就是邻接多重表。


对于无向图的邻接表,我们更加关注的重点是顶点,那么是不错的选择,但是我们要是关注的是边的操作。
比如:删除一条边,那么我们的操作将变得复杂,我们需要找到这条边的两个顶点,方便去其链表中删除所表示的边。稍微有点麻烦。

改进

我们只出现无向图中对应条数的边表结点,其他的结构,我们全部由指针来联系,所以当我们想要删除一条边时,就只需要删除对应的边表结点。指向她的指针会置为空,他自己产生的指针会消失。就完成了对边的操作。

例如上图,我们若是使用邻接表:是要10个顶点结点去表示5条边,而我们若是使用邻接多重表,只需要5个边结点即可。删除一条边就不存在重复操作。

邻接多重表结构

  1. 其中ivexjvex是指某条边依附的两个顶点在顶点表中的下标。ilink指向依附顶点ivex的下一条边,jlink指向依附顶点jvex的下一条边。

再认识下邻接多重表

  1. 1.表头结点即顶点结点,与邻接表一样是顺序存储。
  2. 2.对于每个顶点结点之后是与之相关联的边结点(与该顶点结点相连的边),而邻接表则是一些与顶点结点相连接的点。
  3. 3.从每个顶点结点开始有一条链表,这条链表将所有与该顶点相连的边都连接了起来。
  4. 4.邻接多重表中边结点的个数就是无向图中边的数量,又因为无向图中的边必然连接两个顶点,所以便边结点结构中的ilinkjlink会连接两个不同的链表。

java实现

  1. /**
  2. * Created by yanfeng-mac on 2017/12/9.
  3. * 无向图的邻接多重表的实现
  4. * 优点: 使用邻接表在对边进行操作时(如删除),需要两次操作,因为一条边在两个链表里面存储,
  5. * 而邻接多重表的优点就在于对边操作时只需要一次操作,这就意味着边只存储一次
  6. */
  7. public class GraphMutiplyTable {
  8. /**
  9. * vName-->顶点名称
  10. * firstEdge-->顶点边链表的头结点
  11. */
  12. private static class Vertex {
  13. private String vName;
  14. private Edge firstEdge;
  15. public Vertex() {}
  16. public Vertex(String name) {
  17. this.vName = name;
  18. }
  19. }
  20. /**
  21. * iVex-->边的其中一个顶点A
  22. * iLink-->边中顶点A的边链表的指针
  23. * jVex-->边的另一个顶点B
  24. * jLink-->边中顶点B的边链表的指针
  25. */
  26. private static class Edge {
  27. private int iVex;
  28. private Edge iLink;
  29. private int jVex;
  30. private Edge jLink;
  31. public Edge() {}
  32. public Edge(int iVex,int jVex) {
  33. this.iVex = iVex;
  34. this.jVex = jVex;
  35. }
  36. }
  37. private static class GraphEdge {
  38. private String vex;
  39. private String otherVex;
  40. public GraphEdge(String vexName,String otherVexName) {
  41. this.vex = vexName;
  42. this.otherVex = otherVexName;
  43. }
  44. }
  45. private List<Vertex> vertexArr;
  46. public void init(String[] vexArr,List<GraphEdge> edgeList) {
  47. initVexArr(vexArr);
  48. initEdge(edgeList);
  49. }
  50. private void initVexArr(String[] vexArr) {
  51. vertexArr = new ArrayList<Vertex>(vexArr.length);
  52. for(int i = 0;i < vexArr.length;i++) {
  53. Vertex vertex = new Vertex(vexArr[i]);
  54. vertexArr.add(vertex);
  55. }
  56. }
  57. private void initEdge(List<GraphEdge> edgeList) {
  58. for(int i = 0;i < edgeList.size();i++) {
  59. GraphEdge graphEdge = edgeList.get(i);
  60. if(contains(graphEdge.vex) && contains(graphEdge.otherVex)) {
  61. //获取顶点的下标
  62. int vIndex = getVexIndex(graphEdge.vex);
  63. int oIndex = getVexIndex(graphEdge.otherVex);
  64. //获取顶点
  65. Vertex vertex = vertexArr.get(vIndex);
  66. Vertex oVertex = vertexArr.get(oIndex);
  67. //构造两个顶点的边
  68. Edge edge = new Edge(vIndex,oIndex);
  69. //头插法插入vertex的边
  70. //这里一定是从iLink出发,因为ivex相同
  71. if(vertex.firstEdge == null) {
  72. vertex.firstEdge = edge;
  73. } else {
  74. Edge vexNextEdge = vertex.firstEdge;
  75. edge.iLink = vexNextEdge;
  76. vertex.firstEdge = edge;
  77. }
  78. //头插法插入oVertex的边
  79. //这里一定是从jLink出发因为jvex相同
  80. if(oVertex.firstEdge == null) {
  81. oVertex.firstEdge = edge;
  82. } else {
  83. Edge oVexNextEdge = oVertex.firstEdge;
  84. edge.jLink = oVexNextEdge;
  85. oVertex.firstEdge = edge;
  86. }
  87. }
  88. }
  89. }
  90. private boolean contains(String vName) {
  91. for(Vertex vertex : vertexArr) {
  92. if(vertex.vName.equals(vName))
  93. return true;
  94. }
  95. return false;
  96. }
  97. private int getVexIndex(String vName) {
  98. for(int i = 0;i < vertexArr.size();i++) {
  99. if(vertexArr.get(i).vName.equals(vName))
  100. return i;
  101. }
  102. return -1;
  103. }
  104. public void print() {
  105. for(Vertex vertex : vertexArr) {
  106. System.out.println("顶点 " + vertex.vName + " 的所有边: ");
  107. int vIndex = getVexIndex(vertex.vName);
  108. Edge cursor = vertex.firstEdge;
  109. while (cursor != null) {
  110. System.out.print(cursor.iVex + "---" + cursor.jVex + " ||");
  111. if(cursor.iVex == vIndex) {
  112. cursor = cursor.iLink;
  113. } else {
  114. cursor = cursor.jLink;
  115. }
  116. }
  117. System.out.println();
  118. }
  119. }
  120. //删除边
  121. /**
  122. * 删除边的整体思路
  123. * 1.找到边上的两个顶点A和B
  124. * 2.分别遍历AB的边链表,直到找到要删除的边S
  125. * 3.分别将边S及边S的前驱边PS的数据存储起来,这里A的要删除的边为cursor,前驱边为preCursor,B的要删除的边为oCursor,前驱边为oPreCursor
  126. * 4.调整链表结构
  127. * @param graphEdge
  128. */
  129. public void remove(GraphEdge graphEdge) {
  130. String vName = graphEdge.vex;
  131. String oName = graphEdge.otherVex;
  132. int vIndex = getVexIndex(vName);
  133. int oIndex = getVexIndex(oName);
  134. //处理边的第一个顶点A
  135. Vertex vertex = vertexArr.get(vIndex);
  136. Edge cursor = vertex.firstEdge;
  137. //指针的前驱
  138. Edge preCursor = null;
  139. while (cursor != null) {
  140. if(cursor.iVex == oIndex || cursor.jVex == oIndex) {
  141. //通过遍历顶点A的所有边,找到边的前驱指针
  142. break;
  143. }
  144. preCursor = cursor;
  145. if(cursor.iVex == vIndex) {
  146. cursor = cursor.iLink;
  147. } else {
  148. cursor = cursor.jLink;
  149. }
  150. }
  151. //处理边的第二个顶点B
  152. Vertex oVertex = vertexArr.get(oIndex);
  153. Edge oCursor = oVertex.firstEdge;
  154. //指针的前驱
  155. Edge oPreCursor = null;
  156. while (oCursor != null) {
  157. if(oCursor.iVex == vIndex || oCursor.jVex == vIndex) {
  158. //通过遍历顶点B的所有边,找到边的前驱指针
  159. break;
  160. }
  161. oPreCursor = oCursor;
  162. if(oCursor.iVex == oIndex) {
  163. oCursor = oCursor.iLink;
  164. } else {
  165. oCursor = oCursor.jLink;
  166. }
  167. }
  168. if(preCursor != null) {
  169. if(preCursor.iVex == vIndex && cursor.iVex == vIndex) {
  170. preCursor.iLink = cursor.iLink;
  171. } else if(preCursor.iVex == vIndex && cursor.jVex == vIndex) {
  172. preCursor.iLink = cursor.jLink;
  173. } else if(preCursor.jVex == oIndex && cursor.iVex == vIndex) {
  174. preCursor.jLink = cursor.iLink;
  175. } else {
  176. preCursor.jLink = cursor.jLink;
  177. }
  178. } else {
  179. if(cursor.iVex == vIndex) {
  180. vertex.firstEdge = cursor.iLink;
  181. } else {
  182. vertex.firstEdge = cursor.jLink;
  183. }
  184. }
  185. if(oPreCursor != null) {
  186. if(oPreCursor.iVex == oIndex && oCursor.iVex == oIndex) {
  187. oPreCursor.iLink = oCursor.iLink;
  188. } else if(oPreCursor.iVex == oIndex && oCursor.jVex == oIndex) {
  189. oPreCursor.iLink = oCursor.jLink;
  190. } else if(oPreCursor.jVex == oIndex && oCursor.iVex == oIndex) {
  191. oPreCursor.jLink = oCursor.iLink;
  192. } else {
  193. oPreCursor.jLink = oCursor.jLink;
  194. }
  195. } else {
  196. if(oCursor.iVex == oIndex) {
  197. oVertex.firstEdge = oCursor.iLink;
  198. } else {
  199. oVertex.firstEdge = oCursor.jLink;
  200. }
  201. }
  202. }
  203. public static void main(String[] args) {
  204. GraphMutiplyTable graph = new GraphMutiplyTable();
  205. String[] vexArr = {"V0","V1","V2","V3"};
  206. GraphEdge edge = new GraphEdge("V0","V1");
  207. GraphEdge edge1 = new GraphEdge("V0","V2");
  208. GraphEdge edge2 = new GraphEdge("V0","V3");
  209. GraphEdge edge3 = new GraphEdge("V1","V2");
  210. GraphEdge edge4 = new GraphEdge("V2","V3");
  211. List<GraphEdge> edgeList = new ArrayList<GraphEdge>();
  212. edgeList.add(edge);
  213. edgeList.add(edge1);
  214. edgeList.add(edge2);
  215. edgeList.add(edge3);
  216. edgeList.add(edge4);
  217. graph.init(vexArr,edgeList);
  218. graph.remove(edge3);
  219. graph.print();
  220. }
  221. }

实现来自:https://www.jianshu.com/p/ae1c8308526d

 821

啊!这个可能是世界上最丑的留言输入框功能~


当然,也是最丑的留言列表

有疑问发邮件到 : suibibk@qq.com 侵权立删
Copyright : 个人随笔   备案号 : 粤ICP备18099399号-2