스택과 큐,재귀 함수는 DFS/BFS에서 가장 중요한 개념이다,배우기전 한번더 숙지 하길 바란다.

그래프(graph)

알기전에 그래프에 기본 구조를 알아 보자.

그래프

그래프 구조:

1.노드:
노드를 정점(Vertex)이 라고도 부른다.
2.간선

그래프 탐색이란

하나의 노드를 시작으로 다수의 노드를 방문하는 것.

프로그래밍에서는 그래프를 크게 2가지로 표현한다

1.인접 행렬:2차원 배열로 그래프의 연결 관계를 표현하는 방식.

2차원 배열에 각 노드가 연결된 형태 기록하는 방식,

INF = 999999

graph =[
[0,1,0,0],
[0,0,1,0],
[1,0,0,1],
[1,1,0,0]
]

print(graph)

결과:

[[0, 1, 0, 0], [0, 0, 1, 0], [1, 0, 0, 1], [1, 1, 0, 0]]

2.인접 리스트:리스트로 그래프의 연결 관계를 표현하는 방식.

graph = [[] for _ in range(4)]

graph[1].append((2, 7))
graph[2].append((3, 2))
graph[3].append((2, 4))
graph[3].append((1, 4))

print(graph)

결과

[[], [(2, 7)], [(3, 2)], [(2, 4), (1, 4)]]

두 방법의 차이점:

메모리 측면에서는 인접행렬이 불 필요한 관계도 저장되므로 메모리가 낭비된다.
반면 인접 리스트는 연결된 정보만 저장하기때문에 메모리 효율적으로 저장,하지만 인접 리스트는 인접 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지 대한 정보를 얻는 속도가 느리다. 인접 리스트에서는 연결된 리스트를 하나씩 확인해야하기때문.
특정한 노드와 연결된 모든 인접 노드를 순회하는 경우.인접 리스트방식이 인접 행력 방식에 비해 메모리 공간의 낭비가 적다.