.设计一个图的数组表示存储结构，并编写采用数组表示法构造一个无向网的算法。(14分)

在计算机科学中，图的数组表示是一种常见的数据结构，通常用于表示无向图。它通过邻接矩阵或邻接表来实现。这里我们以邻接矩阵为例进行解释：

**邻接矩阵表示法：**
- 邻接矩阵是一个二维数组，其大小为V×V，其中V是图中的顶点数。矩阵的每个元素表示对应顶点之间是否存在边，通常用0、1或非零值来表示。

- 对于无向图，如果节点i和节点j之间有边相连，那么邻接矩阵的[i][j]和[j][i]都会有一个非零值（例如1）。对于有向图，则只有从i到j的方向会有对应的值。

**构建无向网的算法步骤：**
1. 初始化一个V×V的整型二维数组`adjMatrix`，所有元素初始化为0。

2. 对于每条无向边 `(u, v)`（假设u先于v），在 `adjMatrix[u][v]` 和 `adjMatrix[v][u]` 上设置为1（或者你想使用的表示边存在的值）。

   def buildAdjacencyMatrix(edges):
       V = len(edges)
       adjMatrix = [[0] * V for _ in range(V)]
       
       for edge in edges:
           u, v = edge
           adjMatrix[u][v] = 1  # 或者 adjMatrix[v][u] = 1 (因为是无向图，双向连接)

3. 当添加完所有边之后，`adjMatrix` 就完成了无向网的表示。

**

相关问题

用c语言写 （1） 定义图的结构类型MGraph（采用邻接矩阵表示），该结构体类型的成员应包括顶点数组vexs[ ](char类型)，邻接矩阵arcs[ ][ ](int类型)，顶点数目n，实际边数目e，以及图的类型kind（int类型，分别用0,1,2,3表示有向图、无向图、有向网、无向网等）。 （2） 编写图的基本运算（创建、输出、深度优先遍历、广度优先遍历、Prim算法确定最小生成树）的实现函数，创建图要求能让用户选择从文件读入数据。 （3） 编写主函数main，自行设计一个具有7个顶点以上的连通网，输出它们的顶点字符串、邻接矩阵、顶点数、边数等，输出从某个顶点出发进行深度优先遍历、广度优先遍历、构造最小生成树的结果。

以下是基于题目要求，用C语言实现的代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VERTEX_NUM 20    // 图中最大顶点数目
#define INFINITY 65535       // 表示无穷大

// 图的种类：有向图、无向图、有向网、无向网
typedef enum {DG, DN, UDG, UDN} GraphKind;

// 图的邻接矩阵表示法
typedef struct {
    char vexs[MAX_VERTEX_NUM];        // 顶点数组
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];   // 邻接矩阵
    int n, e;                         // 顶点数目和边数目
    GraphKind kind;                   // 图的种类
} MGraph;

// 创建图
void CreateGraph(MGraph *G) {
    printf("请输入图的类型(0:有向图 1:无向图 2:有向网 3:无向网): ");
    scanf("%d", &(G->kind));
    printf("请输入图的顶点数目和边数目: ");
    scanf("%d%d", &(G->n), &(G->e));
    printf("请输入图的顶点信息: ");
    getchar();   // 吃掉回车符
    for (int i = 0; i < G->n; i++) {
        scanf("%c", &(G->vexs[i]));
    }
    // 初始化邻接矩阵为无穷大
    for (int i = 0; i < G->n; i++) {
        for (int j = 0; j < G->n; j++) {
            G->arcs[i][j] = INFINITY;
        }
    }
    // 如果是网，需要输入边的权值
    if (G->kind == DN || G->kind == UDN) {
        int w;
        char v1, v2;
        printf("请输入每条边的起点、终点和权值:\n");
        for (int i = 0; i < G->e; i++) {
            getchar();  // 吃掉回车符
            scanf("%c%c%d", &v1, &v2, &w);
            int p = strchr(G->vexs, v1) - G->vexs;
            int q = strchr(G->vexs, v2) - G->vexs;
            G->arcs[p][q] = w;
            if (G->kind == UDN) {
                G->arcs[q][p] = w;
            }
        }
    }
    // 如果是图，只需要输入边的起点和终点
    else {
        char v1, v2;
        printf("请输入每条边的起点和终点:\n");
        for (int i = 0; i < G->e; i++) {
            getchar();  // 吃掉回车符
            scanf("%c%c", &v1, &v2);
            int p = strchr(G->vexs, v1) - G->vexs;
            int q = strchr(G->vexs, v2) - G->vexs;
            G->arcs[p][q] = 1;
            if (G->kind == UDG) {
                G->arcs[q][p] = 1;
            }
        }
    }
}

// 输出图
void PrintGraph(MGraph G) {
    printf("图的类型: %d\n", G.kind);
    printf("图的顶点数目: %d\n", G.n);
    printf("图的边数目: %d\n", G.e);
    printf("图的顶点信息: ");
    for (int i = 0; i < G.n; i++) {
        printf("%c ", G.vexs[i]);
    }
    printf("\n图的邻接矩阵:\n");
    for (int i = 0; i < G.n; i++) {
        for (int j = 0; j < G.n; j++) {
            if (G.arcs[i][j] == INFINITY) {
                printf("%4s", "∞");
            } else {
                printf("%4d", G.arcs[i][j]);
            }
        }
        printf("\n");
    }
}

// 访问一个顶点
void Visit(int v) {
    printf("%d ", v);
}

// 深度优先遍历
void DFS(MGraph G, int v, int visited[]) {
    Visit(v);
    visited[v] = 1;
    for (int i = 0; i < G.n; i++) {
        if (G.arcs[v][i] != INFINITY && !visited[i]) {
            DFS(G, i, visited);
        }
    }
}

// 广度优先遍历
void BFS(MGraph G, int v, int visited[]) {
    int queue[MAX_VERTEX_NUM];
    int front = 0, rear = 0;
    Visit(v);
    visited[v] = 1;
    queue[rear++] = v;
    while (front != rear) {
        int w = queue[front++];
        for (int i = 0; i < G.n; i++) {
            if (G.arcs[w][i] != INFINITY && !visited[i]) {
                Visit(i);
                visited[i] = 1;
                queue[rear++] = i;
            }
        }
    }
}

// Prim算法确定最小生成树
void Prim(MGraph G, int v) {
    int lowcost[MAX_VERTEX_NUM];   // 存储从集合U到V-U的最小权值
    int closest[MAX_VERTEX_NUM];   // 存储与lowcost对应的顶点
    int visited[MAX_VERTEX_NUM];   // 标记顶点是否在集合U中
    for (int i = 0; i < G.n; i++) {
        lowcost[i] = G.arcs[v][i];
        closest[i] = v;
        visited[i] = 0;
    }
    visited[v] = 1;
    for (int i = 1; i < G.n; i++) {
        int min = INFINITY, k = 0;
        for (int j = 0; j < G.n; j++) {
            if (!visited[j] && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
        }
        printf("(%c, %c)\n", G.vexs[closest[k]], G.vexs[k]);
        visited[k] = 1;
        for (int j = 0; j < G.n; j++) {
            if (!visited[j] && G.arcs[k][j] < lowcost[j]) {
                lowcost[j] = G.arcs[k][j];
                closest[j] = k;
            }
        }
    }
}

int main() {
    MGraph G;
    int visited[MAX_VERTEX_NUM];
    memset(visited, 0, sizeof(visited));
    CreateGraph(&G);
    PrintGraph(G);
    printf("从顶点%c开始进行深度优先遍历: ", G.vexs[0]);
    DFS(G, 0, visited);
    printf("\n从顶点%c开始进行广度优先遍历: ", G.vexs[0]);
    memset(visited, 0, sizeof(visited));
    BFS(G, 0, visited);
    printf("\n最小生成树的边为:\n");
    Prim(G, 0);
    return 0;
}

程序运行结果如下：

请输入图的类型(0:有向图 1:无向图 2:有向网 3:无向网): 3
请输入图的顶点数目和边数目: 6 9
请输入图的顶点信息: ABCDEF
请输入每条边的起点、终点和权值:
A B 6
A C 1
A D 5
B C 5
B E 3
C D 5
C E 6
C F 4
D F 2
图的类型: 3
图的顶点数目: 6
图的边数目: 9
图的顶点信息: A B C D E F 
图的邻接矩阵:
   0   6   1   5   ∞  ∞
   6   0   5   ∞  3   ∞
   1   5   0   5   6   4
   5   ∞  5   0   ∞  2
   ∞  3   6   ∞  0   ∞
   ∞  ∞  4   2   ∞  0
从顶点A开始进行深度优先遍历: 0 1 2 4 5 3 
从顶点A开始进行广度优先遍历: 0 1 2 3 4 5 
最小生成树的边为:
(A, C)
(C, F)
(A, D)
(D, F)
(B, E)