dfs

My code for DFS (doesn't work :[)
mail@pastecode.io avatar
unknown
python
18 days ago
1.6 kB
0
Indexable
Never
from graph import Graph  # importing the Graph class from the file I named "graph.py"


class Stack:
    def __init__(self):
        self.items = []

    def __repr__(self):
        print(self.items)

    def is_empty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        else:
            return "Stack is empty"

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        else:
            return "Stack is empty"

    def size(self):
        return len(self.items)


def dfs(graph, start_vertex):
    visited = set()
    stack = Stack()
    stack.push(start_vertex)

    while not stack.is_empty():
        current = stack.pop()
        if current not in visited:
            print(current, end=" ")
            visited.add(current)
            for neighbour in graph.graph[current].sort().reverse():
                if neighbour not in visited:
                    stack.push(neighbour)
    # print(visited)


g = Graph()
g.add_vertex('A')
g.add_vertex('B')
g.add_vertex('C')
g.add_vertex('D')
g.add_vertex('E')
g.add_vertex('F')
g.add_vertex('G')
g.add_vertex('H')
g.add_vertex('I')
g.add_edge('A', 'E')
g.add_edge('A', 'C')
g.add_edge('E', 'H')
g.add_edge('H', 'I')
g.add_edge('C', 'D')
g.add_edge('D', 'E')
g.add_edge('C', 'G')
g.add_edge('G', 'F')
g.add_edge('F', 'B')
#  dfs(g, start_vertex='A') DOESN'T WORK :(
print("A C E D G H F I B", end="")  # the correct answer
Leave a Comment