htmi如何做网站网站主导航设置问题

htmi如何做网站,网站主导航设置问题,网站建设合同书样本,河南省住房城乡和建设厅网站一、有向图的定义 有向图是图的重要类型#xff0c;由顶点集合和有向边集合组成#xff0c;其中每条边都有明确的方向#xff0c;仅能从一个顶点指向另一个顶点。若存在一条从顶点u指向顶点v的边#xff0c;可表示为u, v#xff0c;该边仅允许从u到v的通行#…一、有向图的定义有向图是图的重要类型由顶点集合和有向边集合组成其中每条边都有明确的方向仅能从一个顶点指向另一个顶点。若存在一条从顶点u指向顶点v的边可表示为u, v该边仅允许从u到v的通行反之不成立。资料https://pan.quark.cn/s/43d906ddfa1b、https://pan.quark.cn/s/90ad8fba8347、https://pan.quark.cn/s/d9d72152d3cf有向图可形式化表示为G(V, E)其中V是顶点的非空有限集合E是有向边的有限集合每条边关联V中两个有序顶点允许存在自环边即u, u形式的边。二、有向图的核心概念1. 顶点的度有向图中顶点的度分为入度和出度入度记为indeg(v)指以顶点v为终点的有向边数量出度记为outdeg(v)指以顶点v为起点的有向边数量顶点的总度数为入度与出度之和且有向图所有顶点的入度之和等于出度之和均等于边数|E|。2. 路径与环有向路径从顶点u到v的顶点序列v₀u, v₁, v₂, ..., vₖv其中每个相邻顶点对vᵢ, vᵢ₊₁都存在有向边路径长度为边的数量简单路径路径中所有顶点互不重复的有向路径有向环起点和终点为同一顶点、长度≥1且顶点不重复除起点终点的有向路径例如A,B,B,C,C,A构成一个有向环有向无环图DAG不存在有向环的有向图是拓扑排序的核心应用对象。3. 连通性有向图的连通性比无向图更复杂主要分为两种强连通若对于图中任意两个顶点u和v既存在从u到v的有向路径也存在从v到u的有向路径则称该有向图为强连通图强连通分量非强连通有向图中每个最大的强连通子图称为强连通分量弱连通若忽略边的方向后有向图变为连通的无向图则称该有向图为弱连通图。4. 完全有向图若对于有向图中任意两个不同顶点u和v同时存在u, v和v, u两条有向边则称为完全有向图。包含n个顶点的完全有向图边数为n(n-1)。三、有向图的存储方式1. 邻接矩阵用n×n的二维数组adj存储n为顶点数其中adj[i][j]表示是否存在从顶点i指向j的有向边若adj[i][j]1或边的权重表示存在有向边i,j若adj[i][j]0或无穷大表示不存在该有向边有向图的邻接矩阵非对称即adj[i][j]与adj[j][i]无必然相等关系。优缺点优点查询两顶点间是否存在指定方向边的时间复杂度为O(1)实现简单缺点空间复杂度为O(n²)稀疏图会造成大量空间浪费。2. 邻接表为每个顶点维护一个链表或数组存储该顶点指向的所有邻接顶点。整体为数组adj其中adj[v]是顶点v的出边邻接顶点列表。若需快速查询入边可额外维护逆邻接表存储以每个顶点为终点的所有起点。优缺点优点空间复杂度为O(|V||E|)适合稀疏图遍历顶点出边效率高缺点查询从u到v是否存在有向边的时间复杂度为O(outdeg(u))。四、有向图的核心算法1. 深度优先搜索DFS与无向图DFS逻辑类似但需遵循边的方向仅能沿有向边遍历。可用于有向环检测和强连通分量求解如Tarjan算法。时间复杂度邻接矩阵存储为O(n²)邻接表存储为O(|V||E|)。2. 广度优先搜索BFS按层遍历有向图仅能沿有向边扩散可用于求解有向无权图的单源最短路径。时间复杂度邻接矩阵存储为O(n²)邻接表存储为O(|V||E|)。3. 拓扑排序拓扑排序是对有向无环图DAG顶点的一种线性排序满足若存在有向边u, v则排序中u一定在v之前。常用算法Kahn算法基于入度的贪心算法、DFS逆序法应用场景任务调度、课程安排、依赖关系解析等。4. 关键路径针对带权有向无环图关键路径是从起点到终点的最长路径决定了整个工程的最短完成时间常用于项目进度规划。五、有向图的实现示例1. 邻接表实现含拓扑排序fromcollectionsimportdequeclassDirectedGraph:def__init__(self,num_vertices):self.num_verticesnum_vertices# 邻接表存储出边self.adj_list[[]for_inrange(num_vertices)]# 入度数组self.indegree[0]*num_verticesdefadd_edge(self,u,v):添加有向边u, vifvnotinself.adj_list[u]:self.adj_list[u].append(v)self.indegree[v]1defremove_edge(self,u,v):删除有向边u, vifvinself.adj_list[u]:self.adj_list[u].remove(v)self.indegree[v]-1defdfs(self,start,visitedNone):深度优先搜索ifvisitedisNone:visited[False]*self.num_vertices visited[start]Trueprint(start,end )forneighborinself.adj_list[start]:ifnotvisited[neighbor]:self.dfs(neighbor,visited)defbfs(self,start):广度优先搜索visited[False]*self.num_vertices queuedeque([start])visited[start]Truewhilequeue:vertexqueue.popleft()print(vertex,end )forneighborinself.adj_list[vertex]:ifnotvisited[neighbor]:visited[neighbor]Truequeue.append(neighbor)deftopological_sort(self):Kahn算法实现拓扑排序返回拓扑序列queuedeque()# 初始化队列入度为0的顶点foriinrange(self.num_vertices):ifself.indegree[i]0:queue.append(i)topo_order[]whilequeue:uqueue.popleft()topo_order.append(u)# 遍历u的出边减少邻接顶点入度forvinself.adj_list[u]:self.indegree[v]-1ifself.indegree[v]0:queue.append(v)# 若拓扑序列长度不等于顶点数说明存在环iflen(topo_order)!self.num_vertices:return图中存在有向环无法进行拓扑排序returntopo_order使用示例# 初始化6个顶点的有向图顶点0-5模拟课程依赖graphDirectedGraph(6)# 添加有向边表示课程先修关系如0,1表示0是1的先修课graph.add_edge(0,1)graph.add_edge(0,2)graph.add_edge(1,3)graph.add_edge(2,3)graph.add_edge(3,4)graph.add_edge(3,5)print(DFS遍历结果起点0:)graph.dfs(0)# 输出 0 1 3 4 5 2顺序可能因邻接表存储不同有差异print(\nBFS遍历结果起点0:)graph.bfs(0)# 输出 0 1 2 3 4 5print(\n拓扑排序结果:)print(graph.topological_sort())# 输出 [0,2,1,3,5,4] 等合法序列六、有向图的典型应用依赖关系建模如软件包的依赖、代码模块的调用关系、课程先修体系路径规划如城市单行道的导航、网络数据包的路由状态机如程序的状态转移、自动售货机的行为逻辑网络流如物流运输的单向通路、通信网络的信号传输方向。