비선형 자료구조 (그래프)
이번 포스트에서는 비선형 자료구조 중 하나인 그래프에 대하여 설명하겠습니다. 그래프 그래프는 간선으로 연결된 정점들의 모음을 표현한 자료구조입니다. 이때 정점과 정점을 연결하는 간선들이 방향을 가지지 않는 경우, 이 그래프를 무방향 그래프라고 합니다. 반대로, 방향을 가지는 경우 방향 그래프라고 정의합니다. 부분그래프는 그래프 G의 정점 V와 간선 E가 있을 때, 부분그래프 G'는 다음 수식을 만족합니다. G' = (V', E'), V' 는 V에 속하고, E'는 E에 속해야합니다. 무방향 그래프 G 내 임의의 서로 다른 두 정점 u, v에 대해, u에서 v로 가는 경로가 존재한다면, G는 연결 되었다고 합니다. 이때, G 내에서 최대로 연결된 부분그래프를 연결요소 라고한다. 반대로 방향 그래프 G 에서 ..
2023. 9. 11.