定义图的邻接矩阵和邻接表。 （2）编写图的深度优先和广度优先搜索的遍历算法。 （3）编写求最小生成树的算法。 （4）设计菜单，以选择菜单方式进行操作，并实现上述算法。

好的，我会根据您的要求，为您回答这个问题。

1. 定义图的邻接矩阵和邻接表

邻接矩阵是一个二维数组，用来表示图中节点之间的关系。如果节点 i 和节点 j 之间有一条边，那么邻接矩阵中的第 i 行第 j 列的值为 1，否则为 0。

邻接表是一个数组，每个数组元素是一个链表，用来表示每个节点的邻居节点。如果节点 i 和节点 j 之间有一条边，那么邻接表中节点 i 的链表中会有一个指向节点 j 的指针，反之同理。

2. 编写图的深度优先和广度优先搜索的遍历算法

深度优先搜索算法（DFS）：

#define MAX_VERTEX_NUM 100 // 最大节点数
typedef int VertexType;     // 节点类型
typedef int EdgeType;       // 边权值类型
typedef struct {
    VertexType vexs[MAX_VERTEX_NUM];    // 存储点的数组
    EdgeType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边的邻接矩阵
    int vexnum;     // 顶点数
    int arcnum;     // 边数
} MGraph;

int visited[MAX_VERTEX_NUM]; // 记录节点是否已访问

void DFS(MGraph G, int v) {
    visited[v] = 1;
    printf("%d ", G.vexs[v]);
    for (int w = 0; w < G.vexnum; w++) {
        if (G.arcs[v][w] && !visited[w]) {
            DFS(G, w);
        }
    }
}

void DFSTraverse(MGraph G) {
    for (int i = 0; i < G.vexnum; i++) {
        visited[i] = 0;
    }
    for (int i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            DFS(G, i);
        }
    }
}

广度优先搜索算法（BFS）：

#define MAX_VERTEX_NUM 100 // 最大节点数
typedef int VertexType;     // 节点类型
typedef int EdgeType;       // 边权值类型
typedef struct {
    VertexType vexs[MAX_VERTEX_NUM];    // 存储点的数组
    EdgeType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边的邻接矩阵
    int vexnum;     // 顶点数
    int arcnum;     // 边数
} MGraph;

int visited[MAX_VERTEX_NUM]; // 记录节点是否已访问

void BFS(MGraph G, int v) {
    visited[v] = 1;
    printf("%d ", G.vexs[v]);
    int queue[MAX_VERTEX_NUM];
    int front = 0, rear = 0;
    queue[rear++] = v;
    while (front < rear) {
        int w = queue[front++];
        for (int i = 0; i < G.vexnum; i++) {
            if (G.arcs[w][i] && !visited[i]) {
                visited[i] = 1;
                printf("%d ", G.vexs[i]);
                queue[rear++] = i;
            }
        }
    }
}

void BFSTraverse(MGraph G) {
    for (int i = 0; i < G.vexnum; i++) {
        visited[i] = 0;
    }
    for (int i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            BFS(G, i);
        }
    }
}

3. 编写求最小生成树的算法

Kruskal 算法：

#define MAX_VERTEX_NUM 100 // 最大节点数
typedef int VertexType;     // 节点类型
typedef int EdgeType;       // 边权值类型
typedef struct {
    VertexType vexs[MAX_VERTEX_NUM];    // 存储点的数组
    EdgeType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边的邻接矩阵
    int vexnum;     // 顶点数
    int arcnum;     // 边数
} MGraph;

typedef struct {
    int u;  // 边的起点
    int v;  // 边的终点
    EdgeType w; // 边的权值
} Edge;

int Find(int parent[], int f) {
    while (parent[f] > 0) {
        f = parent[f];
    }
    return f;
}

void Kruskal(MGraph G) {
    int parent[MAX_VERTEX_NUM] = {0};
    Edge edges[MAX_VERTEX_NUM];
    int k = 0;
    for (int i = 0; i < G.vexnum; i++) {
        for (int j = i + 1; j < G.vexnum; j++) {
            if (G.arcs[i][j] != 0) {
                edges[k].u = i;
                edges[k].v = j;
                edges[k].w = G.arcs[i][j];
                k++;
            }
        }
    }
    for (int i = 0; i < k; i++) {
        int uf = Find(parent, edges[i].u);
        int vf = Find(parent, edges[i].v);
        if (uf != vf) {
            parent[uf] = vf;
            printf("(%d, %d) ", edges[i].u, edges[i].v);
        }
    }
}

4. 设计菜单，以选择菜单方式进行操作，并实现上述算法。

以下是用 C 语言编写的实现菜单方式进行操作的完整代码：