CODEWITHSUNDEEP
algorithmgraphdepth-first-search
user1261083
user1261083

Reputation: 69

DFS and a stack

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?

Upvotes: 3

Views: 1813

Answers (2)

Hooked
Hooked

Reputation: 88148

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

Upvotes: 2

andrew cooke
andrew cooke

Reputation: 46882

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

Upvotes: 4

Related Questions