C语言数据结构以邻接矩阵和邻接表的形式创建一个无向图的算法分析

创建一个无向图可以使用邻接矩阵或邻接表两种方式。

1. 邻接矩阵的算法分析

邻接矩阵是一个二维数组，其中数组的每个元素表示两个顶点之间是否存在边。对于一个无向图，邻接矩阵是一个对称矩阵，即第 i 行第 j 列元素等于第 j 行第 i 列元素。

邻接矩阵的创建步骤如下：

1. 定义一个二维数组 matrix，大小为 n x n，其中 n 表示顶点的个数。
2. 初始化 matrix 中的所有元素为 0。
3. 遍历所有边，将 matrix 中对应的元素置为 1。
4. 返回 matrix。

邻接矩阵的时间复杂度为 O(n^2)，空间复杂度为 O(n^2)。

2. 邻接表的算法分析

邻接表是由一个链表数组构成的，其中每个链表表示一个顶点和它所连接的所有边。对于一个无向图，每个顶点的链表中存储的是与该顶点相邻的其他顶点。

邻接表的创建步骤如下：

1. 定义一个链表数组 adjList，大小为 n，其中 n 表示顶点的个数。
2. 遍历所有边，将每条边的两个顶点加入对应的链表中。
3. 返回 adjList。

邻接表的时间复杂度为 O(m+n)，其中 m 表示边的数量，n 表示顶点的数量。空间复杂度为 O(m+n)。

总体上，邻接表比邻接矩阵更加适用于稀疏图，而邻接矩阵则更适用于稠密图。在实际应用中，应根据实际情况选择合适的数据结构。

相关问题

c语言，以邻接矩阵形式创建一个无向图的算法分析

创建一个无向图的邻接矩阵的算法如下：

1. 首先，需要定义一个二维数组来表示邻接矩阵，假设该数组名为adj_matrix。

2. 然后，需要输入图的顶点数n和边数m。

3. 接下来，需要初始化邻接矩阵，将其中所有元素都置为0。

4. 读入每一条边的信息，包括边的起点和终点。

5. 对于每一条边，将其对应的邻接矩阵中的元素设为1，表示该边存在。

6. 最后，输出邻接矩阵adj_matrix。

算法分析：

时间复杂度为O(n^2)，因为需要初始化整个邻接矩阵，并且需要遍历所有的边。空间复杂度为O(n^2)，因为需要存储整个邻接矩阵。这种方法适用于边数比较少的情况，对于边数很大的图，邻接矩阵会变得非常稀疏，造成空间浪费。此时，可以考虑使用邻接表来表示图。

用c语言以邻接矩阵形式创建一个无向图并 以邻接表的形式创建一个无向图。

创建无向图邻接矩阵的C语言代码：

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

typedef struct {
    int matrix[MAXV][MAXV]; // 邻接矩阵
    int num_v;  // 顶点数
} Graph;

void init(Graph *G, int num_v) {
    G->num_v = num_v;
    for (int i = 0; i < num_v; i++) {
        for (int j = 0; j < num_v; j++) {
            G->matrix[i][j] = 0;    // 初始化为0
        }
    }
}

void addEdge(Graph *G, int u, int v) {
    G->matrix[u][v] = 1;
    G->matrix[v][u] = 1;    // 无向图，所以需要反向再赋值一次
}

void printGraph(Graph *G) {
    for (int i = 0; i < G->num_v; i++) {
        printf("%d: ", i);
        for (int j = 0; j < G->num_v; j++) {
            if (G->matrix[i][j]) {
                printf("%d ", j);
            }
        }
        printf("\n");
    }
}

int main() {
    Graph G;
    int num_v = 5;
    init(&G, num_v);
    addEdge(&G, 0, 1);
    addEdge(&G, 0, 4);
    addEdge(&G, 1, 2);
    addEdge(&G, 1, 3);
    addEdge(&G, 1, 4);
    addEdge(&G, 2, 3);
    addEdge(&G, 3, 4);
    printGraph(&G);
    return 0;
}

创建无向图邻接表的C语言代码：

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

typedef struct node {
    int v;  // 该边所连向的顶点
    struct node *next;  // 指向下一条边的指针
} EdgeNode;

typedef struct vnode {
    int data;   // 顶点信息
    EdgeNode *first_edge;   // 指向第一条依附于该顶点的边的指针
} VertexNode;

typedef struct {
    VertexNode adj_list[100];   // 邻接表，最多100个顶点
    int num_v, num_e;   // 顶点数和边数
} Graph;

void init(Graph *G, int num_v) {
    G->num_v = num_v;
    G->num_e = 0;
    for (int i = 0; i < num_v; i++) {
        G->adj_list[i].data = i;
        G->adj_list[i].first_edge = NULL;
    }
}

void addEdge(Graph *G, int u, int v) {
    EdgeNode *e = (EdgeNode *) malloc(sizeof(EdgeNode));
    e->v = v;
    e->next = G->adj_list[u].first_edge;
    G->adj_list[u].first_edge = e;

    e = (EdgeNode *) malloc(sizeof(EdgeNode));
    e->v = u;
    e->next = G->adj_list[v].first_edge;
    G->adj_list[v].first_edge = e;

    G->num_e++;
}

void printGraph(Graph *G) {
    for (int i = 0; i < G->num_v; i++) {
        printf("%d: ", G->adj_list[i].data);
        EdgeNode *e = G->adj_list[i].first_edge;
        while (e != NULL) {
            printf("%d ", e->v);
            e = e->next;
        }
        printf("\n");
    }
}

int main() {
    Graph G;
    int num_v = 5;
    init(&G, num_v);
    addEdge(&G, 0, 1);
    addEdge(&G, 0, 4);
    addEdge(&G, 1, 2);
    addEdge(&G, 1, 3);
    addEdge(&G, 1, 4);
    addEdge(&G, 2, 3);
    addEdge(&G, 3, 4);
    printGraph(&G);
    return 0;
}