DAG - 确保存在单个源和单个接收器的算法

4 回答

• 0

  如果您的图表由邻接矩阵表示，那么如果矩阵的第x列为0，则节点x是源节点，如果矩阵的行x为0，则节点x是汇聚节点 . 您可以在矩阵上运行两次快速传递计算0的行数和列数，以确定存在多少源和接收器以及它们是什么 . 这需要时间O（n2）并且可能是检查这个的最快方法 .

  如果图形由邻接列表表示，则可以通过检查任何节点是否没有传出边缘来查找时间O（n）中的所有汇聚节点 . 您可以通过为每个节点维护一个布尔值来查找所有接收器，该布尔值指示它是否有任何传入边缘，最初为false . 然后，您可以在时间O（n m）内迭代列表中的所有边，标记具有传入边的所有节点 . 然后，未标记为具有传入边缘的节点是源 . 这个过程需要时间O（m n）并且开销很小，这可能是最快的方法之一 .

  希望这可以帮助！

  回复于 2024-05-03T09:20:38+08:00
• 0

  简单的广度或深度优先搜索应满足此要求 . 首先，您可以保留一组包含您已经看到的汇聚节点的节点 . 其次，您可以保留使用BFS / DFS发现的一组节点 . 然后，如果存在单个连接组件，则将连接图形 . 假设您正在为图表使用某种邻接列表样式表示，算法将如下所示：

  create an empty queue
  create an empty set to store seen vertices
  create an empty set for sink nodes
  
  add source node to queue
  
  while queue is not empty
      get next vertex from queue, add vertex to seen vertices
      if num of adjacent nodes == 0
          add sink nodes to sink node set
      else
          for each node in adjacent nodes
          if node is not in seen vertices
              add node to queue
  
  return size of sink nodes == 1 && size of seen vertices == total number in graph
  

  这将是图中顶点和边的数量的线性 .

  请注意，只要您知道要从头开始的源顶点，这也将确保单个源的属性：BFS / DFS将不会发现作为源的任何其他顶点，因此看到的大小顶点不是图表中的总数 .

  回复于 2024-05-03T09:20:38+08:00
• 0

  如果您的算法将弱连接的DAG作为输入，则假设只有一个节点s的入度为零，并且只有一个节点t的出度为零，而所有其他节点都具有正入度和out-degree，则s可以到达所有其他节点，所有其他节点都可以到达t . 通过矛盾，假设存在s无法到达的节点v . 由于没有节点可以达到s，也就是说，v也无法达到s . 因此，v和s断开连接，这与假设相矛盾 . 另一方面，如果DAG没有弱连接，它肯定不能满足您的要求 . 总而言之，您可以先使用BFS / DFS计算DAG的弱连通分量，同时记住入度或出度为零的节点数 . 该算法的复杂性为O（| E |） .

  回复于 2024-05-03T09:20:38+08:00
• 1

  首先，从源节点开始在图表上执行DFS，正如您所说，它是事先已知的 . 如果你遇到后沿[1]，那么你有一个循环，你可以退出并出错 . 在此遍历期间，您可以确定是否存在无法从源[2]访问的节点并采取适当的操作 .

  一旦确定图形是DAG，就可以确保每个节点位于从源到接收器的路径上，由源从源开始，如下所示：

  bool have_path(source, sink) {
      if source == sink {
          source.flag = true
          return true
      }
  
      // traverse all successor nodes of `source`
      for dst in succ(source) {
          if not dst.flag and not have_path(dst, sink)
             return false // exit as soon as we find a node with no path to `sink`
      }
      source.flag = true;
      return true
  }
  

  过程 have_path 在每个节点中设置一个布尔值 flag ，从该节点到接收器存在一些路径 . 同时，该过程仅遍历从源可到达的节点，并且它遍历从源可到达的所有节点 . 如果过程返回true，则从源可到达的所有节点都位于接收器的路径上 . 在第一阶段已经处理了无法访问的节点 .

  ---

  [1]边缘，将具有较大DFS编号的节点链接到具有较小DFS编号的节点，该节点尚未完全处理，即仍在DFS堆栈上

  [2]例如他们没有指定的DFS号码

  回复于 2024-05-03T09:20:38+08:00