Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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
- if __name__ == "__main__":
- graph: Graph = Graph("graph-data.txt")
- graph.recursive_dfs(0)
- # graph.iterative_dfs(0)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement