c语言已知某有向图（n个结点）的邻接表，求该图各结点的入度数

对于一个有向图的邻接表表示，我们可以通过遍历整个邻接表来计算每个节点的入度数。

首先，我们需要初始化一个大小为n的数组indegree，用于存储每个节点的入度数。将数组中的所有元素初始化为0。

然后，我们遍历整个邻接表。对于每个节点v，我们遍历其邻接链表中的所有节点，并将对应节点的入度数加1。具体步骤如下：

1. 遍历邻接表中的每个节点v：
- 获取节点v的邻接链表头指针adjList[v]。
- 初始化一个指针p，指向邻接链表头指针adjList[v]。
- 循环遍历邻接链表，直到p为空：
- 获取当前节点p所指向的顶点w。
- 将顶点w的入度数加1：indegree[w]++。
- 将指针p移动到下一个节点：p = p->next。

这样，遍历完成后，数组indegree中存储了每个节点的入度数。可以根据需要使用该数组进行后续操作。

相关问题

已知某有向图（n个结点）的邻接表，求该图各结点的入度数。用C语言写代码

为了求解有向图中各节点的入度数，我们可以使用邻接表表示图的数据结构。遍历每个节点的邻接表，并统计指向该节点的边的数量，即为该节点的入度数。

以下是使用C语言编写的求解有向图各节点入度数的代码示例：

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100

// 邻接表的链表节点
struct Node {
    int vertex;
    struct Node* next;
};

// 图的结构体
struct Graph {
    struct Node* adjLists[MAX_VERTICES];
};

// 创建新节点
struct Node* createNode(int v) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// 创建图
struct Graph* createGraph() {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    for (int i = 0; i < MAX_VERTICES; i++) {
        graph->adjLists[i] = NULL;
    }
    return graph;
}

// 添加边
void addEdge(struct Graph* graph, int src, int dest) {
    // 添加 src -> dest 边
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
}

// 计算节点的入度数
int calculateIndegree(struct Graph* graph, int vertex) {
    int indegree = 0;
    for (int i = 0; i < MAX_VERTICES; i++) {
        struct Node* node = graph->adjLists[i];
        while (node != NULL) {
            if (node->vertex == vertex) {
                indegree++;
            }
            node = node->next;
        }
    }
    return indegree;
}

int main() {
    struct Graph* graph = createGraph();
    int numVertices, numEdges;

    // 输入顶点数和边数
    printf("Enter the number of vertices: ");
    scanf("%d", &numVertices);
    printf("Enter the number of edges: ");
    scanf("%d", &numEdges);

    // 输入边信息
    for (int i = 0; i < numEdges; i++) {
        int src, dest;
        printf("Enter edge %d (source destination): ", i + 1);
        scanf("%d %d", &src, &dest);
        addEdge(graph, src, dest);
    }

    // 计算并打印各节点的入度数
    printf("Indegree of each vertex:\n");
    for (int i = 0; i < numVertices; i++) {
        int indegree = calculateIndegree(graph, i);
        printf("Vertex %d: %d\n", i, indegree);
    }

    return 0;
}

在上述代码中，我们首先定义了邻接表的链表节点结构 `Node` 和图的结构体 `Graph`。然后，我们实现了创建新节点、创建图、添加边和计算节点入度数的函数。在 `main` 函数中，我们先输入顶点数和边数，然后输入边的信息并使用邻接表表示图。接下来，我们调用 `calculateIndegree` 函数计算每个节点的入度数，并打印出结果。

注意：上述代码仅为示例，实际使用时需要根据实际情况进行修改。同时，为了简化示例，我们没有进行输入验证和错误处理，请在实际应用中进行适当的验证和错误处理。

已知有一个有向图的邻接表，试用C语言编写一个算法，计算各顶点的入度，输出运行结果

以下是计算各顶点入度的C语言代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100

/* 邻接表中的边结构体 */
typedef struct EdgeNode {
    int adjvex;                     // 相邻节点编号
    struct EdgeNode* next_edge;     // 下一个边结点指针
} EdgeNode;

/* 邻接表中的顶点结构体 */
typedef struct VertexNode {
    int vertex;                     // 顶点编号
    EdgeNode* first_edge;           // 第一个边结点指针
} VertexNode;

/* 邻接表结构体 */
typedef struct AdjList {
    VertexNode vertices[MAX_VERTICES];  // 顶点数组
    int num_vertices;                   // 顶点数
} AdjList;

/* 初始化邻接表 */
void init_adj_list(AdjList* adj_list) {
    int i;
    adj_list->num_vertices = 0;
    for (i = 0; i < MAX_VERTICES; i++) {
        adj_list->vertices[i].first_edge = NULL;
    }
}

/* 向邻接表中插入一条边 */
void insert_edge(AdjList* adj_list, int from_vertex, int to_vertex) {
    EdgeNode* new_edge = (EdgeNode*)malloc(sizeof(EdgeNode));
    new_edge->adjvex = to_vertex;
    new_edge->next_edge = adj_list->vertices[from_vertex].first_edge;
    adj_list->vertices[from_vertex].first_edge = new_edge;
}

/* 计算各顶点入度 */
void calc_indegree(AdjList* adj_list, int* indegrees) {
    int i;
    EdgeNode* cur_edge;
    for (i = 0; i < adj_list->num_vertices; i++) {
        indegrees[i] = 0;               // 初始化入度为0
    }
    for (i = 0; i < adj_list->num_vertices; i++) {
        cur_edge = adj_list->vertices[i].first_edge;
        while (cur_edge != NULL) {
            indegrees[cur_edge->adjvex]++;  // 计算入度
            cur_edge = cur_edge->next_edge;
        }
    }
}

/* 主函数 */
int main() {
    AdjList adj_list;
    int indegrees[MAX_VERTICES];
    int i;

    init_adj_list(&adj_list);

    // 向邻接表中插入边
    insert_edge(&adj_list, 0, 1);
    insert_edge(&adj_list, 0, 2);
    insert_edge(&adj_list, 1, 2);
    insert_edge(&adj_list, 2, 0);
    insert_edge(&adj_list, 2, 3);
    insert_edge(&adj_list, 3, 3);

    // 计算各顶点入度
    calc_indegree(&adj_list, indegrees);

    // 输出各顶点入度
    for (i = 0; i < adj_list.num_vertices; i++) {
        printf("Vertex %d indegree: %d\n", i, indegrees[i]);
    }

    return 0;
}

以上代码中，我们首先定义了邻接表的数据结构，并实现了初始化邻接表和向邻接表中插入一条边的函数。然后，我们实现了计算各顶点入度的函数，并在主函数中调用这个函数计算各顶点入度并输出结果。