C++로 무방향 그래프의 간선 개수 구하기

이 글에서는 무방향 그래프(Undirected Graph)에 존재하는 간선의 개수를 구하는 방법을 C++ 코드와 함께 알아보겠습니다.

무방향 그래프란 여러 개의 정점(Vertex)이 서로 연결되어 하나의 그래프를 이루는 구조로, 모든 간선이 양방향으로 통행 가능한 그래프를 의미합니다. 즉, 어느 노드에서든 연결된 다른 노드로 자유롭게 이동할 수 있습니다.

다음은 무방향 그래프의 시각적인 예시입니다.

C++로 무방향 그래프의 간선 개수 구하기 — 인접 리스트 완전 정복

문제 정의

그래프에서 간선(Edge)이란 두 정점을 잇는 선을 말합니다. 주어진 무방향 그래프에 간선이 총 몇 개 있는지 계산하는 것이 목표입니다.

입력 −

insert(graph_list, 0, 1);
insert(graph_list, 0, 2);
insert(graph_list, 1, 2);
insert(graph_list, 1, 4);
insert(graph_list, 2, 4);
insert(graph_list, 2, 3);
insert(graph_list, 3, 4);

출력 −

count of edges are: 7

해결 접근 방식

그래프의 모든 정점 정보를 저장할 인접 리스트(adjacency list) 배열을 초기화하고, 간선 정보를 차례대로 삽입합니다.
count_edges 함수 안에서 간선의 개수를 세기 위한 변수 count = 0을 선언합니다.
반복문을 사용해 첫 번째 정점부터 마지막 정점까지 리스트를 순회하면서, 각 정점의 인접 리스트 크기(graph_list[i].size())를 count에 더해 줍니다.
모든 정점 순회가 끝나면 count를 2로 나눈 뒤 결과를 출력합니다.

여기서 결과를 2로 나누는 이유는, 무방향 그래프에서는 하나의 간선이 양쪽 정점의 인접 리스트에 각각 한 번씩 기록되기 때문입니다. 따라서 전체 합계에는 모든 간선이 두 번씩 포함됩니다.

C++ 구현 예제

#include<bits/stdc++.h>
using namespace std;

// 정점을 연결하는 간선을 삽입하는 함수
void insert(list<int> graph_list[], int u, int v){
   graph_list[u].push_back(v);
   graph_list[v].push_back(u);
}

// 총 간선의 개수를 세는 함수
void count_edges(list<int> graph_list[], int v){
   int count=0;
   // 마지막 정점까지 리스트를 순회
   for (int i = 0 ; i < v ; i++){
      count += graph_list[i].size();
   }
   count = count/2;
   cout<<"count of edges are: "<<count;
}

int main(int argc, char* argv[]){
   // 그래프에 정점 5개 생성
   int vertices = 5;
   // 그래프용 리스트 선언 후 정점 수 전달
   list<int> graph_list[vertices];
   // 리스트, 정점, 연결된 정점을 인자로 insert 함수 호출
   insert(graph_list, 0, 1);
   insert(graph_list, 0, 2);
   insert(graph_list, 1, 2);
   insert(graph_list, 1, 4);
   insert(graph_list, 2, 4);
   insert(graph_list, 2, 3);
   insert(graph_list, 3, 4);
   // 간선의 개수를 세는 함수 호출
   count_edges(graph_list, vertices);
   return 0 ;
}

실행 결과

위 코드를 컴파일하여 실행하면 다음과 같은 출력을 확인할 수 있습니다.

count of edges are: 7

마무리 및 시간 복잡도

이 알고리즘은 모든 정점의 인접 리스트를 한 번씩 순회하므로, 정점의 개수를 V, 간선의 개수를 E라고 할 때 시간 복잡도는 O(V + E)입니다. 인접 행렬 방식(O(V²))보다 효율적이므로, 그래프 탐색 문제에서 인접 리스트를 활용하는 습관을 들이면 좋습니다.