10-12-2012, 12:35 PM
Seminar on Topological Sort
Topological.pdf (Size: 615.12 KB / Downloads: 23)
Introduction
A Topological Sort of a Graph is a sequential ordering of its vertices.
For every edge u-v, u comes before v in ordering.
The graph must be directed where no cycle is permitted.
It is used for scheduling a sequence of jobs or tasks based on their dependencies.
Terminologies
BFS- Breadth First Search. Uses Queue as DS.
DFS- Depth First Search. Uses Stack as DS.
Adjacency matrix- For a graph G(V,E), it is a V*V matrix A(aij) where,
aij = 1,if edge i-j is present in G.
= 0, otherwise.
Analysis of the Algorithm
Asymptotic complexity of the algorithm is Θ(V+E).
The algorithm can be used to find out all possible orderings that can exist in a graph.
Same algorithm may give different results for a graph depending upon the initial node.