Graph Search DFS_BFS_UCS

Most used Graph Search methos:

  • DFS- Depth First Search
  • BFS- Breedth First Search
  • UCS- Uninform Cost Search
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
import matplotlib.pyplot as plt
import networkx as nx
import queue

class Graph:
    def __init__(self):
        self.nodes = {}
    def add_edge(self, start, end, cost=1):
        if start not in self.nodes:
            self.nodes[start] = {}
        self.nodes[start][end] = cost
    def get_neighbors(self, node):
        return self.nodes.get(node,{}) #if not exist return {}
    

def dfs(graph, start, goal): # Depth First Search
    stack = queue.LifoQueue() #Last in first out queue, stack
    stack.put((start,[start], 0)) # start_node, path, cost
    while not stack.empty(): # stop when stack is empty
        vertex, path, cost = stack.get() #pop a element from stack, node, path, cost
        #sort the neighbors of the element pop from stack
        sorted_neighbors = sorted(graph.get_neighbors(vertex).items(), key=lambda x:x[0], reverse = True)
        #go through the sorted neighbors of the element pop from stack
        for next_node, next_cost in sorted_neighbors:
            if next_node in path: # if next_node is in path which mean has been went through
                continue # just walk through
            elif next_node == goal: # if the next_node == goal, return the final path and total cost
                return path + [next_node], cost + next_cost
            else : # if it is not the goal node, put it into the stack waiting for check its neighbors
                stack.put((next_node, path + [next_node], cost + next_cost))
    # stack is empty which means all elements have been went through, return None, None reprensent didn't find the goal in graph
    return None, None    

def bfs(graph, start, goal): # Breadth First Search
    q = queue.Queue() # a queue that first in and first out
    q.put((start, [start], 0)) #start_node, path, cost
    while not q.empty(): # go through all elements in the queue
        vertex, path, cost = q.get() # get an ele from the queue, node, path, cost
        sorted_neighbors = sorted(graph.get_neighbors(vertex).items(), key = lambda x:x[0], reverse = True )
        for next_node, next_cost in sorted_neighbors:
            if next_node in path:
                continue
            elif next_node == goal:
                return path+[next_node], cost + next_cost
            else:
                q.put((next_node, path+[next_node], cost+next_cost))
    return None, None
    
def ucs(graph, start, goal): # Uninform Cost Search
    pq = queue.PriorityQueue() # pop the priority
    pq.put((0, start, [start])) # cost(also is priority), start_node, path
    visited = set()
    while not pq.empty():
        cost, vertex, path = pq.get()
        if vertex in visited:
            continue
        if vertex == goal:
            return  path, cost
        visited.add(vertex)
        for next_node, next_cost in graph.get_neighbors(vertex).items():
            if next_node not in visited:
                pq.put((cost+next_cost, next_node, path+[next_node]))
    return None, None


def visualize_graph(graph):
    G = nx.DiGraph() # Create a directed graph 创建一个有向图
    for node, neighbors in graph.nodes.items():
        for neighbor, cost in neighbors.items():
            G.add_edge(node, neighbor, weight = cost)
    plt.figure(figsize = (3,3))
    pos = nx.spring_layout(G)
    nx.draw(G, pos, with_labels = True, node_size = 500, node_color = "skyblue", node_shape = "o", alpha = 0.6, linewidths =4)
    labels = nx.get_edge_attributes(G, 'weight')
    nx.draw_networkx_edge_labels(G, pos, edge_labels = labels)
    plt.show()

graph = Graph()
graph.add_edge('S','A',1)
graph.add_edge('S','B',3)
graph.add_edge('A','C',1)
graph.add_edge('A','D',1)
graph.add_edge('C','G',5)
graph.add_edge('D','G',2)
graph.add_edge('B','G',2)
graph.add_edge('B','G',5)



path, cost = dfs(graph, 'S', 'G')
print(f"DFS path: {path}, cost: {cost}")

path, cost = bfs(graph, 'S', 'G')
print(f"BFS path: {path}, cost: {cost}")

path, cost = ucs(graph, 'S','G')
print(f"UCS path: {path}, cost: {cost}")


visualize_graph(graph)