Python Learning Week 5 (Solution)

CODE:

graph = {
    ‘E’ : [‘A’,‘B’],
    ‘A’ : [‘D’],
    ‘B’ : [‘D’],
    ‘D’ : [‘C’],
    ‘C’:   []

}
 #EDGE-LIST
def edges(graph):
    edge_list = []
    for node in graph:
        for neighbour in graph[node]:
            edge_list.append((node, neighbour))

    return edge_list

#VERTEX-LIST
class Vertices_list:
    def __init__(self,graph_dict=None):
        if graph_dict is None:
            graph_dict = []
        self.graph_dict = graph_dict

    def get_Vertices(self):
        return list(self.graph_dict.keys())
G = Vertices_list(graph)

#BFS ALGORITHM
import collections
def bfs(graph, root):

    visited, queue = set(), collections.deque([root])
    visited.add(root)

    while queue:
        vertex = queue.popleft()
        print(str(vertex) + ” “, end=“”)

        for neighbour in graph[vertex]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)

#SHORTEST-PATH

def shortest_path(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return path
    shortest = None
    for node in graph[start]:
        if node not in path:
            newpath = shortest_path(graph, node, end, path)
            if newpath:
                if not shortest or len(newpath) < len(shortest):
                    shortest = newpath
    return shortest

#DFS ALGORITHM

def dfs(graph, node, visited):
    if node not in visited:
        visited.append(node)
        for k in graph[node]:
            dfs(graph,k, visited)
    return visited

a = int(input(”’\nSelect your choice
1. Display Graph Adjecency List
2. Display Graph Edge-List
3. Display Graph Vertex-List
4. Display BFS Algorithm Result
5. Display BFS Shortest Path between two nodes
6. Display DFS  Algorithm Result\n”’))

if a == 1:
    print(‘Graph Adjecency List’)
    print(graph) 
elif a == 2:
    print(‘Graph Edge List ‘)
    print(edges(graph))
elif a == 3:
    print(‘Graph Vertex List ‘)
    print(G.get_Vertices())
elif a == 4:
    print(‘BFS Algorithm Result’)
    bfs(graph, ‘E’)
elif a == 5:
    first = input(“Enter FIRST node “)
    second = input(“Enter SECOND node “)
    print(‘Shortest Path between two nodes is :’)
    print(shortest_path(graph, first, second))
elif a == 6:
    print(‘DFS  Algorithm Result’)
    visited = dfs(graph, ‘E’, [])
    print(visited)

else:
    print(“wrong option”)

OUTPUT:

Task 2

Implement given graph in python. Traverse Graph using DFS traversals. The starting node is ‘Frankfurt’ and goal node is ‘Munchen’.

CODE:

graph = {
    ‘Frankfurt’: [‘Mannheim’, ‘Wurzburg’, ‘Kassel’],
    ‘Mannheim’: [‘Karlsruhe’],
    ‘Karlsruhe’: [‘Augsburg’],
    ‘Wurzburg’: [‘Nurnberg’, ‘Erfurt’],
    ‘Nurnberg’: [‘Stuttgart’],
    ‘Kassel’: [‘Munchen’],
    ‘Augsburg’: [],
    ‘Stuttgart’: [],
    ‘Erfurt’: [],
    ‘Munchen’: []

}
def dfs(graph, node, visited):
    if node not in visited:
        visited.append(node)
        for k in graph[node]:
            dfs(graph,k, visited)
    return visited

print(‘Traversing graph from “Frankfurt” to “Munchen”‘)
visited = dfs(graph, ‘Frankfurt’, [])
print(visited)

OUTPUT:

What we studied in Week 5:

In this week we study Uninformed Search  that is Depth First Search (DFS) and Breadth First Search (BFS). Basically DFS & BFS  is an algorithm for traversing , searching tree and graph data structures. DFS algorithm starts at the root node and explores as far as possible along each branch before backtracking. In BFS starts at the root node explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. DFS will process the vertices first deep and then wide after processing a vertex its recursively processes all of its descendants. DFS uses stack (LIFO) data structure and BFS uses Queue (FIFO) data structure and we implemented both searches in python. This is all we have studied in this week.