2.2 topological sort 02

Data Structure-topological sort 02

1. TOPOLOGICAL SORT

2. Definition
A topological sort of a Directed Acylic Graph
(DAG) is a linear ordering of all its vertices such
that if there is a path from v
i
to v
k
then v
i
appears
before v
k
in the ordering.

3. Algorithm for finding a topological sort
Initialize TSArray to null
for (i=1; i<=numofvertices; i++)
v = find vertex of degree zero
if v is null
 Graph has a cycle. Exit
else
 add v to TSArray
 remove v and all its outgoing vertices
Print TSArray

4. Algorithm for enumerating all topological sorts
TopologicalSorts()
compute the indegree count array, Indegree[ ]
initialize TSArray[ ] to null
for each vertex v
if indegree[v] == zero
push Indegree[ ], TSArray[ ], v
while (stack not empty)
pop Indegree[ ], TSArray[ ], v
add v to TSArray
for each x adjacent to v, Indegree[x]--
for each vertex v
if indegree[v] == zero
push Indegree[ ], TSArray[ ], v

5. Find out the ordering
1 2
4
6 7
53

6. Solution
•1 2 5 4 3 7 6
•1 2 5 4 7 3 6
•Find out other possibilities.

8. How many squares can you create in this figure by connecting any 4
dots (the corners of a square must lie upon a grid dot?
TRIANGLES:
How many triangles are located in the image below?

9. There are 11 squares total; 5 small, 4 medium, and 2 large.
27 triangles. There are 16 one-cell triangles, 7 four-cell triangles, 3 nine-cell triangles, and
1 sixteen-cell triangle.

10. There are 11 squares total; 5 small, 4 medium, and 2 large.
27 triangles. There are 16 one-cell triangles, 7 four-cell triangles, 3 nine-cell triangles, and
1 sixteen-cell triangle.