Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from collections import deque
- from dataclasses import dataclass
- def create_list(size: int, element_to_append) -> list:
- retval = []
- for _ in range(size):
- retval.append(element_to_append[:])
- return retval
- @dataclass
- class Graph:
- vertices: list[list[int]]
- def __init__(self, filepath: str) -> None:
- self.read_from_file(filepath)
- pass
- def read_from_file(self, filepath: str) -> None:
- with open(filepath) as file:
- edges = int(next(file))
- self.vertices = create_list(edges, [])
- for line in file:
- source, dist = [int(x) for x in line.split()]
- self.vertices[source].append(dist)
- self.vertices[dist].append(source)
- pass
- def recursive_dfs(self, head_element: int, path = None) -> None:
- if path is None: path = []
- path.append(head_element)
- for neighbour in self.vertices[head_element]:
- if neighbour not in path:
- print(neighbour)
- self.recursive_dfs(neighbour, path)
- pass
- def iterative_dfs(self, head_element: int) -> None:
- visited = [False for _ in range(len(self.vertices))]
- stack = [head_element]
- while stack:
- current = stack.pop()
- if not visited[current]:
- print(current)
- visited[current] = True
- for neighbour in self.vertices[current]:
- stack.append(neighbour)
- pass
- def recursive_bfs(self, queue = None, discovered = None) -> None:
- if queue is None and discovered is None:
- queue = deque([ 0, ])
- discovered = [False] * len(self.vertices)
- discovered[0] = True
- if not queue: return
- value = queue.popleft()
- print(value)
- for neighbour in self.vertices[value]:
- if not discovered[neighbour]:
- discovered[neighbour] = True
- queue.append(neighbour)
- self.recursive_bfs(queue, discovered)
- pass
- def iterative_bfs(self, head_element: int) -> None:
- visited = [False] * len(self.vertices)
- queue = []
- queue.append(head_element)
- visited[head_element] = True
- while queue:
- current = queue.pop(0)
- print(current)
- for neighbour in self.vertices[current]:
- if not visited[neighbour]:
- queue.append(neighbour)
- visited[neighbour] = True
- pass
- if __name__ == "__main__":
- graph: Graph = Graph("graph-data.txt")
- # graph.recursive_dfs(0)
- # graph.iterative_dfs(0)
- # graph.iterative_bfs(0)
- graph.recursive_bfs()
- print(graph)
Add Comment
Please, Sign In to add comment