c语言邻接矩阵表示带权无向图

邻接矩阵是一种常见的表示图的方法，对于带权无向图，我们可以使用一个二维数组来表示邻接矩阵。具体来说，设图G的顶点数为n，邻接矩阵为matrix，则matrix[i][j]表示顶点i和顶点j之间的边的权值，如果i和j之间没有边，则matrix[i][j]的值为0。由于是带权图，所以matrix[i][j]的值可能为任意非负数，当然也可能为负数。如果图是有向图，则邻接矩阵不一定是对称的。在使用邻接矩阵表示图时，需要注意空间复杂度，如果图的顶点数很多，邻接矩阵可能会非常大，甚至超出计算机的内存限制。

相关问题

如何用c语言邻接矩阵表示法建立无向图

邻接矩阵是一种用于表示图的数据结构，其中矩阵中的每个元素表示两个顶点之间是否存在边。对于无向图而言，矩阵是对称的。

以下是使用C语言邻接矩阵表示法建立无向图的示例代码：

#include <stdio.h>

#define MAX_VERTEX_NUM 20

// 邻接矩阵无向图结构体
typedef struct {
    char vertices[MAX_VERTEX_NUM];  // 顶点表
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 邻接矩阵
    int vertex_num;  // 顶点数
    int edge_num;  // 边数
} MGraph;

// 初始化无向图
void InitMGraph(MGraph *G) {
    int i, j;
    printf("请输入顶点数和边数：\n");
    scanf("%d %d", &G->vertex_num, &G->edge_num);
    fflush(stdin);
    printf("请输入顶点信息：\n");
    for (i = 0; i < G->vertex_num; i++) {
        scanf("%c", &G->vertices[i]);
        fflush(stdin);
    }
    // 初始化邻接矩阵
    for (i = 0; i < G->vertex_num; i++) {
        for (j = 0; j < G->vertex_num; j++) {
            G->arcs[i][j] = 0;
        }
    }
    // 构建邻接矩阵
    printf("请输入每条边的起点和终点：\n");
    for (i = 0; i < G->edge_num; i++) {
        int v1, v2;
        scanf("%d %d", &v1, &v2);
        G->arcs[v1][v2] = 1;
        G->arcs[v2][v1] = 1;
    }
}

// 打印无向图
void PrintMGraph(MGraph G) {
    int i, j;
    printf("邻接矩阵：\n");
    for (i = 0; i < G.vertex_num; i++) {
        for (j = 0; j < G.vertex_num; j++) {
            printf("%d ", G.arcs[i][j]);
        }
        printf("\n");
    }
}

int main() {
    MGraph G;
    InitMGraph(&G);
    PrintMGraph(G);
    return 0;
}

在上面的代码中，我们定义了一个 `MGraph` 结构体来表示邻接矩阵无向图。`InitMGraph` 函数用于初始化图，包括输入顶点数、边数、顶点信息以及每条边的起点和终点，并构建邻接矩阵。`PrintMGraph` 函数用于打印邻接矩阵。在 `main` 函数中，我们调用 `InitMGraph` 和 `PrintMGraph` 函数来构建并打印无向图。

注意，上面的代码中，我们假设顶点使用字符表示，因此在输入顶点信息时使用了 `%c` 格式化符号。如果顶点使用其他类型表示，需要相应更改输入和打印的代码。

C语言邻接矩阵建立无向图并转换成邻接表输出

好的，下面是C语言代码：

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

#define MAX_VERTEX_NUM 100   // 最大顶点数

// 邻接矩阵结构体
typedef struct {
    int vertex[MAX_VERTEX_NUM];     // 顶点数组
    int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM];   // 邻接矩阵
    int vertex_num;     // 顶点数
    int edge_num;   // 边数
} MGraph;

// 邻接表结构体
typedef struct ArcNode {
    int adj_vex;    // 邻接点下标
    struct ArcNode *nextarc;    // 指向下一个邻接点的指针
} ArcNode;

typedef struct VNode {
    int data;       // 顶点信息
    ArcNode *firstarc;   // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices;   // 邻接表
    int vertex_num;     // 顶点数
    int edge_num;   // 边数
} ALGraph;

// 邻接矩阵转邻接表
void MGraphToALGraph(MGraph mg, ALGraph *ag) {
    ag->vertex_num = mg.vertex_num;     // 顶点数
    ag->edge_num = mg.edge_num;     // 边数

    for (int i = 0; i < mg.vertex_num; i++) {
        ag->vertices[i].data = mg.vertex[i];     // 存储顶点信息
        ag->vertices[i].firstarc = NULL;    // 初始化邻接表的第一个邻接点指针
    }

    for (int i = 0; i < mg.vertex_num; i++) {
        for (int j = 0; j < mg.vertex_num; j++) {
            if (mg.edge[i][j] != 0) {
                // 创建一个新的邻接点
                ArcNode *newArcNode = (ArcNode *) malloc(sizeof(ArcNode));
                newArcNode->adj_vex = j;
                newArcNode->nextarc = NULL;

                // 将新的邻接点插入到对应的邻接表中
                if (ag->vertices[i].firstarc == NULL) {
                    ag->vertices[i].firstarc = newArcNode;
                } else {
                    ArcNode *p = ag->vertices[i].firstarc;
                    while (p->nextarc != NULL) {
                        p = p->nextarc;
                    }
                    p->nextarc = newArcNode;
                }
            }
        }
    }
}

int main(void) {
    // 构建邻接矩阵
    MGraph mg;
    mg.vertex_num = 5;
    mg.edge_num = 7;
    mg.vertex[0] = 0;
    mg.vertex[1] = 1;
    mg.vertex[2] = 2;
    mg.vertex[3] = 3;
    mg.vertex[4] = 4;
    mg.edge[0][1] = 1;
    mg.edge[0][2] = 1;
    mg.edge[1][3] = 1;
    mg.edge[1][4] = 1;
    mg.edge[2][3] = 1;
    mg.edge[2][4] = 1;
    mg.edge[3][4] = 1;

    // 转换成邻接表
    ALGraph ag;
    MGraphToALGraph(mg, &ag);

    // 输出邻接表
    printf("邻接表：\n");
    for (int i = 0; i < ag.vertex_num; i++) {
        printf("%d -> ", ag.vertices[i].data);
        ArcNode *p = ag.vertices[i].firstarc;
        while (p != NULL) {
            printf("%d ", ag.vertices[p->adj_vex].data);
            p = p->nextarc;
        }
        printf("\n");
    }

    return 0;
}

以上代码将邻接矩阵转换成邻接表并输出，可以根据需要进行修改。