企业的网站如何建立的更合高明网站建设

企业的网站如何建立的,更合高明网站建设,wordpress 发布分离,西宁网站建设多少钱图其实有很多应用#xff0c;现实系统可以用图来建模#xff0c;相应的问题也可以约化为图计算问题。图#xff08;graph#xff09;是一种非线性数据结构#xff0c;由顶点#xff08;vertex#xff09;和边#xff08;edge#xff09;组成。我们可以将图 图G 抽象地…图其实有很多应用现实系统可以用图来建模相应的问题也可以约化为图计算问题。图graph是一种非线性数据结构由顶点vertex和边edge组成。我们可以将图图G 抽象地表示为一组顶点V 和一组边E 的集合。如果将顶点看作节点将边看作连接各个节点的引用指针我们就可以将图看作一种从链表拓展而来的数据结构。相较于线性关系链表和分治关系树网络关系图的自由度更高因而更为复杂。图的表示1邻接矩阵设图的顶点数量为 n 邻接矩阵adjacency matrix使用一个 n乘以n大小的矩阵来表示图每一行列代表一个顶点矩阵元素代表边用 1 或 0表示两个顶点之间是否存在边。设邻接矩阵为 M、顶点列表为 V 那么矩阵元素 M[i,j]1表示顶点 V[i]到顶点 V[j] 之间存在边反之 M[i,j]0表示两顶点之间无边。顶点不能与自身相连此时邻接矩阵主对角线元素没有意义。对于无向图两个方向的边等价此时邻接矩阵关于主对角线对称。将邻接矩阵的元素从 1 和 0替换为权重则可表示有权图。使用邻接矩阵表示图时我们可以直接访问矩阵元素以获取边因此增删查改操作的效率很高时间复杂度均为 O(1)。然而矩阵的空间复杂度为O(n平方) 内存占用较多。基于邻接矩阵的基础操作/* 基于邻接矩阵实现的无向图类 */classGraphAdjMat{ListIntegervertices;// 顶点列表元素代表“顶点值”索引代表“顶点索引”ListListIntegeradjMat;// 邻接矩阵行列索引对应“顶点索引”/* 构造方法 */publicGraphAdjMat(int[]vertices,int[][]edges){this.verticesnewArrayList();this.adjMatnewArrayList();// 添加顶点for(intval:vertices){addVertex(val);}// 添加边// 请注意edges 元素代表顶点索引即对应 vertices 元素索引for(int[]e:edges){addEdge(e[0],e[1]);}}/* 获取顶点数量 */publicintsize(){returnvertices.size();}/* 添加顶点 */publicvoidaddVertex(intval){intnsize();// 向顶点列表中添加新顶点的值vertices.add(val);// 在邻接矩阵中添加一行ListIntegernewRownewArrayList(n);for(intj0;jn;j){newRow.add(0);}adjMat.add(newRow);// 在邻接矩阵中添加一列for(ListIntegerrow:adjMat){row.add(0);}}/* 删除顶点 */publicvoidremoveVertex(intindex){if(indexsize())thrownewIndexOutOfBoundsException();// 在顶点列表中移除索引 index 的顶点vertices.remove(index);// 在邻接矩阵中删除索引 index 的行adjMat.remove(index);// 在邻接矩阵中删除索引 index 的列for(ListIntegerrow:adjMat){row.remove(index);}}/* 添加边 */// 参数 i, j 对应 vertices 元素索引publicvoidaddEdge(inti,intj){// 索引越界与相等处理if(i0||j0||isize()||jsize()||ij)thrownewIndexOutOfBoundsException();// 在无向图中邻接矩阵关于主对角线对称即满足 (i, j) (j, i)adjMat.get(i).set(j,1);adjMat.get(j).set(i,1);}/* 删除边 */// 参数 i, j 对应 vertices 元素索引publicvoidremoveEdge(inti,intj){// 索引越界与相等处理if(i0||j0||isize()||jsize()||ij)thrownewIndexOutOfBoundsException();adjMat.get(i).set(j,0);adjMat.get(j).set(i,0);}/* 打印邻接矩阵 */publicvoidprint(){System.out.print(顶点列表 );System.out.println(vertices);System.out.println(邻接矩阵 );PrintUtil.printMatrix(adjMat);}}邻接表adjacency list使用 n个链表来表示图链表节点表示顶点。第 i个链表对应顶点 i其中存储了该顶点的所有邻接顶点与该顶点相连的顶点。邻接表仅存储实际存在的边而边的总数通常远小于 因此它更加节省空间。然而在邻接表中需要通过遍历链表来查找边因此其时间效率不如邻接矩阵。基于邻接表的基础操作/* 基于邻接表实现的无向图类 */classGraphAdjList{// 邻接表key顶点value该顶点的所有邻接顶点MapVertex,ListVertexadjList;/* 构造方法 */publicGraphAdjList(Vertex[][]edges){this.adjListnewHashMap();// 添加所有顶点和边for(Vertex[]edge:edges){addVertex(edge[0]);addVertex(edge[1]);addEdge(edge[0],edge[1]);}}/* 获取顶点数量 */publicintsize(){returnadjList.size();}/* 添加边 */publicvoidaddEdge(Vertexvet1,Vertexvet2){if(!adjList.containsKey(vet1)||!adjList.containsKey(vet2)||vet1vet2)thrownewIllegalArgumentException();// 添加边 vet1 - vet2adjList.get(vet1).add(vet2);adjList.get(vet2).add(vet1);}/* 删除边 */publicvoidremoveEdge(Vertexvet1,Vertexvet2){if(!adjList.containsKey(vet1)||!adjList.containsKey(vet2)||vet1vet2)thrownewIllegalArgumentException();// 删除边 vet1 - vet2adjList.get(vet1).remove(vet2);adjList.get(vet2).remove(vet1);}/* 添加顶点 */publicvoidaddVertex(Vertexvet){if(adjList.containsKey(vet))return;// 在邻接表中添加一个新链表adjList.put(vet,newArrayList());}/* 删除顶点 */publicvoidremoveVertex(Vertexvet){if(!adjList.containsKey(vet))thrownewIllegalArgumentException();// 在邻接表中删除顶点 vet 对应的链表adjList.remove(vet);// 遍历其他顶点的链表删除所有包含 vet 的边for(ListVertexlist:adjList.values()){list.remove(vet);}}/* 打印邻接表 */publicvoidprint(){System.out.println(邻接表 );for(Map.EntryVertex,ListVertexpair:adjList.entrySet()){ListIntegertmpnewArrayList();for(Vertexvertex:pair.getValue())tmp.add(vertex.val);System.out.println(pair.getKey().val: tmp,);}}}