考研真题数据结构

【2022山西大学考研真题】设计一个算法，统计一个采用邻接表存储的具有n个顶点的无向无权图

所有顶点的度。

（1）给出算法的基本思想；

（2）根据设计思想，给出描述的算法。

（3）求出所用算法的时间复杂度。

（1）算法的基本思想如下：

1.?遍历图中的所有顶点，统计每个顶点的度。
2.?对于每个顶点，遍历其邻接表，统计其邻接点的个数即为该顶点的度。

（2）下面是使用C语言描述这个算法的代码：

typedef?struct?Node?{
????int?vertex;
????struct?Node*?next;
}?Node;

typedef?struct?Graph?{
????int?numVertices;
????Node**?adjacencyList;
}?Graph;

//?统计图中所有顶点的度
void?degreeOfVertices(Graph*?graph)?{
????for?(int?i?=?0;?i?<?graph->numVertices;?i++)?{
????????int?degree?=?0;
????????Node*?current?=?graph->adjacencyList[i];
????????
????????while?(current?!=?NULL)?{
????????????degree++;
????????????current?=?current->next;
????????}
????????
????????printf("顶点?%d?的度为?%d\n",?i,?degree);
????}
}

（3）算法的时间复杂度是?O(V+E)，其中?V?是顶点数，E?是边数。我们需要遍历每个顶点的邻接表，并统计度数。

?