DFS and a stack

3
votes

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?

2
algorithmgraphdepth-first-search
Is this homework? If so you should tag it as such. - smessing
Also, I would suggest drawing a real graph from the adjacency matrix, this will enable you to have a better picture of how DFS works. Then, walk through the functioning of DFS on a, to get a sense of how things are added to the stack. - smessing
Why don't you try it out? Implement DFS, print the stack every time you modify it. - Fred Foo
not homework, just trying to learn the theory rather than actually code it - user1261083
would like to see the pattern as then I can work out what is happening and how, this is how I learned BFS earlier today. - user1261083

2 Answers

4
votes

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).

2
votes

As an addendum to andrew cooke's nice answer, you can use the python library networkx to actually visualize the DFS search! By default the DFS starts at node 0, but this can be changed. You can modify the graph at the beginning to visualize more complex systems.

enter image description here

import numpy as np
import networkx as netx
import pylab as plt

# Reshape the input string into a numpy array then a graph
A = np.array(map(int,"010100101100010110111000001001000010")).reshape(6,6)
G = netx.Graph(A)

# Compute the DFS tree
T = netx.dfs_tree(G)

# Show the edges traversed
print list(netx.dfs_edges(G))

# Plot the original graph
plt.subplot(121)
pos = netx.circular_layout(G)
netx.draw(G,pos,node_color='w',node_size=800)
netx.draw_networkx_nodes(G,pos,nodelist=[0],node_color='r',node_size=800)

# Plot the result of the DFS
plt.subplot(122)
pos = netx.circular_layout(T)
netx.draw(T,pos,node_color='w',node_size=800)
netx.draw_networkx_nodes(T,pos,nodelist=[0],node_color='r',node_size=800)

plt.show()