별 그래프란 무엇인가?
하나의 그래프가 주어졌을 때, 이 그래프가 별 그래프(star graph)인지 아닌지를 판별하는 문제입니다.
별 그래프는 하나의 중심 정점이 나머지 모든 정점과 간선으로 연결되어 있고, 중심 정점을 제외한 정점들 사이에는 어떠한 간선도 존재하지 않는 트리 형태의 그래프입니다. 마치 별이 빛을 뻗는 모습과 닮았다고 하여 '별 그래프'라고 부릅니다.
따라서 그래프를 순회하면서 차수(degree)가 1인 정점의 개수와 차수가 n-1인 정점의 개수를 구해야 합니다. (여기서 n은 주어진 그래프의 정점 개수입니다.) 차수가 1인 정점이 n-1개이고, 차수가 n-1인 정점이 정확히 1개라면 해당 그래프는 별 그래프입니다.
입력 및 출력
입력 (인접 행렬): 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 출력: It is a star graph. (별 그래프입니다.)
알고리즘
checkStarGraph(graph)
입력: 주어진 그래프
출력: 그래프가 별 그래프이면 참(true), 아니면 거짓(false)
의사 코드(Pseudocode)
시작
degOneVert := 0, degNminOneGraph := 0
만약 그래프에 정점이 하나뿐이라면
자기 루프(self-loop)가 없으면 true 반환
아니면 만약 그래프에 정점이 두 개라면
두 정점 사이에 간선이 하나만 존재하면 true 반환
아니면
그래프의 모든 정점 i에 대해 반복
degree := 0
i와 인접한 모든 정점 j에 대해 반복
degree := degree + 1
종료
만약 degree = 1이면
degOneVert := degOneVert + 1
아니면 만약 degree = n-1이면
degNminOneGraph := degNminOneGraph + 1
종료
만약 degOneVert = n-1이고 degNminOneGraph = 1이면
true 반환
그렇지 않으면 false 반환
종료C++ 구현 예제
#include<iostream>
#define NODE 4
using namespace std;
int graph[NODE][NODE] = {
{0, 1, 1, 1},
{1, 0, 0, 0},
{1, 0, 0, 0},
{1, 0, 0, 0}
};
bool checkStarGraph() {
int degOneVert = 0, degVert = 0; //초기에 차수가 1인 정점과 차수가 n-1인 정점의 개수는 0
if (NODE == 1) //정점이 하나뿐인 경우
return (graph[0][0] == 0);
if (NODE == 2)
return (graph[0][0] == 0 && graph[0][1] == 1 && graph[1][0] == 1 && graph[1][1] == 0 );
for (int i = 0; i < NODE; i++) { //정점이 3개 이상인 그래프 처리
int degree = 0;
for (int j = 0; j < NODE; j++) //정점 i의 차수 계산
if (graph[i][j])
degree++;
if (degree == 1)
degOneVert++;
else if (degree == NODE-1)
degVert++;
}
//차수가 n-1인 정점이 하나뿐이고, 나머지 정점의 차수가 모두 1이면 별 그래프
return (degOneVert == (NODE-1) && degVert == 1);
}
int main() {
if(checkStarGraph())
cout << "It is a star graph.";
else
cout << "It is not a star graph.";
}실행 결과
It is a star graph.
시간 복잡도
위 알고리즘은 인접 행렬을 한 번 전체 순회하므로 시간 복잡도는 O(n²)입니다. 만약 인접 리스트(adjacency list)를 사용하여 그래프를 표현하면 각 정점의 차수를 더 효율적으로 얻을 수 있어, 시간 복잡도를 O(V+E)까지 줄일 수 있습니다.