已知一个有向图的邻接表，编写C语言算法建立其逆邻接表

为了建立有向图的逆邻接表，我们需要遍历整个邻接表，将每个顶点的出边转化为入边，然后将这些入边插入到相应的顶点的逆邻接表中。具体实现步骤如下：

void InvertAdjList(AdjList gin, AdjList gout) {
    int i, j;
    ArcNode *p, *s;
    for (i = 1; i <= n; i++) {
        // 复制顶点信息
        strcpy(gin[i].vertex, gout[i].vertex);
        // 初始化逆邻接表
        gin[i].firstarc = NULL;
    }
    for (i = 1; i <= n; i++) {
        // 遍历邻接表
        p = gout[i].firstarc;
        while (p != NULL) {
            j = p->adjvex;
            // 将边插入到相应的逆邻接表中
            s = (ArcNode*)malloc(sizeof(ArcNode));
            s->adjvex = i;
            s->nextarc = gin[j].firstarc;
            gin[j].firstarc = s;
            p = p->nextarc;
        }
    }
}

相关问题

已知有一个有向图的邻接表，试用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;
}

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

求邻接表表示的有向图各顶点的入度 正文: 已知有一个有向图的邻接表，试编写一个算法，计算各顶点的入度。用C语言实现

下面是用 C 语言实现计算有向图各顶点入度的算法，假设邻接表用一个指针数组来表示，每个指针指向一个链表，链表中存储该顶点指向的其他顶点。

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

#define MAX_VERTICES 100

// 邻接表中的链表节点
typedef struct Node {
    int dest;           // 目标顶点编号
    struct Node* next;  // 链表中的下一个节点
} Node;

// 邻接表中的顶点
typedef struct Vertex {
    Node* head;         // 链表头指针
    int in_degree;      // 顶点入度
} Vertex;

// 邻接表表示的有向图
typedef struct Graph {
    Vertex vertices[MAX_VERTICES];  // 顶点数组
    int num_vertices;               // 顶点数
} Graph;

// 初始化有向图
void init_graph(Graph* graph, int num_vertices) {
    graph->num_vertices = num_vertices;
    for (int i = 0; i < num_vertices; i++) {
        graph->vertices[i].head = NULL;
        graph->vertices[i].in_degree = 0;
    }
}

// 添加有向边
void add_edge(Graph* graph, int src, int dest) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->dest = dest;
    new_node->next = graph->vertices[src].head;
    graph->vertices[src].head = new_node;

    graph->vertices[dest].in_degree++;
}

// 计算各顶点的入度
void calc_in_degree(Graph* graph) {
    for (int i = 0; i < graph->num_vertices; i++) {
        Node* p = graph->vertices[i].head;
        while (p != NULL) {
            graph->vertices[p->dest].in_degree++;
            p = p->next;
        }
    }
}

// 打印各顶点的入度
void print_in_degree(Graph* graph) {
    for (int i = 0; i < graph->num_vertices; i++) {
        printf("Vertex %d has in-degree %d\n", i, graph->vertices[i].in_degree);
    }
}

// 测试代码
int main() {
    Graph graph;
    init_graph(&graph, 5);
    add_edge(&graph, 0, 1);
    add_edge(&graph, 0, 2);
    add_edge(&graph, 1, 2);
    add_edge(&graph, 2, 3);
    add_edge(&graph, 4, 1);
    add_edge(&graph, 4, 2);

    calc_in_degree(&graph);
    print_in_degree(&graph);

    return 0;
}

输出结果为：

Vertex 0 has in-degree 0
Vertex 1 has in-degree 2
Vertex 2 has in-degree 3
Vertex 3 has in-degree 1
Vertex 4 has in-degree 0

其中，邻接表表示的有向图如下所示：

0 -> 1 -> 2
    |
    v
    2 -> 3
4 -> 1 -> 2