检查星图
给出了一个图表;我们必须检查给定的图是否是星图。
通过遍历图,我们必须找到度数为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 << "它不是星图。"; }
它是一个星图。