Graph ADT :
Structure Graph is
objects: a nonempty set of vertices and a set of undirected edges, where each edge is a pair of vertices
functions: for all graph belongs Graph, v, v1 and v2 belongs Vertices
Graph Create()::=return an empty graph
Graph InsertVertex(graph, v)::= return a graph with v inserted. v has no incident edge.
Graph InsertEdge(graph, v1,v2)::= return a graph with new edge between v1 andv2
Graph DeleteVertex(graph, v)::= return a graph in which v and all edges incident to it are removed
Graph DeleteEdge(graph, v1, v2)::=return a graph in which the edge (v1, v2) is removed
Boolean IsEmpty(graph)::= if (graph==empty graph) return TRUE else return FALSE
List Adjacent(graph, v)::= return a list of all vertices that are adjacent to v
- One way to find a topological sort is to consider in-degrees of the vertices
- The first vertex must have in-degree zero --every DAG must have at least one vertex with in-degree zero.
ALGORITHM
int topologicalOrderTraversal( ){
int numVisitedVertices = 0;
while(there are more vertices to be visited){
if(there is no vertex with in-degree 0)
break;
else{
select a vertex v that has in-degree 0;
visit v;
numVisitedVertices++;
delete v and all its emanating edges;
}
}
return numVisitedVertices;
}
.jpeg)
.jpeg)