Sunday, January 21, 2018

Topological Sort based on DFS

Class Node {
   int val;
   Node *child[];
   bool visited;
}

list<int> Toposort(list<Node *> graph) {   // list of node contains the graph head nodes.
   list<int> ans;
   for (int i = 0; i < graph.size(); i++) {
      dfs(graph[i], ans);
   }
   return ans;
}

void dfs(Node *head, list<int>& ans) {
   if (head == NULL || head -> visited) {
      return;
   }
   head -> visited = true;
   for (int i = 0; i < head->child.size(); i++) {
      if (!head->child[i] ->visited) {
         dfs(head->child[i], ans);
      }
       ans.front(head->val);   // Insert in front of list when node completes DFS traversal.
   }
}


No comments:

Post a Comment