비선형 자료구조: 데이터를 일렬로 구성하지 않고, 자료 순서/관계를 계층적으로 구성한 자료구조
(ex. 트리/그래프/해시 테이블 etc)
1. 그래프
: 정점(Vertex)과 간선(Edge)로 이루어진 자료구조로, 정점 간 관계를 표현하는 조직도(ex. 최단 경로)
"이러한 관점에서 트리는 그래프의 일종이지만, 그래프는 트리와 달리 정점마다 간선이 있을 수도/없을 수도 있고 루트노드와 부모/자식 개념이 없다"
👉🏻 [종류]
- 무방향(Undirected) 그래프: 두 정점을 연결하는 간선에 방향이 없는 그래프
- 방향(Directed) 그래프: 두 정점을 연결하는 간선에 방향이 존재하는 그래프
- 가중치(Weighted Graph) 그래프: 간선에 가중치가 할당된 그래프, 두 정점을 이동할 때 비용이 드는 그래프
👉🏻 [표현 방식]
- 인접 행렬(Adjacency Matrix): 그래프의 노드를 2차원 배열로 만든 것으로, 노드 간에 직접 연결이 되어 있으면 1, 아니면 0을 저장
- 인접 리스트(Adjacency List): 그래프의 노드를 리스트로 표현한 것으로, 주로 정점의 리스트 배열을 만들어 관계를 설정하고 노드 간 직접 연결이 되어 있으면 해당 노드의 인덱스에 그 노드를 삽입
👉🏻 [용어]
- 정점(Vertex): 노드라고도 하며 정점에는 데이터가 저장됨
- 간선(Edge): 정점(노드)를 연결하는 선
- 인접 정점(adjacent Vertex): 간선에 의해 직접 연결된 정점
- 단순 경로(simple path): 경로 중 반복되는 정점이 없는 경우 (한붓그리기)
- 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점 수
- 진출 차수(in-degree): 방향 그래프에서 외부로 향하는 간선 수
- 진입 차수(on-degree): 방향 그래프에서 외부에서 들어오는 간선 수
- 경로 길이(path length): 경로를 구성하는데 사용된 간선 수
- 사이클(cycle): 단순 경로의 시작/종료 정점이 동일한 경우 [ 비순환 그래프: 사이클 x, 순환 그래프: 사이클 o ]
👉🏻 [탐색]
1. 깊이 우선 탐색(DFS, Depth-First Search): 루트 노드(or 임의 노드)에서 시작해 다음 분기로 넘어가기 전 해당 분기를 완벽하게/깊게 탐색
[구현 과정]
1. 먼저 시작 노드를 방문처리 해주고
2. 해당 노드에 인접한 노드들을 재귀로 탐색/방문처리(오름차순 정렬이 되어 있다는 가정 하에)
3. 한 노드를 깊게(끝까지) 탐색한 후에
4. 다시 돌아와서 그 다음 노드를 또 깊게 탐색하는 흐름graph = [[], #노드를 1부터 시작하기 위해서 처음은 비워두기 [2, 3, 5], #1노드 [1, 4], #2노드 [1, 4, 5], #3노드 [2, 3, 7], #4노드 [1, 3, 6], #5노드 [5], #6노드 [3, 4]] #7노드 visited = [False] * (len(graph)) #방문 처리 리스트 def DFS(graph, node): visited[node] = True #방문처리 해주고 print(node, end=' ') # 인접한 노드들에 대해 재귀 호출 for i in graph[node]: # 시작 노드 1을 넣었을 때 2, 3, 4 중 2를 먼저 끝까지 탐색 # 2를 깊게 탐색한 다음, 3을 탐색하려하면 이미 2에서 탐색했음 # 그럼 넘어가고 다음 4 탐색 하면 7까지 모든 노드 탐색 완료 if not visited[i]: DFS(graph, i) # 시작 노드를 1로 설정하여 DFS 실행 DFS(graph, 1)
- 너비 우선 탐색(BFS, Breadth-First Search): 루트(or 임의 노드)에서 시작해 인접한 노드를 먼저 탐색, 시작 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문
[구현 과정]
1. 탐색 시작 정점을 방문처리하고 큐에 삽입
2. 큐의 front에서 꺼낸 정점의 인접한 정점들에 대해 탐색
3. 방문되지 않은 정점은 큐에 삽입/방문처리
4. 큐가 공백이 될 때까지 2-3 반복graph = [[], #노드를 1부터 시작하기 위해서 처음은 비워두기 [2, 3, 5], #1노드 [1, 4], #2노드 [1, 4, 5], #3노드 [2, 3, 7], #4노드 [1, 3, 6], #5노드 [5], #6노드 [4]] #7노드 visited = [False] * (len(graph)) q = deque() #양쪽에서 삽입/삭제 가능 def BFS(graph, node): q.append(node) #시작 노드 먼저 큐에 삽입 visited[node] = True #방문처리 해주고 while q: #큐가 빌 때까지 반복 node = q.popleft() #큐에서 pop해줌 print(node, end=' ') for i in graph[node]: #인접한 노드 중에 if not visited[i]: #방문하지 않은 노드가 있다면 q.append(i) #큐에 삽입해주고 visited[i] = True #방문처리 BFS(graph, 1)
