class StationNode:
"""지하철 역을 나타내는 역"""
def __init__(self, station_name):
self.station_name = station_name
self.adjacent_stations = []
self.visited = False
def add_connection(self, station):
"""파라미터로 받은 역과 엣지를 만들어주는 메소드"""
self.adjacent_stations.append(station)
station.adjacent_stations.append(self)
from collections import deque
from subway_graph import create_station_graph
def bfs(graph, start_node):
"""시작 노드에서 bfs를 실행하는 함수"""
queue = deque() # 빈 큐 생성
# 일단 모든 노드를 방문하지 않은 노드로 표시
for station_node in graph.values():
station_node.visited = False
# 시작점 노드를 방문 표시한 후 큐에 넣어준다
start_node.visited = True
queue.append(start_node)
while queue: # 큐에 노드가 있는 동안
a = queue.popleft() # 큐의 가장 앞 데이터를 갖고 온다
for adjacent_stations_of_a in a.adjacent_stations: # 인접한 노드를 돌면서
if adjacent_stations_of_a.visited == False: # 방문하지 않은 노드면
adjacent_stations_of_a.visited = True # 방문 표시를 하고
queue.append(adjacent_stations_of_a) # 큐에 넣는다
visited
변수를 False
로 만들기 위해 그래프를 다 돌기 때문에 👉 =
class StationNode:
"""지하철 역을 나타내는 역"""
def __init__(self, station_name):
self.station_name = station_name
self.adjacent_stations = []
self.visited = False
def add_connection(self, station):
"""파라미터로 받은 역과 엣지를 만들어주는 메소드"""
self.adjacent_stations.append(station)
station.adjacent_stations.append(self)
from collections import deque
from subway_graph import *
def dfs(graph, start_node):
"""dfs 함수"""
stack = deque() # 빈 스택 생성
# 모든 노드를 처음 보는 노드로 초기화
for station_node in graph.values():
station_node.visited = 0
start_node.visited = 1
stack.append(start_node)
while stack:
a = stack.pop()
a.visited = 2
for neighbors_of_a in a.adjacent_stations:
if neighbors_of_a.visited == 0:
neighbors_of_a.visited = 1
stack.append(neighbors_of_a)
visited
변수를 False
로 만들기 위해 그래프를 다 돌기 때문에 👉 =