We Will consider the below example to solve DFS traversal.
I assume you have prior knowledge of how DFS works.
node = ["a", "b", "c", "d", "e", "f", "g"]
edges = [["a", "b"], ["b", "c"], ["b", "e"], ["c", "d"], ["c", "e"],
["e", "g"], ["f", "f"]]
visited = set()
graph = {}
for i in node:
graph[i] = []
for (u, v) in edges:
graph[u].append(v)
graph[v].append(u)
The Above code will generate a graph which will be as per the above figure.
First, we are declaring the nodes i.e. all the nodes like "a", "b", "c"... then we declare the edges i.e all the connections between the nodes as we know that it is an undirected graph, Once done with making connections we can just push all the connections in the graph, In the first for loop we can see.
We are using visited=set() because here we will store the visited node cause once we visit something we also need to keep a note of that so we use set(set does not store duplicate value)
We are using graph={}->(dictionary in python hashmap in easy term), In hashmap we usually store key-value pair so as per our case we need to get the node which is connected to whom so we are using hashmap/dictionary (Key-value).
for i in node:
graph[i] = []
Here we store the number of keys in the graph(If confused then please consider reading about hashmap/dictionary/object), So for each node, we create an empty list in which we will store the connections of the key concerning list.
{'a': [], 'b': [], 'c': [], 'd': [], 'e': [], 'f': [], 'g': []}
Once our basic key is done then we create the connections with the key value i.e. who is connected to "a" ->Only b right? yes similarly for all the nodes we check which edges are connected to the node
for (u, v) in edges:
graph[u].append(v)
graph[v].append(u)
Output (graph):
{'a': ['b'], 'b': ['a', 'c', 'e'], 'c': ['b', 'd', 'e'], 'd': ['c'], 'e': ['b', 'c', 'g'], 'f': ['f', 'f'], 'g': ['e']}
Now come's the DFS :
First, I'll share the code and then explain each step
def dfs(graph, node, visited):
print(node)
visited.add(node)
for item in graph[node]:
if item not in visited:
dfs(graph, item, visited)
We are going to use recursion for iterating over all the nodes, First, we print the node which we are currently in i.e. print(node) then after printing we add that to our book of list visited, we go over each item in the graph[node] (in simple words we will go over all the connected edges of the node i.e. graph[a] will give all the connected node to a) after that we check have we already visited this node? if yes then we skip else we pass the current item to the function (recursion) this will go on until the base case is satisfied, so when no more nodes will be left to visit our dfs traversal will be done
Output(DFS):
a
b
c
d
e
g
The F node was not printed/visited because the F node is not connected to any other node :)