Find a topological ordering for the following graph 5 extra

Find a topological ordering for the following graph. (5% extra credit) (Hash Tables) Suppose that keys are binary integers. For a modular hash function with prime m greaterthanorequalto 2, prove that any two binary integers that differ in exactly one bit have different hash values. (5% extra credit) (BFS) Suppose you use a stack instead of a queue when running breadth-first search. does it still compute shortest paths?

Solution

1) To find the topological order we will start with vertex having zero degree and delete it and its connected ones from graph(the one who will be zero degree) and write to output

S is the vertex of zero degree
Now find all the connected vertices to it and write to output and repeat until all the done from graph
S, A, G,D

Now take G because next vertex of zero degree is G
G- D,E,H
D is already in output , lets check for E and H
S,A,G,D,E,H
till no there is no break in order

Next zero degree vertex is D
D - E, A and both are already in output
S,A,G,D,E,H

Next zero degree vertex is A
A- E,B , here E is already in output we will write B
S,A,G,D,E,H,B

Next is H
H - E, I , here E is already in output so we will add I
S,A,G,D,E, H, B,I

Next is E,
E - I,F,C, here I is already in output
F is connected to C hence we will first write F in order and then C
S,A,G,D,E,H,B,I,F,C

Next vertex is B
B-C, and it already in output
S,A,G,D,E,H,B,I,F,C

Next is I
I- F,t, here F is already in output we will write t
S,A,G,D,E,H,B,I,F,C,t

Next is F
F- t, C, both are already in output

Next is C
C-t , t is already in output

Hence topological sort is
S,A,G,D,E,H,B,I,F,C,t