DFS and a stack

Question

I am learning CS algorithms in my spare time and have been getting on quite well but I'm having trouble understanding adjacency matrix and DFS.

010100
101100
010110
111000
001001
000010

If the above is a undirected graph, with 6 vertices (a, f) (1st row is vertex a etc.) If the graph is traverse using DFS and a stack, starting at vertex a.

What would the contents of the queue after every time vertices are inserted to or removed from it be? I'm assuming that if there are 2 inserted at the same time it will be in alphabetical order.

Can someone explain how to work this out?

Answer 1

you're at a, so your row is 010100 and your neighbours are b,d. so put those on the stack (and you have visited a):

[d b]                  {a}

pop d, add it to the set of visited nodes, and visit there - 111000 (a,b,c) (but you have visited a):

[c b b]                {a d}

pop c, add it to the set of visited nodes, and visit there - 010110 (b, d, e) (but we have visited d):

[e b b b]              {a d c}

pop e, add it to the set of visited nodes, and visit there - 001001 (c, f) (but we have visited c):

[f b b b]              {a d c e}

pop f, add it to the set of visited nodes, and visit there - 000010 (e) (but we have visited there):

[b b b]                {a d c e f}

pop b, add it to the set of visited nodes, and visit there - 101100 (a, c, d) (but we have visited all those):

[b b]                  {a d c e f b}

and we have visited b, so pop and discard twice.

[]                     {a d c e f b}

ps it's DFS and so it's a stack, not a queue (you mention both in the question). for BFS it would be similar but you append to the queue, so the first few steps would be:

[d b]                  {a}
[b b c]                {a d}

where b and c are added on the "right" instead of the "left" (but we still take from the left, so we explore breadth-wise, and the next node would be b).