数据结构十字链表怎么画,数据结构数组代码

数据结构图论01邻接矩阵、邻接表代码

数据结构图论02交叉链表详细代码

阅读前请理解邻接表数据结构图论01邻接矩阵、邻接表代码

数据结构上的数组链表可以节省空间和方便地删除，但计算顶点的度数很麻烦。问题是十字链表就是解决计算顶点入度(有多少条边通向此节点)

顶点Vertex的结构

data :顶点的具体数据信息firstIn (指向该顶点的(垂直)边链表的一个节点firstOut (指向其他顶点的)横向)边链表的第一个节点边edge的结构

fromVertex :箭头所指向顶点(例如a顶点) toVertex :箭头所指向的顶点) b顶点)fromEdge：指向目标点是fromVertex的边，这里就是竖向链表的核心实现（绿色的2条边DA,CA)toEdge ) fromVertex为基础，在其他顶点的边(红色的两边、AC、)

为了解决计算顶点入度的问题，在用横向链表表示度的基础上(红色边)添加十字链表的结构(绿色边)，可以在纵向链表中轻松获得入度。

红色箭头是横向显示度，(与相邻链表一样)竖向链表表示入度(纵向链表是十字链表的关键)代码实现图形

import java.util.ArrayList； /** *交叉链接列表* @ authorjarvan * @版本1.0 * @ create 2020/11/2516336043 */publicclasscrosslinkedlistgraphe { classion Edge第一次输出；公共vertex (edata，Edge firstIn，Edge firstOut ) { this.data=data； this.firstIn=firstIn； this.firstOut=firstOut； } } class Edge{ int fromVertex； int toVertex； Edge fromEdge； Edge toEdge；智能微信； publicedge(intfromVertex，int toVertex，Edge fromEdge，Edge toEdge，int weight ) { this.fromVertex=fromVertex； this.toVertex=toVertex； this.fromEdge=fromEdge； this.toEdge=toEdge； this.weight=weight； } }私密int numofvertices；私密int maxofvertices；私有阵列验证验证验证； publiccrosslinkedlistgraph (intmaxofvertices ) this.maxofvertices=maxofvertices； this.vertices=new ArrayList (maxofvertices )； numOfVertices=0； }publicbooleanputvertex(edata ) if ) numofverticesmaxofvertices ) vertices.add ) new vertex (data，null，null ) )； numOfVertices；返回真； }返回假； } publicegetvertexdata (intvertexindex ) if ) vertexindexmaxofvertices (return vertices.get ) vertexindex ).data； }返回空值；插入(} /** *边，旁边的所有列表均为(/publicbooleanputedge (intfromvertexindex，

int toVertexIndex,int weight){ if (fromVertexIndex < maxOfVertices && toVertexIndex < maxOfVertices){ Vertex fromVertex = vertices.get(fromVertexIndex); Edge newEdge = new Edge(fromVertexIndex,toVertexIndex,null,null,weight); //插入横向链表 if (fromVertex.firstOut == null) { fromVertex.firstOut = newEdge; //插入竖向链表 return insertFromEdgeLinkedList(fromVertex.firstOut); } //遍历元素然后将元素放到尾部 Edge edge = fromVertex.firstOut; while (edge.toEdge != null) { edge = edge.toEdge; } edge.toEdge = newEdge; //插入竖向链表 return insertFromEdgeLinkedList(edge.toEdge); } return false; } /** * 将插入竖向链表提升为一个方法 */ private boolean insertFromEdgeLinkedList(Edge edge){ if ( edge!=null){ //获得新增加的指向的顶点 Vertex toVertex = vertices.get(edge.toVertex); if (toVertex.firstIn==null){ //如果指向的顶点没有竖向链表就直接将第一个边赋值给竖向链表 toVertex.firstIn = edge; return true; } Edge fromEdge = toVertex.firstIn; while (fromEdge.fromEdge!=null){ fromEdge = fromEdge.fromEdge; } fromEdge.fromEdge = edge; return true; } return false; } public void print(){ for (Vertex vertex : vertices) { Edge edge = vertex.firstOut; System.out.print(vertex.data+": "); while (edge!=null){ System.out.print(vertices.get(edge.fromVertex).data + " --> " +vertices.get(edge.toVertex).data +" weight="+edge.weight +"; "); edge = edge.toEdge ; } System.out.println(); } } public void printVertexFromEdge(int fromVertex){ System.out.println("====print vertex from edges===="); Vertex vertex = vertices.get(fromVertex); Edge firstIn = vertex.firstIn; if (vertex.firstIn!=null){ Edge fromEdge = vertex.firstIn; while (fromEdge!=null){//这里debug的时候录为null System.out.println(vertices.get(fromEdge.fromVertex).data +" --> "+ vertices.get(fromEdge.toVertex).data); fromEdge = fromEdge.fromEdge; } }else { System.out.println("null of firstIn"); } }}

test

CrossLinkedListGraph<String> graph = new CrossLinkedListGraph<>(4);graph.putVertex("A");graph.putVertex("B");graph.putVertex("C");graph.putVertex("D");graph.putEdge(0,1,4);graph.putEdge(0,2,3);graph.putEdge(2,3,5);graph.putEdge(2,0,5);graph.putEdge(3,0,6);graph.putEdge(3,1,6);graph.print();//获得一个点的fromEdge然后打印graph.printVertexFromEdge(0);

result

A: A --> B weight=4; A --> C weight=3; B: C: C --> D weight=5; C --> A weight=5; D: D --> A weight=6; D --> B weight=6; ====print vertex from edges====C --> AD --> AProcess finished with exit code 0

数据结构优点缺点邻接矩阵二维数组，实现简单，能同时求出顶点的出度和入度稀疏图造成的空间浪费邻接表数组+链表，不会空间浪费不能同时求出出度和入度；对边的操作需要2次十字链表横竖十字链表：可以同时求出出度和入度对边的操作需要2次邻接多重表对边的操作减少到了一次删除较为复杂