Graph
그래프 구조는 Node와 Edge로 표현되는 자료구조 중 하나 Queue/ Stack을 활용하여 BFS, DFS 서치가 가능하다
graph LR
A --> B
A --> C
A --> D
B --> C
B --> D
B --> E
C --> E
D --> A
D --> B
파이썬에서 구현한 그래프는?
{'a': {'b'}, 'b': {'a', 'c'}, 'c': {'b', 'd'}, 'd': {'c', 'e', 'f'}, 'e': {'d'}, 'f': {'d'},'g': {'d'}}
그래프를 가장 쉽게 구현할 수 있는 방법은 Dictionary에서 해당 Key에 대한 Nodes들의 set을 매핑시키는 것!
Queue/Stack
def bfs(graph,start):
queue = [start]
visited = [];
while queue:
n = queue.pop(0) # queue의 index / stack은 queue.pop();
if n not in visited:
visited.append(n)
queue += graph[n] - set(visited) # 해당 노드에 연결되어 있는 edge를 활용하여, 검색하지 않은 Node들은 queue에 insert함
return visited;
queue와 stack의 차이는 pop되는 index의 차이이므로, pop(0)하게 되면 queue, pop(default=last_index)이면 stack
repo="ghk829" issue-term="pathname" theme="github-dark" crossorigin="anonymous" async>