인시던스 리스트(Incidence List)로 그래프를 표현하는 C++ 프로그램

이 프로그램은 인시던스 리스트(incidence list) 방식으로 그래프를 표현합니다. 인시던스 리스트란 그래프의 각 간선이 연결하고 있는 두 정점을 나열함으로써 그래프의 구조를 나타내는 방법입니다. 이 알고리즘의 시간 복잡도는 O(e)로, 간선의 개수에 비례하여 매우 효율적입니다.

알고리즘

시작
   그래프의 정점 개수 'v'와 간선 개수 'e'를 입력받는다.
   주어진 그래프의 'e'개 정점 쌍을 e[][] 배열에 입력받는다.
   각 간선에 대해 해당 연결에 포함된 정점들을 출력한다.
종료

예제 코드

#include<iostream>
using namespace std;
int main() {
   int i, v, e, j, c;
   cout<<"그래프의 정점 개수를 입력하세요: ";
   cin>>v;
   cout<<"\n그래프의 간선 개수를 입력하세요: ";
   cin>>e;
   int edge[e][2];
   for(i = 0; i < e; i++) {
      cout<<"\n간선 "<<i+1<<"의 정점 쌍을 입력하세요";
      cout<<"\nV(1): ";
      cin>>edge[i][0];
      cout<<"V(2): ";
      cin>>edge[i][1];
   }
   cout<<"\n\n주어진 그래프의 인시던스 리스트 표현: ";
   for(i = 0; i < e; i++) {
      // 각 간선마다 연결된 정점을 출력한다.
      cout<<"\n\tE("<<i+1<<") -> { ";
         cout<<"V("<<edge[i][0]<<") , "<<"V("<<edge[i][1]<<")";
         cout<<" }";
   }
}

코드 설명

위 코드의 동작 과정은 다음과 같습니다.

1. 사용자로부터 그래프의 정점 개수(v)와 간선 개수(e)를 입력받습니다.
2. 크기가 e×2인 2차원 배열 edge를 선언하여, 각 간선을 구성하는 두 정점의 번호를 저장합니다.
3. 모든 간선에 대해 반복문을 수행하며, 간선 번호와 함께 해당 간선이 연결하는 두 정점을 형식에 맞춰 출력합니다.

실행 결과

그래프의 정점 개수를 입력하세요: 3
그래프의 간선 개수를 입력하세요: 4
간선 1의 정점 쌍을 입력하세요
V(1): 2
V(2): 1
간선 2의 정점 쌍을 입력하세요
V(1): 1
V(2): 2
간선 3의 정점 쌍을 입력하세요
V(1): 3
V(2): 2
간선 4의 정점 쌍을 입력하세요
V(1): 2
V(2): 3
주어진 그래프의 인시던스 리스트 표현:
E(1) -> { V(2) , V(1) }
E(2) -> { V(1) , V(2) }
E(3) -> { V(3) , V(2) }
E(4) -> { V(2) , V(3) }

마무리

인시던스 리스트는 간선 중심으로 그래프를 표현하기 때문에, 특정 간선이 어떤 정점들을 연결하는지 빠르게 확인해야 하는 상황에서 유용합니다. 위 예제처럼 간선 정보를 배열에 저장한 뒤 순회하며 출력하기만 하면 되므로, 구현이 간단하면서도 O(e)의 선형 시간 복잡도를 보장합니다.