1.概念图（Graph）是一种用来表示对象之间关系的结构。经过数学抽象后的“对象”称为节点或顶点（Vertex,nodeorpoint），节点之间的关系称为边。在绘制图形时，节点通常由一组点或小圆圈表示，它们之间的边是直线或曲线。1.有向图和无向图图中的边可以是有向的，也可以是无向的。例如，在一个图中，如果节点代表参加聚会的人，而边代表握手的两个人，则该图是无方向的，因为A和B握手的事实也意味着B必须与A握手反之，如果A到B的一条边代表A欠B的钱，那么这个图就是有向的，因为“被欠钱”的关系不一定是双向的。前者的图称为无向图，后者称为有向图。同时无向图也可以认为是有向图，即可以想象两个节点之间有一条从A到B的边，同时也有一条从B到A的边，所以从从广义上看，所有的图都可以认为是有向图。2.图的表示教材中的表示：邻接表，邻接矩阵1，邻接表2，邻接矩阵如果图G有n个节点，则邻接矩阵为n*n矩阵，定义为：G[i][j]=1（或权重值），如果是G中的一条边；否则G[i][j]=无穷大。对角线的设置，根据实际情况设置。3.常见的表示法以上两种表示法在实际的写题过程中几乎不会遇到。更多的是给你一个n*3的矩阵[[weight,fromNode,toNode]]，比如[[3,A,B],[2,B,M],[5,A,R]]，第一个第一个值代表权重，第二个值代表from节点，第三个值代表to节点。即，边的直接表示。3.图解思路图的算法不难，但是编码成本比较高（1）首先用你最熟练的方式实现图结构的表达（2）实现所有常用的结构onthefamiliarstructure(3)将面试题提供的图结构转化为你熟悉的图结构，然后调用模板或者重写。图的表示方法有很多种，每次给你的形式可能都不一样，所以有必要抽象出自己的表示方法。以后对于不同的形式，只要写一个可以转换为自定义形式的方法（感觉就是一个适配器），这样就可以在不改变的情况下适应所有的变化，把不熟悉的表示法转换成一个你熟悉的方法/***自定义图信息**@authorJava与算法学习：星期一*/publicclassGraph{/***点集，Key：用户给定的点，Value：自定义点信息*/publicHashMap节点；/***边集*/publicHashSetedges;publicGraph(){this.nodes=newHashMap<>();新哈希集=this.edges<>();}/***将用户输入的边的N*3矩阵转换为自定义图***@parammatrixN*3matrix,[3,0,5],[2,2,5]*/publicstaticGraphcreateGraph(int[][]矩阵){Graphgraph=newGraph();for(int[]m:matrix){//获取用户给定的出入节点的边权重信息和边intweight=m[0];intfrom=m[1];intto=m[2];//添加图的点集信息if(!graph.nodes.containsKey(from)){graph.nodes.put(from,newNode(from));}if(!graph.nodes.containsKey(to)){graph.nodes.put(to,newNode(to));//根据点生成边信息NodefromNode=graph.nodes.get(from);节点toNode=graph.nodes.get(to);边edge=newEdge(weight,fromNode,toNode);//节点信息处理//添加当前节点直连的节点，当前节点直连的边fromNode.nexts.add(toNode);fromNode.edges.add(edge);//入度和出度的修改fromNode.out++;toNode.in++;//添加图边集信息graph.edges.add(edge);}}返回图；}}4.图Set的广度优先和深度优先遍历（存放遍历节点，登记表），起始节点为A，将A放入队列Set(2)弹出队列的顶点M，并打印M的值获取M的所有next邻居节点，检查Set中是否有这些下一个节点，如果没有则放入Set和队列中，如果有则跳过下一个节点（3）继续执行步骤2，直到队列为空/***图宽优先遍历**@authorJava与算法学习：周一*/publicstaticvoidbfs(Nodenode){if(node==null){return;}节点当前=节点；队列<节点>queue=newLinkedList<>();HashSetset=newHashSet<>();queue.add（当前）；设置。添加（当前）；while(!queue.isEmpty()){current=queue.poll();System.out.println(Current.value);for(NodeNext:Current.nexts){if(!Set.contains(next)){queue.add(next);set.add(next);}}}}}}2.深度优先遍历一条路没有走完就一直走，走完了再往回走，看哪些岔路口还没有走完采取。（不能跳出循环，走的地方不能去）（1）准备一个栈（存放当前整个路径），一个Set（存放遍历的节点，注册表），起始节点为A，将A放入栈中并Set，同时打印A的值（入栈时打印）（2）弹出栈顶元素M，遍历所有M的下一个邻居节点，检查Set中是否有这些下一个节点。此时将下一个节点入栈，将next放入Set中，打印next的值（入栈时打印），结束对下一个节点的遍历（即就是，只有一个不在Set中的节点被压入栈中）（3）一直执行步骤2，直到栈为空/***图的深度优先遍历**@authorJava与算法学习：星期一*/publicstaticvoiddfs(Nodenode){if(node==null){return;}Stackstack=newStack<>();HashSetset=newHashSet<>();当前节点=节点；堆栈。添加（当前）；设置。添加（当前）；.println(当前值);while(!stack.isEmpty()){current=stack.pop();for(Nodenext:current.nexts){if(!set.contains(next)){staddack(Current);stack.add（下一步）；set.add（下一步）；system.out.println(next.value);//只输入一个节点的栈break;}}}}}}有向无环图的拓扑排序有一个拓扑排序（1）打印当前图中的输入度数为0的节点（多个为0，谁都可以先打印）(2)从图中移除打印的节点（自然地，与这些节点直接相连的边也被移除）(3)一直执行1、2步直到图的节点为空/***图的拓扑排序**@authorJava与算法学习：周一*/publicstaticListtopologySort(Graphgraph){//Key：节点，Value：剩余输入度HashMapinMap=newHashMap<>();//存储度数为0的节点QueuezeroInQueue=newLinkedList<>();for(Nodenode:graph.nodes.values()){//将初始给定图中的所有节点放入inMapinMap.put(node,node.in);if(node.in==0){//初始入度为0的节点zeroInQueue.add(node);}}}Listresult=newArrayList<>();while(!zeroInQueue.isEmpty()){节点当前=zeroInQueue.poll();结果.添加（当前）；extnfor:(current.nexts){//将遍历节点的邻居节点的入度减一（可以理解为从图中移除当前节点）inMap.put(next,inMap.get（下一个）-1）；如果（inMap.get（下一个）==0）{dd（下一个）；}}}}}returnresult;}五、最小生成树算法需要一个无向图，在所有点都连通的情况下，所有权值和最小的边构成的树1.Kruskal算法使用搜索集(1)总是从权值最小的边开始，然后依次寻找权值递增的边(权值相等取其一)(2)如果当前边进入最小代树的集合中不会有环，所以需要当前边；否则丢弃(3)找到所有边后，得到最小生成树的集合/***Kruskal算法-使用和搜索**@authorJava与算法学习：星期一*/publicstaticSetkruskal(Graphgraph){UnionFindunionFind=newUnionFind(graph.nodes.values());//基于权值的小根堆PriorityQueuesmallEdgeQueue=newPriorityQueue<>((a,b)->a.weight-b.weight);//将所有边放入小根堆for(Edgeedge:graph.edges){smallEdgeQueue.offer(edge);}Setresult=newHashSet<>();while(!smallEdgeQueue.isEmpty()){边edge=smallEdgeQueue.poll();//小根堆顶部的边对应的节点在加入结果集之前不会成环（即两个点不在同一个集合中），否则丢弃if(!unionFind.isSameSet(edge.from,edge.to)){结果.add(edge);unionFind.union(edge.from,edge.to);}}}returnresult;}2.Prim算法(1)可以从任意一个节点开始寻找最小生成树(2)在选中的点上添加一个点后，解锁所有新的边(3)选择其中最小的边所有解锁的边，然后看这条边加到解锁点后是否会成环（4）如果是，则舍弃当前边，返回步骤3;如果不是，则保留当前边，解锁这条边指向的点，把这条边加到结果中，所有点都解锁后返回步骤2（5），得到最小生成树/***minimumSpanningTree算法-Prim算法**@authorJava和算法学习：周一*/publicstaticSetprim(Graphgraph){Collectionnodes=graph.nodes.values();如果（节点。isEmpty（））{返回空；}//解锁的边按照权重值标准放入小根堆PriorityQueuesmallEdgeQueue=newPriorityQueue<>((a,b)->a.weight-b.weight);//解锁点SetnodeSet=newHashSet<>();Set结果=newHashSet<>();//1.从任意节点开始寻找最小生成树for(Nodenode:nodes){If(!NodeSet.Contains(node)){//点解锁nodeset.add(node);//2.所有边解锁for(edgeedge:node.edges){SmalledgeQueue.offer(EDGE);}}//3.在所有未锁定的边中选择最小的边，然后看这条边添加到选择的点后是否会形成一个环while(!smallEdgeQueue.isEmpty()){//从未锁定的边中弹出Edge中的最小边currentEdge=smallEdgeQueue.poll();节点tonode=urrentge.to;//边的点未解锁，则解锁if(!NodeSet.Contains(Tonode)){nodeSet.add(tonode);result.add(Currentedge);Allthesideunlockfor(edgeedge:tonode.edges){Smalledgequeue.offer(edge);}//边的方向已经解锁，直接放弃这条边}//为了防止森林，它isnotbreak//如果明确知道不会有森林（或者不需要阻止森林），就可以break//break;}}returnresult;}六、迪杰斯特拉算法（Dijkstraalgorithm）1.意思是以一个顶点为源节点，然后求出从一个顶点到图中所有其他节点的最短路径，不考虑不可达节点。该算法解决了图上的加权单源最短路径问题。2.常用于路由、寻路、交通和规划。例如，如果图中的顶点代表城市，边上的权重代表城市之间的行驶距离，则该算法可用于寻找两个城市之间的最短路径。应该注意的是，Dijkstra算法适用于没有负权重的有向图。3、代码思路（1）定义一个Map，存储指定点A到目标点的距离。从指定的A点开始，到目标点A的距离为0。到A一步可以直接到达的点的距离等于边上的权重值，到不能直接到达的点的距离到达是无限的。更新地图。A点被锁定。(2)从Map中找到到目标点权重最小的边B，一步中B到C点的距离加上第一步得到的A到B的距离小于A到B的距离C在第一步得到的距离[(A->B)+(B->C)<(A->C)]更新Map中到C的距离，否则保持不变；根据这个条件，它一直在一步步检查从B点可以直接到达的所有距离。检查完点与点之间的距离后，将锁定B点。(3)执行步骤2，直到所有点都被锁定。/***Dijkstra算法-原版**@authorJava与算法学习：星期一*/publicstaticMapdijkstra1(Nodehead){//head到目标点的距离，key：目标点，value:距离MapdistanceMap=newHashMap<>();//自己到自己的最短距离一定是0distanceMap.put(head,0);//锁定点SetselectedNode=newHashSet<>();//MinNode此时一定是头节点minNode=getMinDistanceFromUnSelectedNode(distanceMap,selectedNode);while(minNode!=null){//head到minNodeMap的最短距离intdistance.getdistance=distance(minNode);for(Edgeedge:minNode.edges){节点toNode=edge.to;if(!distanceMap.containsKey(toNode)){//如果toNode不存在，此时头到头的最短距离为到minNode的最短距离+这条边的权重值distanceMap.put(toNode,distance+边.权重);}else{//toNode存在，则更新最短距离distanceMap.minto.Mapd.Mapd.put(toNode),distance+edge.weight));????????????}????????}????????//?minNode使命完成（minNode所有直接到的点都遍历完成）????????selectedNode.add(minNode);????????//?重新找出下一个minNode????????minNode?=?getMinDistanceFromUnSelectedNode(distanceMap,?selectedNode);????}????return?distanceMap;}4,UsetheenhancedheapoptimizationYoucanusetheenhancedheapimprovementtoadjustthetimecomplexityoffindingthepointwiththeshortestdistancefromtheMaptotheunlockedtargetpointfromO(N)toO(logN)level./***改进的dijkstra算法**从head开始，把head能到达的所有节点，生成到每个节点的最短路径记录并返回**@authorJava与算法学习：Monday*/publicstaticMapdijkstra1(Nodehead,intsize){//使用增强堆优化NodeHeapnodeHeap=newNodeHeap(size);//head到head的距离必须为0nodeHeap.addOrUpdateOrIgnore(head,0);Mapresult=newHashMap<>();while(!nodeHeap.isEmpty()){NodeRecord记录=nodeHeap.pop();节点node=record.node;intdistance=record.distance;(geednode.edges){nodeHeap.addOrUpdateOrIgnore(edge.to,edge.weight+distance);}result.put(节点，距离);}返回结果；}VII.本文所有代码Github地址：https://github.com/monday-pro/algorithm-study/tree/master/src/basic/graphGitee：https://gitee.com/monday-pro/algorithm-study/tree/master/src/basic/graph
