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。

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

相关问题

c语言求有向图中每个顶点的入度和出度

对于一个有向图，每个顶点的入度和出度可以通过遍历图中所有的边来计算。

1. 入度：对于每个顶点，遍历所有的边，统计指向该顶点的边的数量即为该顶点的入度。

2. 出度：对于每个顶点，遍历所有的边，统计从该顶点出发的边的数量即为该顶点的出度。

具体的代码实现可以参考下面的示例：

#include <stdio.h>
#define MAX_VERTEX_NUM 100   // 最大顶点数

// 边的结构体
typedef struct {
    int tail;   // 起点
    int head;   // 终点
} Arc;

// 有向图的结构体
typedef struct {
    Arc arcs[MAX_VERTEX_NUM];   // 存储所有边的数组
    int indegree[MAX_VERTEX_NUM];   // 存储每个顶点的入度
    int outdegree[MAX_VERTEX_NUM];   // 存储每个顶点的出度
    int vexnum;   // 顶点数
    int arcnum;   // 边数
} Graph;

// 初始化有向图
void initGraph(Graph *G) {
    int i;
    for (i = 0; i < G->vexnum; i++) {
        G->indegree[i] = 0;
        G->outdegree[i] = 0;
    }
}

// 计算每个顶点的入度和出度
void calcDegree(Graph *G) {
    int i;
    for (i = 0; i < G->arcnum; i++) {
        int tail = G->arcs[i].tail;
        int head = G->arcs[i].head;
        G->outdegree[tail]++;
        G->indegree[head]++;
    }
}

int main() {
    Graph G;
    int i;

    printf("请输入顶点数和边数：");
    scanf("%d%d", &G.vexnum, &G.arcnum);

    printf("请依次输入每条边的起点和终点：\n");
    for (i = 0; i < G.arcnum; i++) {
        scanf("%d%d", &G.arcs[i].tail, &G.arcs[i].head);
    }

    initGraph(&G);
    calcDegree(&G);

    printf("每个顶点的入度和出度分别为：\n");
    for (i = 0; i < G.vexnum; i++) {
        printf("顶点%d：入度%d，出度%d\n", i, G.indegree[i], G.outdegree[i]);
    }

    return 0;
}

这里我们用结构体表示有向图，包括顶点数、边数、边的数组以及每个顶点的入度和出度数组。然后通过遍历边的数组，统计每个顶点的入度和出度，最后输出每个顶点的入度和出度即可。

算法设计求有向图中每个顶点的入度和出度

好的，根据您的要求，我来为您编写这个算法。

假设有向图的邻接表存储结构如下：

typedef struct ArcNode {
    int adjvex;                 // 邻接点在顶点数组中的下标
    struct ArcNode *nextarc;    // 指向下一个邻接点的指针
} ArcNode;

typedef struct VNode {
    int data;                   // 顶点的数据
    ArcNode *firstarc;          // 指向第一个邻接点的指针
    int indegree;               // 顶点的入度
    int outdegree;              // 顶点的出度
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices;           // 存储各个顶点的邻接表
    int vexnum, arcnum;         // 图的顶点数和弧数
} ALGraph;

1. 求每个顶点的入度

对于有向图中的每个顶点，可以遍历整个邻接表，统计指向该顶点的弧的条数，即为该顶点的入度。具体算法如下：

void indegree(ALGraph *G) {
    // 初始化每个顶点的入度为0
    for (int i = 0; i < G->vexnum; i++) {
        G->vertices[i].indegree = 0;
    }
    // 遍历整个邻接表，统计每个顶点的入度
    for (int i = 0; i < G->vexnum; i++) {
        ArcNode *p = G->vertices[i].firstarc;
        while (p != NULL) {
            G->vertices[p->adjvex].indegree++;
            p = p->nextarc;
        }
    }
}

2. 求每个顶点的出度

对于有向图中的每个顶点，可以遍历该顶点的邻接表，统计该顶点指向其他顶点的弧的条数，即为该顶点的出度。具体算法如下：

void outdegree(ALGraph *G) {
    // 初始化每个顶点的出度为0
    for (int i = 0; i < G->vexnum; i++) {
        G->vertices[i].outdegree = 0;
    }
    // 遍历每个顶点的邻接表，统计每个顶点的出度
    for (int i = 0; i < G->vexnum; i++) {
        ArcNode *p = G->vertices[i].firstarc;
        while (p != NULL) {
            G->vertices[i].outdegree++;
            p = p->nextarc;
        }
    }
}

希望能够帮助到您！