NaEun's Notes

BFS와 최단경로 💡BFS와 최단경로BFS는 s에서 출발해서 모든 노드를 방문할 뿐만 아니라, 출발점 s에서 부터 각각의 노드까지 가는 가장 짧은 경로를 구할 수 있다.가장 짧은 경로란, 경로의 길이를 에지(edge)의 개수로 본다면 그 수가 가장 적은 경로를 의미모든 노드에 대해 최단 경로의 길이와 predecessor를 구할 수 있다.BFS 최단경로 수도코드 💡수도코드로 이해하는 BFS 최단경로 구하기입력으로 그래프 G와 출발 노드 s를 지정했다고 가정한다.BFS 구현을 위한 큐 Q를 만들어주고, Q는 비어있는 상태이다. d[s]출발점으로 부터의 최단 경로처음에는 출발점이 자신이기때문에 0π[s]특정 노드에 도착하기 직전 노드처음에는 그런 노드가 없기 때문에 null어떤 것을 Q에 넣는 것을 En..

그래프 순회 💡순회그래프의 모든 노드들을 체계적으로, 중복 없이 방문하는 것을 의미💡대표적인 순회 방법 2가지BFS (Breadth-First Search, 너비우선순회)DFS (Depth-First Search, 깊이우선순회)BFS, 너비우선순회 💡BFS, 너비우선순회노드들을 동심원의 형태로 순회하는 알고리즘즉, 출발 노드 방문 후, 출발 노드에 인전합 노드들을 다 방문하는 방식인접하다는 것은, 에지(edge)로 직접 연결되어있다는 의미 = 거리가 1인 노드거리가 1인 노드 방문 후에는 거리가 2인 노드들을 방문, 즉, 거리가 1인 노드와 또 다시 에지로 연결되는 노드들을 방문그래프의 모든 노드들을 방문하기 위해 출발 노드를 지정해줘야 한다. (위 그림에서는 s)💡Queue를 이용한 BFS우선,..

무방향 그래프 주요 용어 정리 💡경로와 연결성경로 (path)무방향 그래프에서 노드 사이의 경로라는 것은, 예를 들어, 4에서 3까지 에지(edge)들을 따라 가는 경로를 의미한다.연결두 노드 사이를 연결하는 경로가 있을 때, 연결되어있다고 말한다.ex. 위 그림에서 4와 2는 에지로 직접 연결되어있으므로 인접(adgacent)한 것이고, 4에서 7처럼 두 노드 사이에 에지들을 거쳐 도달할 수 있는 경우 연결되었다고 한다.연결된(connected) 그래프모든 노드들이 서로간 다 연결이 되어 있는 경우를 연결된 그래프라고 한다.연결 요소 (connected component)연결된 그래프 덩어리아래 그림과 같이 A, B, C가 하나의 그래프 라면, 각각의 3개의 연결요소로 구성되어있다고 한다.출처http..

무방향 그래프(Graph)의 표현 💡인접행렬 (Adjacency Matrix)정점의 개수가 n개인 그래프를 n x n 인 2차원 배열(행렬)로 표현하는 방식i 번째 행, j 번째 열을 𝑎ᵢⱼ 라고 한다면, 정점 i와 j 사이에 에지가 있으면, 1 없으면 0으로 표시한다.모든 정점 쌍에 대해서 에지가 있는지의 여부를 표로 표현할 수 있다.대칭행렬 : 대각선으로 접었을 때, 대칭이 된다는 뜻사용하는 메모리 저장 공간은 O(n2)💡인접리스트 (Adjacency List) 방향 그래프(Directed Graph)의 표현 💡인접행렬 (Adjacency Matrix) 가중치 그래프(Weighted Graph)의 표현 💡인접행렬 (Adjacency Matrix)

그래프(Graph) 💡그래프(Graph) 란?그래프(G)는 V와 E 두개의 집합에 의해 구성된다.보통 그래프라고 칭하면, 방향이 없는 그래프를 의미하는 경우가 많다.방향이 없다는 것은 순서쌍 (1, 2)와 (2, 1)을 동일한 쌍으로 본다는 것을 의미한다. = Edge의 방향이 없다.이진관계 (binary relation)두 개의 객체(정점) 사이의 관계를 순서쌍(ordered pair)으로 표현하는 수학적 개념그래프가 정점들 사이의 쌍으로 이루어진 관계를 나타낸다.이 강의에서 정점의 개수는 n으로, 에지의 개수는 m으로 표현한다.💡방향 그래프(Directed Graph) 란?에지 (u, v)와 (v, u)는 서로 다른 것이 방향 그래프이다.💡가중치 그래프(Weighted Graph) 란?가중치 그..