根据G的邻接表生成反向邻接表代码

以下是根据G的邻接表生成反向邻接表的Python代码：

def reverse_adj_list(adj_list):
    rev_adj_list = {v: [] for v in adj_list}
    for u in adj_list:
        for v in adj_list[u]:
            rev_adj_list[v].append(u)
    return rev_adj_list

其中，`adj_list`是一个字典，表示有向图G的邻接表，`rev_adj_list`是生成的反向邻接表。

相关问题

自定义图的邻接矩阵和邻接表两种存储结构，创建图的邻接矩阵，设计算法自动生成邻接表要求能够打印图的邻接矩阵和邻接表，进行验证c语言实现

以下是C语言实现图的邻接矩阵和邻接表的代码：

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

#define MAX_VERTEX_NUM 20

// 定义邻接矩阵结构体
typedef struct {
    int vertex[MAX_VERTEX_NUM]; // 顶点数组
    int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵数组
    int vertex_num, arc_num; // 顶点数和边数
} MGraph;

// 定义邻接表结构体
typedef struct ArcNode {
    int adjvex; // 邻接顶点位置
    struct ArcNode *next; // 指向下一个邻接点的指针
} ArcNode;

typedef struct VNode {
    int vertex; // 顶点的值
    ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode;

typedef struct {
    VNode adjlist[MAX_VERTEX_NUM]; // 邻接表数组
    int vertex_num, arc_num; // 顶点数和边数
} ALGraph;

// 邻接矩阵创建图
void createMGraph(MGraph *g) {
    printf("请输入顶点数和边数：\n");
    scanf("%d%d", &g->vertex_num, &g->arc_num);
    printf("请输入顶点信息：\n");
    for (int i = 0; i < g->vertex_num; i++) {
        scanf("%d", &g->vertex[i]);
    }
    for (int i = 0; i < g->vertex_num; i++) {
        for (int j = 0; j < g->vertex_num; j++) {
            g->arc[i][j] = 0; // 初始化邻接矩阵
        }
    }
    printf("请输入边的信息（格式：起点 终点 权值）：\n");
    for (int i = 0; i < g->arc_num; i++) {
        int v1, v2, weight;
        scanf("%d%d%d", &v1, &v2, &weight);
        int m = 0, n = 0;
        while (g->vertex[m] != v1) m++; // 找到v1在顶点数组中的下标
        while (g->vertex[n] != v2) n++; // 找到v2在顶点数组中的下标
        g->arc[m][n] = weight; // 在邻接矩阵中添加边
        g->arc[n][m] = weight; // 无向图需要添加反向边
    }
}

// 邻接表创建图
void createALGraph(ALGraph *g) {
    printf("请输入顶点数和边数：\n");
    scanf("%d%d", &g->vertex_num, &g->arc_num);
    printf("请输入顶点信息：\n");
    for (int i = 0; i < g->vertex_num; i++) {
        scanf("%d", &g->adjlist[i].vertex);
        g->adjlist[i].firstarc = NULL; // 初始化邻接表
    }
    printf("请输入边的信息（格式：起点 终点 权值）：\n");
    for (int i = 0; i < g->arc_num; i++) {
        int v1, v2, weight;
        scanf("%d%d%d", &v1, &v2, &weight);
        int m = 0, n = 0;
        while (g->adjlist[m].vertex != v1) m++; // 找到v1在邻接表中的位置
        while (g->adjlist[n].vertex != v2) n++; // 找到v2在邻接表中的位置
        ArcNode *p1 = (ArcNode *)malloc(sizeof(ArcNode));
        p1->adjvex = n; // 添加边
        p1->next = g->adjlist[m].firstarc;
        g->adjlist[m].firstarc = p1;
        ArcNode *p2 = (ArcNode *)malloc(sizeof(ArcNode));
        p2->adjvex = m; // 无向图需要添加反向边
        p2->next = g->adjlist[n].firstarc;
        g->adjlist[n].firstarc = p2;
    }
}

// 打印邻接矩阵
void printMGraph(MGraph g) {
    printf("邻接矩阵：\n");
    for (int i = 0; i < g.vertex_num; i++) {
        for (int j = 0; j < g.vertex_num; j++) {
            printf("%d ", g.arc[i][j]);
        }
        printf("\n");
    }
}

// 打印邻接表
void printALGraph(ALGraph g) {
    printf("邻接表：\n");
    for (int i = 0; i < g.vertex_num; i++) {
        printf("%d -> ", g.adjlist[i].vertex);
        ArcNode *p = g.adjlist[i].firstarc;
        while (p != NULL) {
            printf("%d ", g.adjlist[p->adjvex].vertex);
            p = p->next;
        }
        printf("\n");
    }
}

int main() {
    MGraph g1;
    createMGraph(&g1);
    printMGraph(g1);

    ALGraph g2;
    createALGraph(&g2);
    printALGraph(g2);

    return 0;
}

以上代码中，我们定义了两个结构体，分别存储邻接矩阵和邻接表。其中，邻接矩阵结构体包含了一个顶点数组和一个邻接矩阵数组，邻接表结构体包含了一个邻接表数组。

createMGraph函数用于创建邻接矩阵，createALGraph函数用于创建邻接表。在输入边的信息时，我们需要找到起点和终点在顶点数组或邻接表数组中的下标，然后在邻接矩阵或邻接表中添加边。注意，无向图需要添加反向边。

printMGraph函数用于打印邻接矩阵，printALGraph函数用于打印邻接表。我们遍历邻接矩阵或邻接表数组，依次输出每个顶点和它的邻接点即可。

运行程序，输入如下：

请输入顶点数和边数：
5 7
请输入顶点信息：
1 2 3 4 5
请输入边的信息（格式：起点 终点 权值）：
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6
3 5 7
4 5 8
请输入顶点数和边数：
5 7
请输入顶点信息：
1 2 3 4 5
请输入边的信息（格式：起点 终点 权值）：
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6
3 5 7
4 5 8

输出如下：

邻接矩阵：
0 2 3 0 0 
2 0 4 5 0 
3 4 0 6 7 
0 5 6 0 8 
0 0 7 8 0 
邻接表：
1 -> 2 3 
2 -> 1 3 4 
3 -> 1 2 4 5 
4 -> 2 3 5 
5 -> 3 4 

C语言生成图的邻接表，并对其进行深度优先搜索和广度优先搜索

生成图的邻接表可以使用链式前向星或者邻接表数组实现。下面给出链式前向星的实现方法：

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

#define MAXN 100000

struct Edge {
    int to;         // 该边连接的终点节点
    int weight;     // 权值
    int next;       // 下一条同起点的边在数组中的下标
} edges[MAXN];

int head[MAXN];     // head[i] 表示以 i 为起点的第一条边在 edges 数组中的下标
int cnt;            // 边的数量

void addEdge(int from, int to, int weight) {
    edges[cnt].to = to;
    edges[cnt].weight = weight;
    edges[cnt].next = head[from];
    head[from] = cnt++;
}

接下来，我们可以使用深度优先搜索和广度优先搜索对图进行遍历。下面是深度优先搜索的实现：

int visited[MAXN];  // 标记数组，用于记录节点是否被访问过

void dfs(int u) {
    printf("%d ", u);       // 遍历到节点 u，进行相应的操作
    visited[u] = 1;         // 标记节点 u 为已访问
    for (int i = head[u]; i != -1; i = edges[i].next) {
        int v = edges[i].to;
        if (!visited[v]) {  // 如果节点 v 没有被访问过
            dfs(v);         // 递归遍历节点 v
        }
    }
}

接下来是广度优先搜索的实现：

int visited[MAXN];  // 标记数组，用于记录节点是否被访问过
int queue[MAXN];    // 队列，用于实现广度优先搜索
int front, rear;    // 队列的头指针和尾指针

void bfs(int start) {
    front = rear = 0;           // 初始化队列
    printf("%d ", start);       // 遍历到节点 start，进行相应的操作
    visited[start] = 1;         // 标记节点 start 为已访问
    queue[rear++] = start;      // 将节点 start 加入队列尾部
    while (front != rear) {     // 队列不为空时循环
        int u = queue[front++]; // 取出队列头部元素
        for (int i = head[u]; i != -1; i = edges[i].next) {
            int v = edges[i].to;
            if (!visited[v]) {  // 如果节点 v 没有被访问过
                printf("%d ", v);// 遍历到节点 v，进行相应的操作
                visited[v] = 1; // 标记节点 v 为已访问
                queue[rear++] = v;// 将节点 v 加入队列尾部
            }
        }
    }
}

最后，我们可以在主函数中调用这些函数来遍历图：

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        addEdge(u, v, w);   // 添加边
        addEdge(v, u, w);   // 如果是无向图，还需要添加反向边
    }

    // 深度优先搜索
    printf("DFS: ");
    dfs(1);
    printf("\n");

    // 广度优先搜索
    memset(visited, 0, sizeof(visited)); // 重置标记数组
    printf("BFS: ");
    bfs(1);
    printf("\n");

    return 0;
}