Implementation Of Uninformed Search Algorithms (bfs)

Aim

The aim of this experiment is to implement the simple uniformed search algorithm breadth first search methods using python.

---

Procedure (Algorithm)

The steps for implementing the Breadth-First Search (BFS) algorithm are as follows:

1. Start by putting any one of the graph’s vertices at the back of the queue.

2. Now take the front item of the queue and add it to the visited list.

3. Create a list of that vertex’s adjacent nodes. Add those adjacent nodes which are not already within the visited list to the rear of the queue.

4. Keep continuing steps two and three until the queue is empty.

---

Program (Python)

The program uses Python, utilizing the deque collection for managing the queue (fringe) required for BFS.

from collections import deque

class Graph:
    def __init__(self, directed=True):
        self.edges = {}
        self.directed = directed

    def add_edge(self, node1, node2, reversed=False):
        try:
            neighbors = self.edges[node1]
        except KeyError:
            neighbors = set()

        neighbors.add(node2)
        self.edges[node1] = neighbors

        if not self.directed and not reversed:
            self.add_edge(node2, node1, True)

    def neighbors(self, node):
        try:
            return self.edges[node]
        except KeyError:
            return []

    def breadth_first_search(self, start, goal):
        found, fringe, visited, came_from = False, deque([start]), set([start]), {start: None}

        print('{:11s} | {}'.format('Expand Node', 'Fringe'))
        print(' ')
        print('{:11s}|{}'.format('-', start))

        while not found and len(fringe):
            current = fringe.pop()
            print('{:11s}'.format(current), end='|')
            if current == goal:
                found = True
                break

            for node in self.neighbors(current):
                if node not in visited:
                    visited.add(node)
                    fringe.appendleft(node) # Use appendleft to enforce FIFO (BFS)
                    came_from[node] = current
            print(','.join(fringe))

        if found:
            print()
            return came_from
        else:
            print('No path from {} to {}'.format(start, goal))

    @staticmethod
    def print_path(came_from, goal):
        parent = came_from[goal]
        if parent:
            Graph.print_path(came_from, parent)
        else:
            print(goal, end='')
            return
        print(' =>', goal, end='')

graph = Graph(directed=False)
graph.add_edge('A', 'B')
graph.add_edge('A', 'S')
graph.add_edge('S', 'G')
graph.add_edge('S', 'C')
graph.add_edge('C', 'F')
graph.add_edge('G', 'F')
graph.add_edge('C', 'D')
graph.add_edge('C', 'E')
graph.add_edge('E', 'H')
graph.add_edge('G', 'H')

start, goal = 'A', 'H'
traced_path = graph.breadth_first_search(start, goal)

if(traced_path):
    print('Path:', end='')
    Graph.print_path(traced_path, goal)
    print()

---

Output

The execution of the BFS program yields the following output, demonstrating the node expansion and the state of the fringe (queue):

======================RESTART:F:/bfs.py==============================
ExpandNode | Fringe
-          |A
A          |S, B
B          |S
S          |C, G
G          |H, F, C
C          |E, D, H, F
F          |E, D, H
H          |
Path: A => S => G => H

---

Result

Thus, the program for breadth first search was executed and the output is verified.