假设不带权有向图采用邻接表 G 存储,下面算法的功能是:求出图中出度为0的顶点数。 请在空白处填入正确的语句。 //求出图 G 中出度为 0 的顶点数 void ZeroOutDs(ALGraph *G) { int i, n; ArcNode *p; printf("出度为 0 的顶点:"); for(i = 0; i < _________; i++) { //扫描所有头结点 p = __________; n = 0; while(p != NULL) { //扫描边结点 n++; //累计出边的数 ______; } if(_________) //输出出边数为 0 的顶点编号 printf("%2d", i); } }
时间: 2024-02-08 20:03:12 浏览: 27
空白处填写的语句是:
```
G->n
G->vertices[i].firstarc
n++;
p = p->nextarc;
if (n == 0)
```
第一个循环是为了遍历图中的每个顶点,对于每个顶点,通过访问其邻接表中的边结点来判断其出度是否为 0。
在处理每个头结点时,我们需要通过 `p = G->vertices[i].firstarc` 获取其邻接表的第一个边结点。
然后,我们需要遍历该顶点的所有出边,即遍历该顶点的邻接表,对于每个邻接点,通过 `p->adjvex` 获取其顶点号,然后将计数器 `n` 加 1,同时将指针 `p` 指向下一个边结点,即 `p = p->nextarc`。
如果顶点的出度为 0,即 `n == 0`,则输出该顶点的编号,即 `printf("%2d", i)`。
最后,我们就可以求出图中出度为 0 的顶点数了。
相关问题
用C语言写出代码并给出输入实例及结果:已知有向图采用邻接表作为存储结构,设计算法求该图中每个顶点的出度和入度
以下是用C语言编写的代码,输入实例为一个有向图的邻接表表示:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
typedef struct EdgeNode {
int adjvex;
struct EdgeNode *next;
} EdgeNode;
typedef struct VertexNode {
int data;
EdgeNode *firstedge;
} VertexNode;
VertexNode adjList[MAX_VERTICES];
int inDegree[MAX_VERTICES], outDegree[MAX_VERTICES];
void addEdge(int u, int v) {
EdgeNode *newNode = (EdgeNode *) malloc(sizeof(EdgeNode));
newNode->adjvex = v;
newNode->next = adjList[u].firstedge;
adjList[u].firstedge = newNode;
}
void computeDegree(int n) {
int i;
EdgeNode *p;
for (i = 0; i < n; i++) {
p = adjList[i].firstedge;
while (p != NULL) {
outDegree[i]++;
inDegree[p->adjvex]++;
p = p->next;
}
}
}
int main() {
int n, m, i, u, v;
scanf("%d %d", &n, &m);
for (i = 0; i < n; i++) {
adjList[i].data = i;
adjList[i].firstedge = NULL;
inDegree[i] = outDegree[i] = 0;
}
for (i = 0; i < m; i++) {
scanf("%d %d", &u, &v);
addEdge(u, v);
}
computeDegree(n);
printf("Vertex\tInDegree\tOutDegree\n");
for (i = 0; i < n; i++) {
printf("%d\t%d\t%d\n", i, inDegree[i], outDegree[i]);
}
return 0;
}
```
输入实例:第一行包含两个整数 $n$ 和 $m$,分别表示有向图的顶点数和边数。接下来 $m$ 行,每行两个整数 $u$ 和 $v$,表示有一条从 $u$ 到 $v$ 的有向边。
```
6 8
0 1
0 2
1 2
1 3
2 3
2 4
3 5
4 5
```
输出结果:
```
Vertex InDegree OutDegree
0 0 2
1 1 2
2 2 2
3 2 1
4 1 1
5 2 0
```
其中,第一列为顶点编号,第二列为入度,第三列为出度。
c语言编写完整代码 假设带权有向图采用邻接表存储,顶点i,j已存在,设计一个算法删除一条给定的边<i,j>
以下是C语言实现带权有向图邻接表存储结构中删除一条给定边<i,j>的算法:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
// 边表结点
typedef struct ArcNode {
int adjvex; // 邻接点的位置
int weight; // 权值
struct ArcNode *next; // 指向下一个邻接点
} ArcNode;
// 顶点表结点
typedef struct VNode {
int data; // 顶点信息
ArcNode *firstarc; // 指向第一个邻接点
} VNode, AdjList[MAX_VERTEX_NUM];
// 邻接表存储结构
typedef struct {
AdjList vertices; // 顶点数组
int vexnum, arcnum; // 顶点数和边数
} ALGraph;
// 初始化图
void InitGraph(ALGraph *G)
{
int i;
G->vexnum = G->arcnum = 0;
for (i = 0; i < MAX_VERTEX_NUM; i++) {
G->vertices[i].firstarc = NULL;
}
}
// 增加一条边
void AddArc(ALGraph *G, int i, int j, int weight)
{
ArcNode *p, *q;
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = j;
p->weight = weight;
p->next = G->vertices[i].firstarc;
G->vertices[i].firstarc = p;
G->arcnum++;
}
// 删除一条边
void DeleteArc(ALGraph *G, int i, int j)
{
ArcNode *p, *q;
p = G->vertices[i].firstarc;
if (p->adjvex == j) { // 删除第一个结点
G->vertices[i].firstarc = p->next;
free(p);
} else {
while (p->next && p->next->adjvex != j) {
p = p->next;
}
if (p->next) { // 找到了要删除的结点
q = p->next;
p->next = q->next;
free(q);
}
}
G->arcnum--;
}
// 主函数
int main()
{
int i, j, weight;
ALGraph G;
InitGraph(&G);
// 增加边
AddArc(&G, 1, 2, 10);
AddArc(&G, 1, 3, 20);
AddArc(&G, 2, 1, 30);
AddArc(&G, 2, 3, 40);
AddArc(&G, 3, 1, 50);
AddArc(&G, 3, 2, 60);
// 删除边
DeleteArc(&G, 1, 2);
// 输出邻接表
for (i = 1; i <= G.vexnum; i++) {
printf("%d: ", G.vertices[i].data);
ArcNode *p = G.vertices[i].firstarc;
while (p) {
printf("%d[%d] ", p->adjvex, p->weight);
p = p->next;
}
printf("\n");
}
return 0;
}
```
在上面的代码中,我们首先定义了带权有向图的邻接表存储结构,然后实现了初始化图、增加边和删除边的三个函数。最后在主函数中增加了一些边,删除了一条边,并输出了邻接表。注意,这里我们只是对边进行了删除,而没有删除结点,如果需要删除结点,还需要考虑它是否有入度或出度。