[TIL][02.20] 그래프, DFS, BFS, 인접행렬, 인접리스트

그래프

정점 : 그래프 노드 또는 점

간선 : 정점 간의 연결, 부모-자식 개념 없음

가중치 : 간선(엣지)에 할당된 값

차수 : 정점에 연결된 간선의 수

진입 차수 : 방향 그래프에서 특정 정점으로 들어오는 간선의 수

진출 차수 : 방향 그래프에서 특정 정점에서 나가는 간선의 수

경로 :두 정점 간에 존재하는 간선의 연속

사이클 : 시작 정점에서 출발하여 다시 시작 정점으로 돌아오는 경로. 트리와 가장 큰 차이

연결 그래프 : 모든 정점이 서로 연결된 그래프

포화 그래프 : v개의 정점을 가지는 그래프는 최대 V * (V-1) / 2 간선이 가능

부분 그래프 : 원래 그래프의 일부 정점과 간선으로 구성된 그래프

방향 그래프 : 간선에 방향이 있는 그래프

무방향 그래프 : 간선에 방향이 없는 그래프

 

DFS

최대한 깊이 들어간 후, 더 이상 갈 곳이 없으면 되돌아오는 방식

그림 출처 : https://sethuram52001.medium.com/data-structures-and-algorithms-undirected-graph-processing-491d4fdefad0

BFS

현재 노드에서 가까운 노드를 먼저 탐색하고, 점차 멀리 탐색하는 방식

그림 출처 : https://takeuforward.org/graph/breadth-first-search-bfs-level-order-traversal/

인접 행렬 vs 인접 리스트

그래프를 표현하는 방법에는 인접 행렬(Adjacency Matrix) 과 인접 리스트(Adjacency List) 가 있음

인접 행렬 : 2차원 배열을 사용하여 그래프의 연결 정보를 저장, 연결되지 않은 노드 정보도 저장

인접 리스트 : 각 노드마다 연결된 노드 리스트를 저장, 연결된 노드만 저장하므로 메모리 절약 가능

 

도전문제

백준 17478 재귀함수가 뭔가요?

[JAVA]SWEA - 1873. 상호의 배틀필드 (D3)

SWEA 1954 달팽이 숫자

[JAVA]SWEA - 1954. 달팽이 숫자 (D2)

SWEA 1873 상호의 배틀필드

[JAVA]SWEA - 1873. 상호의 배틀필드 (D3)

개인 과제

프로그래머스 최댓값과 최솟값

[JS]프로그래머스 - 최댓값과 최솟값 (Lv.2)

프로그래머스 - 카펫

[JS]프로그래머스 - 카펫 (Lv.2)