how to traverse adjacency matrix graph by DFS and BFS methods in python

Question

I am beginner in DSA.I am student and am learn to solve graph problems. In past experience i am traversing adjacency matrix graph by DFS and BFS but there is nodes are start by 0 to 5 like index but in this case nodes are starting from "A" to "Z" so i need help to solve the problems.

below is code of graph and what i try for solving problem :-

class Graph:
    node=[]
    graph=[]
    node_count=0

    def addNode(self,v):
        if v in self.node:
            print(f"{v} node is already present.")
        else:
            self.node_count +=1
            self.node.append(v)
            for n in self.graph:
                n.append(0)
            temp=[]
            for i in range(self.node_count):
                temp.append(0)
            self.graph.append(temp)

    
    def addEdges(self,v1,v2):
        if v1 not in self.node:
            print(f"{v1} is not in graph")
        elif v2 not in self.node:
            print(f"{v2} is not in graph")
        else:
            index1=self.node.index(v1)
            index2=self.node.index(v2)
            self.graph[index1][index2]=1

    def DFS(self):
        pass

    def BFS(self):
        pass

    def deleteNode(self,v):
        if v not in self.node:
            print(f"{v} is not present in the graph.")
        else:
            index1=self.node.index(v)
            self.node_count -=1
            self.node.remove(v)
            self.graph.pop(index1)
            for i in self.graph:
                i.pop(index1)

    def deleteEdges(self,v1,v2):
        if v1 not in self.node:
            print(f"{v1} is not in graph")
        elif v2 not in self.node:
            print(f"{v2} is not in graph")
        else:
            index1=self.node.index(v1)
            index2=self.node.index(v2)
            self.graph[index1][index2]=0



    def print_graph(self):
        for i in range(self.node_count):
            for j in range(self.node_count):
                print(self.graph[i][j],end=" ")
            print()

    



graphs=Graph()
graphs.addNode("A")
graphs.addNode("B")
graphs.addNode("C")
graphs.addNode("D")
graphs.addNode("E")
graphs.addNode("F")
graphs.addNode("G")
graphs.addNode("Z")
print(graphs.graph)
graphs.addEdges("A","B")
graphs.addEdges("A","C")
graphs.addEdges("B","D")
graphs.addEdges("C","E")
graphs.addEdges("E","F")
graphs.addEdges("D","G")
graphs.addEdges("F","G")
graphs.addEdges("A","Z")

graphs.DFS()
graphs.BFS()

print(graphs.node)
graphs.print_graph()

graphs.deleteNode("G")

print("AFTER DELETE")
graphs.print_graph()
print(graphs.node)

graphs.deleteEdges("E","F")

print("AFTER DELETE EDGE")
graphs.print_graph()

I want to traverse adjacency matrix graph by DFS and BFS method :-

    def DFS(self):
        pass

    def BFS(self):
        pass

graphs.DFS()
graphs.BFS()

vedatbaday · Accepted Answer · 2022-09-28 18:07:27Z

Your DFS and BFS methods do not have an entry point, the search should start in some vertex, so the first thing to do should be adding parameters for this.

def DFS(self, start):
    start_idx = self.node.index(start)
    new_line = True  # for better visualization
    for i in range(self.node_count):
      if self.graph[start_idx][i]:
        new_line = False
        print(f"{start}->{self.node[i]}", end=" ")
        self.DFS(self.node[i])
    if new_line:
      print()


def BFS(self, start):
  que = queue.Queue()
  start_idx = self.node.index(start)
  que.put(start_idx)
  while not que.empty():
    curr_vertex = que.get()
    for i in range(self.node_count):
      if self.graph[curr_vertex][i]:
        que.put(i)
        print(f"{self.node[curr_vertex]}->{self.node[i]}")

In the DFS case, we are simply traversing along the first encountered nodes. For example from starting point "A", first encountered node will be "B". For "B" it will be "D", and so on. By tracing edges and nodes you can find out traversal as follows:

A->B B->D D->G

A->C C->E E->F F->G

A->Z

And for the BFS, instead of traversing the first encountered nodes, the nodes are traversed in breadth, that is traversing all nodes at the current depth before moving on to the next depth. Again for the "A", the traversal can be as:

Node "A" (this is first depth):

A->B

A->C

A->Z

Nodes at the second depth:

B->D

C->E

Nodes at the third depth:

D->G

E->F

Nodes at the fourth depth:

F->G

Since you do not store a mapping between nodes (letters in your example) and their indices, indices are obtained by searching through your node list using self.node.index. It would be better if you use a map for such conversions.

Collectives™ on Stack Overflow

how to traverse adjacency matrix graph by DFS and BFS methods in python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related