流量购买网站萍乡网站建设行吗

流量购买网站,萍乡网站建设行吗,怎么在ppt上做网站,广东东莞市文章目录1. 引言2. 自定义通用图结构设计2.1 结构定义与设计意图3. 两种图遍历3.1 BFS#xff08;宽度优先遍历#xff09;3.2 DFS#xff08;深度优先遍历#xff09;4. 拓扑排序4.1 方法一#xff1a;入度法#xff08;Kahn / BFS 思想#xff09;4.2 方法二#xff…文章目录1. 引言2. 自定义通用图结构设计2.1 结构定义与设计意图3. 两种图遍历3.1 BFS宽度优先遍历3.2 DFS深度优先遍历4. 拓扑排序4.1 方法一入度法Kahn / BFS 思想4.2 方法二DFS 深度法4.3 方法三DFS 点次法5. 最小生成树一Kruskal5.1 核心思路5.2 关键实现细节6. 最小生成树二Prim6.1 核心思路6.2 关键实现细节7. 最短路径Dijkstra朴素实现7.1 核心思路7.2 关键实现细节1. 引言很多图类题目会给出“各式各样”的图表示邻接表、边集、矩阵、甚至是自定义节点结构。你这部分代码的核心目标很明确先把题目给的任意图结构统一转换成一套通用图结构点/边/图再基于该结构实现两种遍历BFS/DFS最后实现拓扑排序。其中“通用结构 标准算法模板”的组合能显著降低不同题目之间的切换成本。​2. 自定义通用图结构设计2.1 结构定义与设计意图定义了三个核心对象Node点包含value并维护入度in/ 出度out以及两套邻接信息nexts直接邻居点列表便于遍历BFS/DFS快速走边edges从该点出发的边列表便于需要边权/边对象的算法例如最小生成树、最短路等扩展方向Edge边包含weight与from/to表达“带权有向边/无向边都能映射”的统一模型Graph图用HashMapInteger, Node管理点集用HashSetEdge管理边集这套结构的优势在于题目无论给的是“点 邻居”还是“边列表”最终都能汇总到 Node/Edge/Graph 上遍历与后续算法只依赖这一层抽象。importjava.util.ArrayList;publicclassNode{publicintvalue;publicintin;publicintout;publicArrayListNodenexts;publicArrayListEdgeedges;publicNode(intvalue){this.valuevalue;in0;out0;nextsnewArrayList();edgesnewArrayList();}}publicclassEdge{publicintweight;publicNodefrom;publicNodeto;publicEdge(intweight,Nodefrom,Nodeto){this.weightweight;this.fromfrom;this.toto;}}importjava.util.HashMap;importjava.util.HashSet;publicclassGraph{publicHashMapInteger,Nodenodes;publicHashSetEdgeedges;publicGraph(){nodesnewHashMap();edgesnewHashSet();}}​3. 两种图遍历3.1 BFS宽度优先遍历这个 BFS 代码强调了一个非常关键的细节“进队时标记”也就是节点一旦入队就立刻加入 visitedHashSet。这样可以从源头避免同一节点被重复入队尤其是在存在环或多路径指向同一节点时更重要。执行流程起点入队同时标记 visited弹出队头并“打印”遍历时机在出队将未访问过的邻居入队并立刻标记importjava.util.HashMap;importjava.util.HashSet;importjava.util.LinkedList;importjava.util.Queue;publicclassGraphBFS{publicvoidgraphBFS(Nodestart){if(startnull)return;QueueNodequeuenewLinkedList();HashSetNodehsnewHashSet();queue.add(start);hs.add(start);while(!queue.isEmpty()){Nodepollqueue.poll();System.out.print(poll.value, );for(Nodecurr:poll.nexts){if(!hs.contains(curr)){queue.add(curr);hs.add(curr);}}}}}3.2 DFS深度优先遍历这里的 DFS 写法很有代表性它不是“纯粹弹栈就打印”的版本而是采用一种更贴近递归的栈模拟策略起点入栈后立刻打印遍历时机在入栈每次弹出curr后找到一个未访问的next把curr再压回去用于回溯再压入next继续深入打印next并标记break保证“沿着一条路走到底”的深度优先特性这个“curr 回压 break”是模拟递归调用栈的一种经典技巧。importjava.util.HashSet;importjava.util.Stack;publicclassGraphDFS{publicvoidgraphDFS(Nodestart){if(startnull)return;StackNodestacknewStack();HashSetNodehsnewHashSet();stack.add(start);System.out.print(start.value, );hs.add(start);while(!stack.isEmpty()){Nodecurrstack.pop();for(Nodenext:curr.nexts){if(!hs.contains(next)){stack.add(curr);stack.add(next);System.out.print(next.value, );hs.add(next);break;}}}}}​4. 拓扑排序这里给了三种拓扑排序思路入度法Kahn、DFS 深度法、DFS 点次法不推荐。它们针对的“题目给定结构”是DirectedGraphNode(label neighbors)属于常见的题目输入模型。4.1 方法一入度法Kahn / BFS 思想核心点是用哈希表记录入度并维护一个“入度为 0 的队列 zero”。实现步骤很清晰第一次遍历把所有点入inDegree初始化入度为 0第二次遍历沿邻接关系累加入度将所有入度为 0 的点入队不断弹出队头加入结果并把它指向的邻居入度减 1减到 0 则入队这本质上就是“每次选一个当前没有前置依赖的点输出”。importjava.lang.reflect.Array;importjava.util.ArrayList;importjava.util.HashMap;importjava.util.LinkedList;importjava.util.Queue;publicclassTopologicalOrder1{publicstaticclassDirectedGraphNode{publicintlabel;publicArrayListDirectedGraphNodeneighbors;publicDirectedGraphNode(intx){labelx;neighborsnewArrayListDirectedGraphNode();}}publicArrayListDirectedGraphNodetopSort(ArrayListDirectedGraphNodegraph){HashMapDirectedGraphNode,IntegerinDegreenewHashMap();QueueDirectedGraphNodezeronewLinkedList();ArrayListDirectedGraphNoderstnewArrayList();for(DirectedGraphNodecurr:graph){inDegree.put(curr,0);}for(DirectedGraphNodecurr:graph){for(DirectedGraphNodenext:curr.neighbors){inDegree.put(next,inDegree.get(next)1);}}for(DirectedGraphNodecurr:inDegree.keySet()){if(inDegree.get(curr)0){zero.add(curr);}}while(!zero.isEmpty()){DirectedGraphNodecurrzero.poll();rst.add(curr);for(DirectedGraphNodenext:curr.neighbors){inDegree.put(next,inDegree.get(next)-1);if(inDegree.get(next)0)zero.add(next);}}returnrst;}}​4.2 方法二DFS 深度法这套写法的关键抽象是Record(node, depth)一个点的 depth 定义为“从该点出发能走到的最大深度 1”。然后DFS 计算每个点的 depth用record做记忆化避免重复计算将所有点的 Record 收集起来按 depth 降序排序排完后的节点顺序作为拓扑序输出直觉上越“靠前”的点通常能到达越多后续层级因此 depth 越大应更先输出。importjava.util.*;publicclassTopologicalOrder2{publicstaticclassDirectedGraphNode{publicintlabel;publicArrayListDirectedGraphNodeneighbors;publicDirectedGraphNode(intx){labelx;neighborsnewArrayListDirectedGraphNode();}}publicArrayListDirectedGraphNodetopSort(ArrayListDirectedGraphNodegraph){if(graphnull)returnnull;HashMapDirectedGraphNode,RecordrecordnewHashMap();for(DirectedGraphNodecurr:graph){if(!record.containsKey(curr)){record.put(curr,getDepth(curr,record));}}ArrayListRecordordernewArrayList();for(DirectedGraphNodecurr:graph){order.add(record.get(curr));}order.sort(newNodeDepthComparator());ArrayListDirectedGraphNoderstnewArrayList();for(Recordcurr:order){rst.add(curr.node);}returnrst;}publicRecordgetDepth(DirectedGraphNodecurr,HashMapDirectedGraphNode,Recordrecord){if(currnull)returnnewRecord(null,0);intnextMathDepth0;for(DirectedGraphNodenext:curr.neighbors){if(record.containsKey(next)){nextMathDepthMath.max(nextMathDepth,record.get(next).depth);}else{RecordnextRecordgetDepth(next,record);nextMathDepthMath.max(nextMathDepth,nextRecord.depth);record.put(next,nextRecord);}}returnnewRecord(curr,nextMathDepth1);}publicclassRecord{publicDirectedGraphNodenode;publicintdepth;publicRecord(DirectedGraphNodenode,intdepth){this.nodenode;this.depthdepth;}}publicclassNodeDepthComparatorimplementsComparatorRecord{Overridepublicintcompare(Recordo1,Recordo2){returno2.depth-o1.depth;}}}​4.3 方法三DFS 点次法标注“不推荐”的原因很典型所谓“点次”这里是从当前点出发可到达节点数的累加含自身然后按点次降序排。这类指标在一些图结构上能产生“看起来合理”的序但它不是拓扑排序的充分条件可到达点多并不必然代表应该更靠前可能存在结构使得点次相近或误导排序因此更适合作为思路对比而非主方案。importjava.util.ArrayList;importjava.util.HashMap;publicclassTopologicalOrder3{publicstaticclassDirectedGraphNode{publicintlabel;publicArrayListDirectedGraphNodeneighbors;publicDirectedGraphNode(intx){labelx;neighborsnewArrayListDirectedGraphNode();}}publicArrayListDirectedGraphNodetopSort(ArrayListDirectedGraphNodegraph){if(graphnull)returnnull;HashMapDirectedGraphNode,LongrecordnewHashMap();for(DirectedGraphNodecurr:graph){if(!record.containsKey(curr)){record.put(curr,getNodeCount(curr,record));}}graph.sort((o1,o2)-Math.toIntExact(record.get(o2)-record.get(o1)));returngraph;}publiclonggetNodeCount(DirectedGraphNodecurr,HashMapDirectedGraphNode,Longrecord){if(currnull)return0;longcount1L;for(DirectedGraphNodenext:curr.neighbors){if(record.containsKey(next)){countrecord.get(next);}else{longnextCountgetNodeCount(next,record);countnextCount;record.put(next,nextCount);}}returncount;}}​5. 最小生成树一Kruskal5.1 核心思路Kruskal 解决的是无向图最小生成树问题从所有边中“由小到大”尝试加入只要不成环就保留否则丢弃。实现上分成两步1把所有边按权重丢进小根堆2用并查集维护“两个端点是否已在同一集合”从而判环。该实现的关键在并查集 DSUfindFather使用栈记录路径并做路径压缩union采用按 size 合并小集合挂到大集合上​5.2 关键实现细节边排序PriorityQueueEdgeWeightComparator权重升序。节点集合初始化将graph.nodes中所有节点收集后构造 DSU。选边循环每弹出一条边若两端点不在同一集合则加入答案并合并集合。importjava.util.*;publicclassKruskal{publicstaticSetEdgekruskal(Graphgraph){if(graphnull)returnnull;SetEdgerstnewHashSet();PriorityQueueEdgepqnewPriorityQueue(newWeightComparator());pq.addAll(graph.edges);ArrayListNodenodesnewArrayList();for(inti:graph.nodes.keySet()){nodes.add(graph.nodes.get(i));}DSUdsunewDSU(nodes);while(!pq.isEmpty()){Edgecurrpq.poll();if(!dsu.isSameSet(curr.from,curr.to)){rst.add(curr);dsu.union(curr.from,curr.to);}}returnrst;}publicstaticclassWeightComparatorimplementsComparatorEdge{Overridepublicintcompare(Edgeo1,Edgeo2){returno1.weight-o2.weight;}}publicstaticclassDSU{publicHashMapNode,Nodefather;publicHashMapNode,Integersize;publicDSU(ListNodenodes){fathernewHashMap();sizenewHashMap();for(Nodecurr:nodes){father.put(curr,curr);size.put(curr,1);}}publicNodefindFather(Nodecurr){StackNodepathnewStack();while(curr!father.get(curr)){path.add(curr);currfather.get(curr);}while(!path.isEmpty()){father.put(path.pop(),curr);}returncurr;}publicbooleanisSameSet(Nodea,Nodeb){returnfindFather(a)findFather(b);}publicvoidunion(Nodea,Nodeb){NodeaFatherfindFather(a);NodebFatherfindFather(b);intaSizesize.get(aFather);intbSizesize.get(bFather);if(aFather!bFather){if(aSizebSize){father.put(aFather,bFather);size.remove(aFather);size.put(bFather,aSizebSize);}else{father.put(bFather,aFather);size.remove(bFather);size.put(aFather,aSizebSize);}}}}}​6. 最小生成树二Prim6.1 核心思路Prim 的视角是“从点出发长出一棵树”从某个起点开始把该点视为已访问代码中叫unlocked / 解锁将解锁点的所有边扔进小根堆每次取堆顶最小边看它指向的to点是否已解锁未解锁保留该边、解锁to并把to的所有边继续入堆已解锁跳过该边。该实现还处理了非连通图对graph.nodes.values()逐个尝试作为新分量的起点因此得到的是最小生成森林。6.2 关键实现细节一个很有辨识度的细节是“延迟判断去重”入堆时不做contains检查允许重复边进入堆等出堆时再用unlocked判断是否应该丢弃。这样代码更简洁且利用堆的性质把去重压力延后到“最关键的一次判定”。importjava.util.*;publicclassPrim{publicstaticSetEdgeprim(Graphgraph){PriorityQueueEdgeleastEdgesnewPriorityQueue(newEdgeComparator());SetEdgerstnewHashSet();HashSetNodeunlockednewHashSet();for(Nodecurr:graph.nodes.values()){if(!unlocked.contains(curr)){unlocked.add(curr);for(Edgeedge:curr.edges){leastEdges.add(edge);}while(!leastEdges.isEmpty()){EdgeedgeleastEdges.poll();NodetoNodeedge.to;if(unlocked.contains(toNode)){continue;}rst.add(edge);unlocked.add(toNode);for(EdgenextEdge:toNode.edges){leastEdges.add(nextEdge);}}}}returnrst;}publicstaticclassEdgeComparatorimplementsComparatorEdge{Overridepublicintcompare(Edgeo1,Edgeo2){returno1.weight-o2.weight;}}}​7. 最短路径Dijkstra朴素实现7.1 核心思路Dijkstra 用于非负权图的单源最短路。该实现的整体框架是典型的“distance 表 selected 集合”distance记录 start 到各节点的当前最短距离selected记录哪些节点已经被选为“跳板”确定最短路不再更新循环过程每次从distance表里选出一个“未 selected 且距离最小”的节点curr用它去松弛relax所有出边。“朴素”体现在选点步骤getCurrMinDistance每轮通过遍历distance.keySet()找最小值因此时间复杂度为 (O(V^2 E)) 量级相对堆优化版。​7.2 关键实现细节未出现在distance的节点代表“不可达”等价于正无穷。松弛逻辑curDistance distance[curr] edge.weight若to不在表中则写入否则取更小值覆盖。importjava.lang.classfile.attribute.InnerClassesAttribute;importjava.util.HashMap;importjava.util.HashSet;publicclassDijkstra{publicstaticHashMapNode,Integerdijkastra(Nodestart){HashMapNode,IntegerdistancenewHashMap();HashSetNodeselectednewHashSet();distance.put(start,0);NodecurrgetCurrMinDistance(distance,selected);while(curr!null){for(Edgeedge:curr.edges){intcurDistancedistance.get(curr)edge.weight;if(!distance.containsKey(edge.to)){distance.put(edge.to,curDistance);}else{distance.put(edge.to,Math.min(distance.get(edge.to),curDistance));}}selected.add(curr);currgetCurrMinDistance(distance,selected);}returndistance;}privatestaticNodegetCurrMinDistance(HashMapNode,Integerdistance,HashSetNodeselected){intminInteger.MAX_VALUE;Noderstnull;for(Nodenode:distance.keySet()){if(!selected.contains(node)distance.get(node)min){rstnode;mindistance.get(node);}}returnrst;}}