C数据结构图的邻接表求度
时间: 2023-12-07 20:39:24 浏览: 30
为了求出图的邻接表中每个顶点的度,我们需要遍历整个邻接表,对于每个顶点,统计其对应链表中的元素个数即可。具体实现方法如下:
```c
// 定义邻接表中的链表结构体
typedef struct AdjListNode {
int dest;
struct AdjListNode* next;
} AdjListNode;
// 定义邻接表结构体
typedef struct Graph {
int V; // 顶点数量
AdjListNode** array; // 邻接表数组
} Graph;
// 创建一个新的邻接表节点
AdjListNode* newAdjListNode(int dest) {
AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
// 创建一个邻接表
Graph* createGraph(int V) {
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->V = V;
graph->array = (AdjListNode**)malloc(V * sizeof(AdjListNode*));
for (int i = 0; i < V; ++i) {
graph->array[i] = NULL;
}
return graph;
}
// 添加一条边到无向图中
void addEdge(Graph* graph, int src, int dest) {
// 添加一条从源节点到目标节点的边
AdjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->array[src];
graph->array[src] = newNode;
// 添加一条从目标节点到源节点的边
newNode = newAdjListNode(src);
newNode->next = graph->array[dest];
graph->array[dest] = newNode;
}
// 求图中每个顶点的度
void printDegrees(Graph* graph) {
for (int i = 0; i < graph->V; ++i) {
int degree = 0;
AdjListNode* node = graph->array[i];
while (node) {
degree++;
node = node->next;
}
printf("Vertex %d has degree %d\n", i, degree);
}
}
```