그래프가 제공됩니다. 주어진 그래프가 별 그래프인지 확인해야 합니다.
그래프를 순회함으로써 우리는 차수가 1인 꼭짓점의 수와 차수가 n-1인 꼭짓점의 수를 찾아야 합니다. (여기서 n은 주어진 그래프의 정점 수입니다). 차수가 1인 꼭짓점의 수가 n-1이고 차수(n-1)인 꼭짓점이 1이면 별 그래프입니다.
입력 및 출력
Input: The adjacency matrix: 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 Output: It is a star graph.
알고리즘
checkStarGraph(graph)
입력: 주어진 그래프.
출력: 그래프가 별 그래프인 경우 참입니다.
Begin degOneVert := 0 and degNminOneGraph := 0 if graph has only one vertex, then return true, if there is no self-loop else if graph has two vertices, then return true if there is only one vertex between two vertices else for all vertices i in the graph, do degree := 0 for all vertices j, adjacent with i, do degree := degree + 1 done if degree = 1, then degOneVert := degOneVert + 1 else if degree = n-1, then degNminOneGraph := degNminOneGraph + 1 done if degOneVert = n-1, and degNminOneGraph = 1, then return true otherwise return false End
예시
#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; //initially vertex with degree 1 and with degree n - 1 are 0 if (NODE == 1) //when there is only one node 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++) { //for graph more than 2 int degree = 0; for (int j = 0; j < NODE; j++) //count degree for vertex i if (graph[i][j]) degree++; if (degree == 1) degOneVert++; else if (degree == NODE-1) degVert++; } //when only vertex of degree n-1, and all other vertex of degree 1, it is a star graph 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.