图的表示以及基础操作

图其实有很多应用，现实系统可以用图来建模，相应的问题也可以约化为图计算问题。

图（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{List<Integer>vertices;// 顶点列表，元素代表“顶点值”，索引代表“顶点索引”List<List<Integer>>adjMat;// 邻接矩阵，行列索引对应“顶点索引”/* 构造方法 */publicGraphAdjMat(int[]vertices,int[][]edges){this.vertices=newArrayList<>();this.adjMat=newArrayList<>();// 添加顶点for(intval:vertices){addVertex(val);}// 添加边// 请注意，edges 元素代表顶点索引，即对应 vertices 元素索引for(int[]e:edges){addEdge(e[0],e[1]);}}/* 获取顶点数量 */publicintsize(){returnvertices.size();}/* 添加顶点 */publicvoidaddVertex(intval){intn=size();// 向顶点列表中添加新顶点的值vertices.add(val);// 在邻接矩阵中添加一行List<Integer>newRow=newArrayList<>(n);for(intj=0;j<n;j++){newRow.add(0);}adjMat.add(newRow);// 在邻接矩阵中添加一列for(List<Integer>row:adjMat){row.add(0);}}/* 删除顶点 */publicvoidremoveVertex(intindex){if(index>=size())thrownewIndexOutOfBoundsException();// 在顶点列表中移除索引 index 的顶点vertices.remove(index);// 在邻接矩阵中删除索引 index 的行adjMat.remove(index);// 在邻接矩阵中删除索引 index 的列for(List<Integer>row:adjMat){row.remove(index);}}/* 添加边 */// 参数 i, j 对应 vertices 元素索引publicvoidaddEdge(inti,intj){// 索引越界与相等处理if(i<0||j<0||i>=size()||j>=size()||i==j)thrownewIndexOutOfBoundsException();// 在无向图中，邻接矩阵关于主对角线对称，即满足 (i, j) == (j, i)adjMat.get(i).set(j,1);adjMat.get(j).set(i,1);}/* 删除边 */// 参数 i, j 对应 vertices 元素索引publicvoidremoveEdge(inti,intj){// 索引越界与相等处理if(i<0||j<0||i>=size()||j>=size()||i==j)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：该顶点的所有邻接顶点Map<Vertex,List<Vertex>>adjList;/* 构造方法 */publicGraphAdjList(Vertex[][]edges){this.adjList=newHashMap<>();// 添加所有顶点和边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)||vet1==vet2)thrownewIllegalArgumentException();// 添加边 vet1 - vet2adjList.get(vet1).add(vet2);adjList.get(vet2).add(vet1);}/* 删除边 */publicvoidremoveEdge(Vertexvet1,Vertexvet2){if(!adjList.containsKey(vet1)||!adjList.containsKey(vet2)||vet1==vet2)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(List<Vertex>list:adjList.values()){list.remove(vet);}}/* 打印邻接表 */publicvoidprint(){System.out.println("邻接表 =");for(Map.Entry<Vertex,List<Vertex>>pair:adjList.entrySet()){List<Integer>tmp=newArrayList<>();for(Vertexvertex:pair.getValue())tmp.add(vertex.val);System.out.println(pair.getKey().val+": "+tmp+",");}}}```