그래프
정점과 간선을 이용해 연결되어 있는 원소 사이 다대다 관계 표현한 자료구조
방향 그래프와 무방향 그래프
- 방향 그래프, 무방향(양방향) 그래프
- 그래프 탐색시 방문 노드 탐색 확인 필수 (ex. Static boolean isVistied[])
연결 그래프와 비연결 그래프
- 연결 그래프 : 모든 노드 탐색
for(노드 : 모든노드) DFS(노드) 👉 시간 복잡도 ↑ - 비연결 그래프 : 한번 탐색으로 모든 노드를 탐색한다고 보장할 수 없음
- 집단이 분할된다고 볼 수 있음 ( grouping )
가중치 그래프
- 각 노드를 갈 때 간선의 가중치를 다양하게 부여할 수 있음
- 다익스트라 알고리즘, 벨만포드
에지리스트
2차원 배열 이용, 간선을 중심으로 그래프 표현
1) 배열에 출발, 도착노드를 저장하여 에지 표현 = A[N][2]
2) 간선에 가중치가 있는 경우 행을 3개로 늘려 3번째 행에 가중치를 저장 = A[N][3]
특정 노드와 관련되어 있는 에지를 탐색하기 불편
인접 행렬
2차원 배열을 자료구조로 이용하, 노드 중심으로 그래프 표현 ( N * N )
- 노드에 비해 간선이 적은 경우 희소 행렬로 표현되어 메모리와 탐색 효율이 굉장히 낮아짐
- 배열이 모두 있는 경우 효율적이지만 그렇지 않다면 효율적이지 않음
- 시간 복잡도 : O(V^2)
- 인접 가중치가 있는 경우 인접 배열 리스트에 저장
인접 리스트
ArrayList 이용, 노드 중심으로 그래프 표현
- N번 노드와 연결되어 있는 노드를 배열의 위치 N에 연결된 노드 개수 만큼 배열 연결
- 공간 효율이 좋고 각 노드에 연결되어 있는 에지 탐색 시 빠름
- 시간 복잡도 O(V+E) : 모든 정점 확인 + 모든 간선 지나면 탐색 종료
- 가중치가 있는 경우 자료형을 클래스로 사용
에지리스트 - 인접리스트 - 탐색 - DFS,BFS
DFS와 BFS
깊이 우선 탐색 (DFS)
완전 탐색 기법
: 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정해
최대 깊이까지 탐색을 마친 후 다른 분기 쪽으로 이동하여 다시 탐색하는 알고리즘
- 특징
- 재귀 함수로 구현
- Stack 자료구조 이용
- 시간 복잡도 (노드 수 V, 에지 수 : E) : O(V+E)
- 백트래킹
❗탐색 방법
1) DFS를 시작할 노드 정한 후 사용할 자료구조 초기화 하기
- 인접 리스트로 그래프 표현하기
- 방문 배열 초기화 하기
- Stack에 시작노드 삽입하기
2) Stack에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 Stack에 삽입하기
- Stack에서 pop 연산을 수행 하여 노드를 꺼낸 후 꺼내 노드를 탐색 순서에 기입
- 인접 노드를 Stack에 삽입하여 방문 배열 체크 (ex. Static boolean isVistied[])
- Stack pop - 방문 배열 F, Stack push - 방문 배열 T
3) Stack에 값이 없을 때 까지 반복 하기 (isEmpty())
- 1, 2번 과정을 Stack에 값이 없을 때 까지 반복하기
- 이미 다녀간 노드는 방문 배열을 바탕으로 재삽입 X
너비 우선 탐색 (BFS)
완전 탐색 기법
: 그래프의 시작 노드에서 출발하여 시작 노드를 기준으로
가까운 노드를 먼저 방문하면서 탐색하는 알고리즘
: 목표 노드에 도착하는 경로가 여러개일 때 최단 경로 보장
- 특징
- FIFO 탐색
- Queue 자료구조 이용
- 시간 복잡도 (노드 수 V, 에지 수 : E) : O(V+E)
❗탐색 방법
1) BFS를 시작할 노드 정한 후 사용할 자료구조 초기화 하기
- 인접 리스트로 그래프 표현하기
- 방문 배열 초기화 하기
- Queue에 시작노드 삽입하기
2) Queue에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 Queue에 삽입(En-Queue)하기
- Queue에서 노드를 꺼내면서 대상 노드의 인접 노드를 Queue에 삽입하기
- 노드를 Queue에 삽입하며 방문 배열 체크 (ex. Static boolean isVistied[])
- Queue 에서 노드를 꺼내면서 탐색 순서에 꺼낸 노드 기록
3) Queue에 값이 없을 때 까지 반복 하기 (isEmpty())
- 1, 2번 과정을 Queue에 값이 없을 때 까지 반복하기
- 이미 다녀간 노드는 방문 배열을 바탕으로 재삽입 X
