检查星图
给出了一个图表；我们必须检查给定的图是否是星图。
通过遍历图，我们必须找到度数为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: 它是一个星图。
算法
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输出结果#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++) { //对于大于2的图 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 << "它是一个星图。"; else cout << "它不是星图。"; }
它是一个星图。