ตรวจสอบกราฟดาว

ให้กราฟ; เราต้องเช็คว่ากราฟที่กำหนดเป็นกราฟดาวหรือเปล่า

โดยการสำรวจกราฟ เราต้องหาจำนวนจุดยอดที่มีดีกรีหนึ่ง และจำนวนจุดยอดที่มีดีกรีเป็น n-1 (ในที่นี้ n คือจำนวนจุดยอดในกราฟที่กำหนด) เมื่อจำนวนจุดยอดที่มีดีกรี 1 เป็น n-1 และจำนวนจุดยอดที่มีองศา (n-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.