假设不带权有向图采用邻接表 G 存储,下面算法的功能是:求出图中每个顶点的入度。 请在空白处填入正确的语句。 //求出图 G 中每个顶点的入度void InDs(ALGraph *G) { ArcNode *p; //A 存放各顶点的入度 int A[MAX_VERTEX_NUM], i; //A 中元素置初值 0 for(i = 0; _________; i++) _____________; for(i = 0; i < G->n; i++) { //扫描所有头结点 p = ____________; while(p != NULL) { //扫描边结点 ____________; //表示 i 到 p->adjvex 顶点有一条边 p = p->nextarc; } } printf("各顶点入度:\n"); //输出各顶点的入度 for(i = 0; i < G->n; i++) printf(" 顶点%d:%d\n", i, A[i]); }
时间: 2024-01-29 19:02:47 浏览: 24
空白处填写的语句是:
```
for(i = 0; i < G->n; i++)
A[i] = 0;
```
第一行的循环是为了初始化 A 数组,将每个顶点的入度都初始化为 0。
第二个循环是为了遍历图中的每个顶点,对于每个顶点,通过访问其邻接表中的边结点来更新其入度。
最后一个循环是为了输出每个顶点的入度,即 A 数组中的值。
相关问题
假设有向图g采用邻接表存储,设计一个算法求出图g每个顶点的入度
可以遍历邻接表中的每个顶点,并统计每个顶点的入度。具体地,可以定义一个数组in_degree,初始值都为0,然后遍历邻接表,对于每个顶点v的邻接表中的每个顶点u,都将in_degree[u]增加1。最终in_degree数组中的每个元素即为对应顶点的入度。
以下是具体的算法实现:
```python
def get_in_degree(adj_list):
n = len(adj_list)
in_degree = [0] * n
for u in range(n):
for v in adj_list[u]:
in_degree[v] += 1
return in_degree
```
其中,adj_list是邻接表,n是顶点数。算法的时间复杂度是O(m+n),其中m是边数。
假设有向图g采用邻接表存储,设计一个算法求出图g每个顶点的入度,用C语言写
可以使用C语言实现上述算法,具体代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 1000
typedef struct node {
int val;
struct node* next;
} Node;
int in_degree[MAX_N];
Node* create_node(int val) {
Node* node = (Node*) malloc(sizeof(Node));
node->val = val;
node->next = NULL;
return node;
}
void add_edge(Node** adj_list, int u, int v) {
Node* node = create_node(v);
node->next = adj_list[u];
adj_list[u] = node;
}
void get_in_degree(Node** adj_list, int n) {
for (int u = 0; u < n; u++) {
Node* cur = adj_list[u];
while (cur != NULL) {
int v = cur->val;
in_degree[v]++;
cur = cur->next;
}
}
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
Node* adj_list[MAX_N] = {0};
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
add_edge(adj_list, u, v);
}
get_in_degree(adj_list, n);
for (int u = 0; u < n; u++) {
printf("in_degree[%d] = %d\n", u, in_degree[u]);
}
return 0;
}
```
其中,Node结构体表示邻接表中的一个节点,包括节点值val和指向下一个节点的指针next。create_node函数创建一个新节点,add_edge函数将一条边从u连向v,get_in_degree函数计算每个顶点的入度,最后在main函数中输出每个顶点的入度。