有一个邻接表存储的图G,用c语言分别设计实现以下要求的算法:求出图中每个顶点的出度;计算图中出度为0的顶点数。
时间: 2024-02-27 14:54:35 浏览: 27
好的,针对您的问题,我来为您解答。
1. 求出图中每个顶点的出度
邻接表存储的图G,可以通过遍历每个顶点的邻接表,来求出该顶点的出度。具体实现如下:
```c
// 定义邻接表节点结构体
typedef struct AdjListNode {
int dest; // 该节点指向的顶点
struct AdjListNode* next; // 指向下一个邻接表节点的指针
} AdjListNode;
// 定义邻接表结构体
typedef struct AdjList {
AdjListNode* head; // 指向邻接表头节点的指针
} AdjList;
// 定义图结构体
typedef struct Graph {
int V; // 图中顶点个数
AdjList* array; // 指向邻接表数组的指针
} Graph;
// 求出图中每个顶点的出度
void printOutDegrees(Graph* graph) {
int i;
for (i = 0; i < graph->V; ++i) {
int outDegree = 0;
AdjListNode* cur = graph->array[i].head;
while (cur != NULL) {
++outDegree;
cur = cur->next;
}
printf("Vertex %d has out degree %d\n", i, outDegree);
}
}
```
2. 计算图中出度为0的顶点数
计算图中出度为0的顶点数很简单,只需遍历每个顶点的邻接表,若邻接表为空,则该顶点的出度为0。具体实现如下:
```c
// 计算图中出度为0的顶点数
int countVerticesWithZeroOutDegree(Graph* graph) {
int count = 0;
int i;
for (i = 0; i < graph->V; ++i) {
if (graph->array[i].head == NULL) {
++count;
}
}
return count;
}
```
希望能够帮助您解决问题。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)