Algorithms

Question 1

Explain the steps of topological sort.

Answer 1

There can be more than one sorting for each graph, it depends on the vertices you choose to start with. Starting with a vertex, you mark it as visited and see if it has any unvisited children, starting from the left. If it does, you repeat same steps for children. Repeat until all children are visited. Then choose another starting vertex and repeat.

https://www.youtube.com/watch?v=ddTC4Zovtbc

Question 2

What are the steps for DFS on a graph?

Answer 2

There will be a start vertex. Push it to stack, and mark it as visited. Look at all unvisited vertices adjacent to it, and find the one that is alphabetically least, and go to it. Push to stack, mark as visited. Continue same step to this vertex.
When all adjacents are visited, pop vertex off stack and keep going backwards until there’s a vertex with unvisited adjacent.

Question 3

What are the steps for BFS on a graph?

Answer 3

There will be a start vertex (A for ex), mark it as visited. We will work on A. Find all vertices connected to A and get the one that is alphabetically least and mark as visited, add to queue. Still on A, we move to next one connected to A alphabetically, and keep marking as visited and add to queue. Once all vertices connected to A are visited, we go in alphabetical order and remove from queue. Repeat the same steps u did for A until all vertices visited.