7-20 有向图输出入度为0顶点 分数 6 作者 DS课程组 单位 临沂大学 本题要求实现一个函数，输出有向图所有入度为0的顶点。 函数接口定义： void PrintV(MGraph G); G为采用邻接矩阵作为存储结构的有向图。 裁判测试程序样例： #include <stdio.h> #define MVNum 100 //最大顶点数 typedef struct { char vexs[MVNum]; //存放顶点的一维数组 int arcs[MVNum][MVNum]; //邻接矩阵 int vexnum, arcnum; //图的当前顶点数和弧数 }MGraph; void PrintV(MGraph G); void CreatMGraph(MGraph *G);/* 创建图 */ int main() { MGraph G; CreatMGraph(&G); PrintV(G); return 0; } void CreatMGraph(MGraph *G) { int i, j, k; scanf("%d%d", &G->vexnum, &G->arcnum); getchar(); for (i = 0; i < G->vexnum; i++) scanf("%c", &G->vexs[i]); for (i = 0; i < G->vexnum; i++) for (j = 0; j < G->vexnum; j++) G->arcs[i][j] = 0; for (k = 0; k < G->arcnum; k++) { scanf("%d%d", &i, &j); G->arcs[i][j] = 1; } } /* 你的代码将被嵌在这里 */ 输入样例： 例如有向图 有向图.png 第一行给出图的顶点数n和弧数e。第二行给出n个字符，表示n个顶点的数据元素的值。后面是e行，给出每一条弧的两个顶点编号。 4 5 ABCD 1 0 2 0 2 1 3 2 3 1 输出样例： 输出为两行，第一行为入度为0的顶点个数，第二行按照输入顺序输出所有入度为0的顶点元素值。顶点的元素值为字符型，输出格式为每个字符后面跟一个空格。如果没有入度为0的顶点，则输出只有一行，个数为0。 1 D

思路：遍历每个顶点，统计其入度，入度为0则输出。为了方便输出入度为0的顶点的元素值，可以开一个数组记录每个顶点的元素值。

代码实现：

void PrintV(MGraph G) {
    int inDegree[MVNum] = {0};  // 入度数组
    char elem[MVNum];           // 元素值数组
    int idx = 0;                // 元素值数组下标
    for (int i = 0; i < G.vexnum; i++) {
        for (int j = 0; j < G.vexnum; j++) {
            if (G.arcs[j][i]) { // 统计入度
                inDegree[i]++;
            }
        }
        if (inDegree[i] == 0) { // 入度为0
            elem[idx++] = G.vexs[i];
        }
    }
    printf("%d\n", idx);        // 输出入度为0的顶点个数
    for (int i = 0; i < idx; i++) {
        printf("%c ", elem[i]); // 输出入度为0的顶点元素值
    }
}

相关问题

7-1 入度与出度分数 10作者 黄龙军单位 绍兴文理学院求有向图g中各顶点的入度与出

有向图中，每个顶点有两个相关的度数，即入度和出度。

入度表示指向该顶点的边的数量，而出度表示从该顶点出发的边的数量。

假设有向图g有n个顶点，则每个顶点的入度与出度可以用两个n维向量来表示。

设向量D表示每个顶点的入度，向量O表示每个顶点的出度，则有：

D = [d1, d2, ..., dn]，O = [o1, o2, ..., on]

其中，di表示第i个顶点的入度，oi表示第i个顶点的出度。

通过遍历每个顶点，可以计算出它们的入度和出度。

具体计算方法如下：

1. 初始化D和O为长度为n的全0向量。
2. 遍历有向图g的每个边，若边的起点是i，终点是j，则将D的第j个元素增加1（即dj = dj + 1），将O的第i个元素增加1（即oi = oi + 1）。
3. 遍历完成后，得到了每个顶点的入度和出度。

举个例子，假设有向图g有4个顶点，边的表示如下：

1 -> 2
1 -> 3
2 -> 3
3 -> 4

则有：

D = [0, 2, 2, 1]
O = [0, 1, 2, 1]

其中，顶点1的入度为0，出度为2；顶点2的入度为2，出度为1；顶点3的入度为2，出度为2；顶点4的入度为1，出度为1。

通过计算每个顶点的入度和出度，可以帮助我们更好地理解有向图的结构，并在分析图的特性和性质时提供参考依据。

采用邻接表作为有向图的存储结构的有向图中入度为n的顶点的个数

在邻接表中，每个顶点对应一个链表，链表中存储该顶点指向的所有其他顶点。因此，对于每个顶点，我们可以通过遍历与其相关的所有链表来计算其出度。而入度则需要遍历整个图，并计算每个顶点指向该顶点的边的数量。这个过程的时间复杂度为 O(V+E)，其中 V 是顶点数，E 是边数。

所以，如果有向图中有一个入度为 n 的顶点，那么需要遍历整个图来计算该顶点的入度。在遍历过程中，需要对每个顶点都计算一次其入度。因此，时间复杂度为 O(V+E)。最终入度为 n 的顶点的个数取决于具体的图的结构，无法通过存储结构来确定。