Блог пользователя aman_naughty

Автор aman_naughty, история, 5 лет назад, По-английски

I was wondering if we can find the mother vertex in a directed connected graph by topological sorting. The last finished vertex will be the mother vertex.

Is this approach correct or am I thinking wrong?

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

I had to google what the hell a "mother vertex" was. Apparently it's a vertex $$$v$$$ such that any other vertex can be reached from $$$v$$$.

And no, it's not correct. What if the graph has no mother vertices? Your algorithm will still try to say something is the mother vertex.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Then we can check whether the last finished vertex is mother or not by a single dfs or bfs. Is it correct now.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yes, but only in a DAG. (At least I think so, but from your blog the "last finished vertex" is a bit unclear.)

      If your however graph isn't acyclic, then the concept of topological sorting is meaningless.

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

This vertex can be easily found with n times a dfs. Start a dfs from each unvisited vertex and only visit unvisited vertices. The last vertex where we started a dfs is the vertex we search(if any such vertex exists). However, a topological sorting may not work.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Isn't topological sort doing the same thing as you mentioned? At the end of the topological sort, the last vertex in the stack will be a candidate for mother vertex.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      its more or less the same as toposort with dfs. However there are other ways to get topological sortings kahns algorithm. This may fail. For example on a non DAG graph kahns algorithm will definitely fail.

»
5 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Find strongly connected components and build the DAG of SCCs , consider the first component in topological sort if that can visit all other components then all nodes in that Strongly connected component are "mother" vertices.