考研真题数据结构

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

所有顶点的度。

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

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

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

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

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

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

```c
#include <stdio.h>
#include <stdlib.h>

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

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

// 创建图
Graph* createGraph(int numVertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = numVertices;

    graph->adjacencyList = (Node**)malloc(numVertices * sizeof(Node*));
    for (int i = 0; i < numVertices; i++) {
        graph->adjacencyList[i] = NULL;
    }

    return graph;
}

// 添加边
void addEdge(Graph* graph, int src, int dest) {
    // 添加从src到dest的边
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = graph->adjacencyList[src];
    graph->adjacencyList[src] = newNode;

    // 添加从dest到src的边（无向图）
    newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = src;
    newNode->next = graph->adjacencyList[dest];
    graph->adjacencyList[dest] = newNode;
}

// 统计图中所有顶点的度
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);
    }
}

// 测试代码
int main() {
    int numVertices = 6;
    Graph* graph = createGraph(numVertices);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 0, 3);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);
    addEdge(graph, 2, 4);
    addEdge(graph, 3, 4);
    addEdge(graph, 4, 5);

    degreeOfVertices(graph);

    return 0;
}
```

在上述代码中，我们首先定义了一个 `Node` 结构体来表示邻接表中的节点，以及一个 `Graph` 结构体来表示图。然后，我们实现了创建图、添加边和统计图中所有顶点度的函数。在 `main` 函数中，我们创建了一个测试用例并进行度的统计。

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