创建图的邻接矩阵,设计算法自动生成邻接表,或: (2) 创建图的邻接表,设计算法自动生成邻接矩阵

(1) 创建图的邻接矩阵，设计算法自动生成邻接表：

假设我们有一个无向图，其中顶点数为V，边数为E。我们可以使用一个VxV的矩阵A来表示它的邻接矩阵，其中A[i][j]表示顶点i和j之间是否有边相连。如果是，A[i][j]的值为1，否则为0。

为了生成邻接表，我们可以遍历矩阵A中的每一个元素，如果A[i][j]的值为1，则表示顶点i和j之间有一条边。我们可以将这个边加入到以i为头结点的链表中。具体算法如下：

1. 初始化一个空的邻接表adj[V]，其中V是顶点数。
2. 遍历邻接矩阵A中的每一个元素A[i][j]：
    a. 如果A[i][j]的值为1，则表示顶点i和j之间有一条边。
    b. 将j加入到以i为头结点的链表中。
3. 返回邻接表adj。

(2) 创建图的邻接表，设计算法自动生成邻接矩阵：

假设我们已经有了一个图的邻接表adj，其中每一个元素adj[i]都是一个链表，表示以i为头结点的所有边。为了生成邻接矩阵，我们可以遍历邻接表中的每一个元素，对于每一个链表中的节点j，我们将邻接矩阵中的A[i][j]和A[j][i]都设置为1。具体算法如下：

1. 初始化一个VxV的零矩阵A，其中V是顶点数。
2. 遍历邻接表adj中的每一个元素adj[i]：
    a. 对于每一个链表中的节点j，将A[i][j]和A[j][i]都设置为1。
3. 返回邻接矩阵A。

相关问题

创建图的邻接矩阵，设计算法自动生成邻接表，生成C语言代码

创建图的邻接矩阵:

假设有一个无向图，有n个节点和m条边，我们可以用一个n*n的矩阵来表示这个图，称之为邻接矩阵。其中第i行第j列的元素表示节点i到节点j是否有边相连，如果相连，那么为1，否则为0。

例如，下面是一个无向图的邻接矩阵：

    1 2 3 4 5
1   0 1 1 0 0
2   1 0 0 1 1
3   1 0 0 1 0
4   0 1 1 0 1
5   0 1 0 1 0

设计算法自动生成邻接表

邻接表是图的另一种表示方式。对于每个节点，我们用一个链表来表示它所连接的其他节点。因此，对于一个有n个节点和m条边的图，邻接表的长度是m+2n。

生成邻接表的算法如下：

1. 首先创建一个长度为n的链表数组adj_list，代表每个节点的邻接表。
2. 遍历邻接矩阵，对于每个节点i，遍历它所连接的其他节点j（j>i）。
3. 对于每个连接节点j，创建一个新的邻接表节点，并将其插入到节点i的邻接表中。
4. 将节点j也加入到节点i的邻接表中（因为是无向图）。
5. 重复2-4，直到遍历完所有节点。

生成C语言代码

下面是生成C语言代码的算法实现：

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

#define MAX_NODES 1000

// 邻接表节点
typedef struct _adj_list_node {
    int dest;                   // 连接的节点
    struct _adj_list_node* next; // 下一个邻接表节点
} adj_list_node;

// 邻接表
typedef struct _adj_list {
    adj_list_node* head; // 邻接表头
} adj_list;

// 图
typedef struct _graph {
    int num_nodes;          // 节点数
    adj_list* adj_lists;    // 邻接表数组
} graph;

// 创建邻接表节点
adj_list_node* create_adj_list_node(int dest) {
    adj_list_node* node = (adj_list_node*)malloc(sizeof(adj_list_node));
    node->dest = dest;
    node->next = NULL;
    return node;
}

// 添加边
void add_edge(graph* g, int src, int dest) {
    adj_list_node* node = create_adj_list_node(dest);
    node->next = g->adj_lists[src].head;
    g->adj_lists[src].head = node;

    node = create_adj_list_node(src);
    node->next = g->adj_lists[dest].head;
    g->adj_lists[dest].head = node;
}

// 创建图
graph* create_graph(int num_nodes, int** edges, int num_edges) {
    graph* g = (graph*)malloc(sizeof(graph));
    g->num_nodes = num_nodes;
    g->adj_lists = (adj_list*)malloc(num_nodes * sizeof(adj_list));

    for (int i = 0; i < num_nodes; i++) {
        g->adj_lists[i].head = NULL;
    }

    for (int i = 0; i < num_edges; i++) {
        int src = edges[i][0];
        int dest = edges[i][1];
        add_edge(g, src, dest);
    }

    return g;
}

// 打印邻接表
void print_graph(graph* g) {
    for (int i = 0; i < g->num_nodes; i++) {
        printf("%d: ", i);
        adj_list_node* node = g->adj_lists[i].head;
        while (node != NULL) {
            printf("%d ", node->dest);
            node = node->next;
        }
        printf("\n");
    }
}

int main() {
    int num_nodes = 5;
    int edges[][2] = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 3}, {3, 4}};
    int num_edges = sizeof(edges) / sizeof(edges[0]);

    graph* g = create_graph(num_nodes, edges, num_edges);
    print_graph(g);

    return 0;
}

C语言创建图的邻接矩阵，设计算法自动生成邻接表。要求能够打印图的邻接矩阵和邻接表，进行验证

以下是C语言实现自动生成邻接表的算法：

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

#define MAX_VERTEX_NUM 20

// 定义邻接矩阵结构体
typedef struct {
    int vertex[MAX_VERTEX_NUM]; // 存储顶点信息
    int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边信息
    int vertex_num; // 顶点数
    int edge_num; // 边数
} MGraph;

// 定义邻接表结构体
typedef struct {
    int vertex; // 存储顶点信息
    struct ArcNode *first_arc; // 指向第一个邻接点的指针
} VNode;

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

typedef struct {
    VNode adj_list[MAX_VERTEX_NUM]; // 存储邻接表信息
    int vertex_num; // 顶点数
    int edge_num; // 边数
} ALGraph;

void generate_adj_list(MGraph *mg, ALGraph *ag);
void print_matrix(MGraph *mg);
void print_adj_list(ALGraph *ag);

int main() {
    MGraph mg = {
        {0, 1, 2, 3, 4}, // 顶点信息
        {
            {0, 1, 1, 0, 0},
            {1, 0, 0, 1, 1},
            {1, 0, 0, 1, 0},
            {0, 1, 1, 0, 1},
            {0, 1, 0, 1, 0}
        }, // 边信息
        5, // 顶点数
        7 // 边数
    };

    ALGraph ag;
    generate_adj_list(&mg, &ag);

    printf("邻接矩阵：\n");
    print_matrix(&mg);

    printf("\n邻接表：\n");
    print_adj_list(&ag);

    return 0;
}

// 根据邻接矩阵生成邻接表
void generate_adj_list(MGraph *mg, ALGraph *ag) {
    ag->vertex_num = mg->vertex_num;
    ag->edge_num = mg->edge_num;

    for (int i = 0; i < ag->vertex_num; i++) {
        ag->adj_list[i].vertex = mg->vertex[i];
        ag->adj_list[i].first_arc = NULL;

        ArcNode *last_arc = NULL; // 指向上一个邻接点的指针

        for (int j = 0; j < ag->vertex_num; j++) {
            if (mg->edge[i][j] != 0) {
                ArcNode *arc = (ArcNode *) malloc(sizeof(ArcNode));
                arc->adjvex = j;
                arc->next = NULL;

                if (last_arc == NULL) { // 如果是第一个邻接点
                    ag->adj_list[i].first_arc = arc;
                } else {
                    last_arc->next = arc;
                }

                last_arc = arc;
            }
        }
    }
}

// 打印邻接矩阵
void print_matrix(MGraph *mg) {
    for (int i = 0; i < mg->vertex_num; i++) {
        for (int j = 0; j < mg->vertex_num; j++) {
            printf("%d ", mg->edge[i][j]);
        }
        printf("\n");
    }
}

// 打印邻接表
void print_adj_list(ALGraph *ag) {
    for (int i = 0; i < ag->vertex_num; i++) {
        printf("%d -> ", ag->adj_list[i].vertex);

        ArcNode *arc = ag->adj_list[i].first_arc;
        while (arc != NULL) {
            printf("%d -> ", ag->adj_list[arc->adjvex].vertex);
            arc = arc->next;
        }

        printf("NULL\n");
    }
}

运行结果：

邻接矩阵：
0 1 1 0 0
1 0 0 1 1
1 0 0 1 0
0 1 1 0 1
0 1 0 1 0

邻接表：
0 -> 1 -> 2 -> NULL
1 -> 0 -> 3 -> 4 -> NULL
2 -> 0 -> 3 -> NULL
3 -> 1 -> 2 -> 4 -> NULL
4 -> 1 -> 3 -> NULL