Miloz46

Graph dfs and bfs, recursive and iterative

May 22nd, 2022 (edited)
213
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.80 KB | None | 0 0
  1. from collections import deque
  2. from dataclasses import dataclass
  3.  
  4. def create_list(size: int, element_to_append) -> list:
  5.     retval = []
  6.     for _ in range(size):
  7.         retval.append(element_to_append[:])
  8.     return retval
  9.  
  10. @dataclass
  11. class Graph:
  12.     vertices: list[list[int]]
  13.  
  14.     def __init__(self, filepath: str) -> None:
  15.         self.read_from_file(filepath)
  16.         pass
  17.  
  18.     def read_from_file(self, filepath: str) -> None:
  19.         with open(filepath) as file:
  20.             edges = int(next(file))
  21.             self.vertices = create_list(edges, [])
  22.             for line in file:
  23.                 source, dist = [int(x) for x in line.split()]
  24.                 self.vertices[source].append(dist)
  25.                 self.vertices[dist].append(source)
  26.         pass
  27.  
  28.     def recursive_dfs(self, head_element: int, path = None) -> None:
  29.         if path is None: path = []
  30.         path.append(head_element)
  31.         for neighbour in self.vertices[head_element]:
  32.             if neighbour not in path:
  33.                 print(neighbour)
  34.                 self.recursive_dfs(neighbour, path)
  35.         pass
  36.  
  37.     def iterative_dfs(self, head_element: int) -> None:
  38.         visited = [False for _ in range(len(self.vertices))]
  39.         stack = [head_element]
  40.         while stack:
  41.             current = stack.pop()
  42.             if not visited[current]:
  43.                 print(current)
  44.                 visited[current] = True
  45.                 for neighbour in self.vertices[current]:
  46.                     stack.append(neighbour)
  47.         pass
  48.  
  49.    
  50.     def recursive_bfs(self, queue = None, discovered = None) -> None:
  51.         if queue is None and discovered is None:
  52.             queue = deque([ 0, ])
  53.             discovered = [False] * len(self.vertices)
  54.             discovered[0] = True
  55.  
  56.         if not queue: return
  57.  
  58.         value = queue.popleft()
  59.         print(value)
  60.  
  61.         for neighbour in self.vertices[value]:
  62.             if not discovered[neighbour]:
  63.                 discovered[neighbour] = True
  64.                 queue.append(neighbour)
  65.        
  66.         self.recursive_bfs(queue, discovered)
  67.         pass
  68.  
  69.     def iterative_bfs(self, head_element: int) -> None:
  70.         visited = [False] * len(self.vertices)
  71.         queue = []
  72.  
  73.         queue.append(head_element)
  74.         visited[head_element] = True
  75.  
  76.         while queue:
  77.             current = queue.pop(0)
  78.             print(current)
  79.             for neighbour in self.vertices[current]:
  80.                 if not visited[neighbour]:
  81.                     queue.append(neighbour)
  82.                     visited[neighbour] = True
  83.         pass
  84.  
  85. if __name__ == "__main__":
  86.     graph: Graph = Graph("graph-data.txt")
  87.     # graph.recursive_dfs(0)
  88.     # graph.iterative_dfs(0)
  89.     # graph.iterative_bfs(0)
  90.  
  91.     graph.recursive_bfs()
  92.  
  93.     print(graph)
  94.  
Add Comment
Please, Sign In to add comment