Scribd
Upload
8 views2 pages

DFS Programs

Uploaded by

vardhanshannu73
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views2 pages

DFS Programs

Uploaded by

vardhanshannu73
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

## Program 1 ##

# Define the graph as an adjacency list


graph = {
1: [2, 3],
2: [4, 5],
3: [6, 7],
4: [],
5: [],
6: [],
7: []
}

# DFS using recursion


def dfs(node, visited):
if node not in visited:
print(node, end=' ')
visited.add(node)
for neighbor in graph[node]:
dfs(neighbor, visited)

# Call DFS starting from the root node (1)


visited = set()
print("DFS Traversal of the tree:")
dfs(1, visited)

## Program 2 ##

graph2 = {
'A': ['B', 'C'],
'B': ['D'],
'C': ['E', 'F'],
'D': [],
'E': [],
'F': []
}

def dfs2(node, visited):


if node not in visited:
print(node, end=' ')
visited.add(node)
for neighbor in graph2[node]:
dfs2(neighbor, visited)

print("\nDFS Traversal - Example 2:")


visited = set()
dfs2('A', visited)
## Program 3 ##

tree = {
'A': ['B', 'C', 'D'],
'B': ['E', 'F'],
'C': [],
'D': ['G'],
'E': [],
'F': [],
'G': ['H', 'I'],
'H': [],
'I': []
}
def dfs_tree(node, visited):
if node not in visited:
print(node, end=' ')
visited.add(node)
for child in tree[node]:
dfs_tree(child, visited)

print("DFS Traversal - General Tree with Branches:")


visited = set()
dfs_tree('A', visited)

You might also like