1.

What is topological sorting in a graph?

Answer»

  • Topological sorting is a linear ordering of vertices such that for every directed edge ij, vertex i comes before j in the ordering.

  • Topological sorting is only possible for Directed Acyclic Graph (DAG).

  • Applications:

    1. jobs scheduling from the given dependencies among jobs.

    2. ordering of formula cell evaluation in spreadsheets

    3. ordering of compilation tasks to be performed in make files,

    4. data serialization

    5. resolving symbol dependencies in linkers.



  • Topological Sort Code in Java:

// V - total vertices
// visited - boolean array to keep track of visited nodes
// graph - adjacency list.
// Main Topological Sort Function.
void topologicalSort()
{
Stack<Integer> stack = new Stack<Integer>();

// Mark all the vertices as not visited
boolean visited[] = new boolean[V];
for (int j = 0; j < V; j++){
visited[j] = false;
}
// Call the util function starting from all vertices one by one
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, stack);

// Print contents of stack -> result of topological sort
while (stack.empty() == false)
System.out.print(stack.pop() + " ");
}

// A helper function used by topologicalSort
void topologicalSortUtil(int v, boolean visited[],
Stack<Integer> stack)
{
// Mark the current node as visited.
visited[v] = true;
Integer i;

// Recur for all the vertices adjacent to the current vertex
Iterator<Integer> it = graph.get(v).iterator();
while (it.hasNext()) {
i = it.next();
if (!visited[i])
topologicalSortUtil(i, visited, stack);
}

// Push current vertex to stack that saves result
stack.push(new Integer(v));
} Conclusion

In this post, we covered the most important and frequently asked Data Structures interview questions. We've also included some pointers and tricks to help you prepare for the interview. When preparing for the product-based companies interview, keep in mind that the Data Structures interview is a critical component of the process. It is critical that you are well prepared for the interview because it will determine whether or not you are hired. As a result, it is critical to begin planning as soon as possible.

Additional Interview Resources

  • Programming: DSA - https://www.interviewbit.com/courses/programming/

  • Data Structure MCQ - https://www.interviewbit.com/data-structure-mcq/

  • Best Books for Data Structures and Algorithms - https://www.interviewbit.com/blog/data-structures-and-algorithms-books/

  • Best Data Structures and Algorithms Course - https://www.interviewbit.com/blog/best-courses-for-data-structures-and-algorithms/

  • Algorithm Interview Questions - https://www.interviewbit.com/algorithm-interview-questions/

  • Master Data Structures and Algorithms With the Scaler Academy Program - https://www.scaler.com/courses/data-structures-and-algorithms/


Discussion

No Comment Found

Related InterviewSolutions