假设不带权有向图采用邻接表G存储,用C语言设计实现以下功能的算法: (1)求出图中每个顶点的入度。 (2)求出图中每个顶点的出度。 (3)求出图中出度为0的顶点数。
时间: 2024-12-24 15:37:22 浏览: 3
在C语言中,我们可以使用邻接表(Adjacency List)的数据结构来存储不带权有向图。这里提供一个基本的实现思路:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int vertex;
struct Node* next; // 指向下一个节点的指针
} Node;
typedef struct Graph {
Node** adj; // 邻接列表,数组下标表示顶点
int vertices; // 顶点的数量
int edges; // 边的数量
} Graph;
// 功能:初始化一个空图
void initGraph(Graph* g, int v) {
g->vertices = v;
g->adj = (Node**)malloc(v * sizeof(Node*));
for(int i=0; i<v; i++) {
g->adj[i] = NULL;
}
}
// 功能:插入边(假设u指向v)
void addEdge(Graph* g, int src, int dest) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->vertex = dest;
newNode->next = g->adj[src];
g->adj[src] = newNode;
}
// 功能:求顶点的入度
int getInDegree(Graph* g, int v) {
int degree = 0;
if(g->adj[v]) {
Node* temp = g->adj[v];
while(temp) {
degree++;
temp = temp->next;
}
}
return degree;
}
// 功能:求顶点的出度
int getOutDegree(Graph* g, int v) {
int degree = 0;
if(g->adj[v]) {
degree = g->adj[v]->next ? 1 : 0; // 如果v有一个后续节点,则出度为1,否则为0
}
return degree;
}
// 功能:求出度为0的顶点数
int countVerticesWithZeroDegree(Graph* g) {
int count = 0;
for(int i=0; i<g->vertices; i++) {
if(getOutDegree(g, i) == 0)
count++;
}
return count;
}
// 示例
int main() {
Graph G;
initGraph(&G, 5); // 假设有5个顶点
// 添加一些边...
printf("In-degree of vertex 0: %d\n", getInDegree(&G, 0));
printf("Out-degree of vertex 1: %d\n", getOutDegree(&G, 1));
printf("Vertices with zero out-degree: %d\n", countVerticesWithZeroDegree(&G));
return 0;
}
```
这个实现仅是一个基础模板,实际应用中还需要处理添加边时可能出现的边界情况和内存管理等问题。同时,上述代码没有包含添加边的具体操作,你需要根据实际情况来完善这部分代码。
阅读全文