graph - 为 Graph 算法编写伪代码

问题描述

给定一个 DAG和一个将每个顶点映射到从 1 到的唯一数字的函数，我需要为一个算法编写一个伪代码，该算法在从 v 可到达的所有顶点 u 中找到的每个最小值，并保存它a v 的一个属性。算法的时间复杂度需要是（假设时间复杂度是）。

我考虑过使用 DFS（或其变体）和/或拓扑排序，但我不知道如何使用它来解决这个问题。

另外，我需要考虑一个算法，它得到一个无向图和函数，并为每个顶点计算相同的东西，我也不知道该怎么做。

标签： graphgraph-algorithmdepth-first-search

您使用 DFS 的想法是正确的。实际上，该函数f(v)只是为了说明每个节点可以从 1 到之间的数字唯一标识|V|。

f(v)只是一个解决的提示，您必须修改 DFS 以便它返回从该节点可到达的顶点的最小值v并将其保存为另一个数组，假设minReach索引将由函数给出f(v)。访问的数组vis将类似地使用来标识f(v)。

如果您无法解决但先自己尝试，我也会提供伪代码。伪代码类似于 python 并假设图形和函数f(v)可用。并且假定基于 0 的索引。

vis=[0, 0, 0, .. |V| times]  # visited array for dfs 
minReach= [1, 2, 3, .. |V| times] #  array for storing no. reachable nodes from a node

function dfs(node):
   vis[f(node)-1]=1                             ### mark unvisited node as visited 
   for v in graph[node]:
       if vis[v]!=1:                            ## check whether adjacent node is visited
           minReach[f(node)-1]=min(minReach[f(node)-1],dfs(v)        ## if not visited apply dfs again
       else:
           minReach[f(node)-1]=min(minReach[f(node)-1],countReach[f(v)-1])   ## else store the minimum node that can be reached from this node.
   return countReach[f(node)-1]

for vertex in graph:         ### each vertex is checked in graph
   if vis[f(vertex)-1]!=1:   ### if vertex is not visited dfs is applied
      dfs(vertex)

graph - 为 Graph 算法编写伪代码

问题描述

解决方案

推荐阅读