用c语言写 以邻接表位存储结构实现无向图的深度优先遍历操作。最小生成树问题

好的，以下是用C语言实现以邻接表为存储结构的无向图的最小生成树问题的代码：

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

#define MAX_VERTEX_NUM 20
#define INF 32767

// 定义邻接表中的边结点
typedef struct ArcNode {
    int adjvex;                 // 邻接点的下标
    int weight;                 // 边的权值
    struct ArcNode *nextarc;    // 指向下一条边的指针
} ArcNode;

// 定义邻接表中的顶点结点
typedef struct VertexNode {
    int data;                   // 顶点的数据信息
    ArcNode *firstarc;          // 指向第一条依附该顶点的边的指针
} VertexNode;

// 定义无向图结构体
typedef struct {
    VertexNode adjlist[MAX_VERTEX_NUM];     // 邻接表
    int n, e;                               // 顶点数和边数
} Graph;

// 初始化无向图
void InitGraph(Graph *G) {
    int i;
    G->n = G->e = 0;
    for (i = 0; i < MAX_VERTEX_NUM; i++) {
        G->adjlist[i].data = 0;
        G->adjlist[i].firstarc = NULL;
    }
}

// 向无向图中插入一条边
void InsertEdge(Graph *G, int u, int v, int w) {
    ArcNode *p, *q;
    p = (ArcNode *)malloc(sizeof(ArcNode));
    p->adjvex = v;
    p->weight = w;
    p->nextarc = G->adjlist[u].firstarc;
    G->adjlist[u].firstarc = p;
    q = (ArcNode *)malloc(sizeof(ArcNode));
    q->adjvex = u;
    q->weight = w;
    q->nextarc = G->adjlist[v].firstarc;
    G->adjlist[v].firstarc = q;
    G->e++;
}

// 深度优先遍历
void DFS(Graph *G, int v, int visited[]) {
    ArcNode *p;
    visited[v] = 1;     // 标记该顶点已访问
    printf("%d ", G->adjlist[v].data);   // 输出该顶点
    p = G->adjlist[v].firstarc;
    while (p != NULL) {
        if (visited[p->adjvex] == 0) {  // 如果邻接点未被访问，则递归访问它
            DFS(G, p->adjvex, visited);
        }
        p = p->nextarc;
    }
}

// 用Prim算法求解最小生成树
void Prim(Graph *G) {
    int i, j, k, min, sum = 0, visited[MAX_VERTEX_NUM], lowcost[MAX_VERTEX_NUM], adjvex[MAX_VERTEX_NUM];
    ArcNode *p;
    for (i = 0; i < G->n; i++) {
        visited[i] = 0;         // 初始化标记数组
        lowcost[i] = INF;       // 初始化边权值数组
        adjvex[i] = 0;          // 初始化邻接点数组
    }
    visited[0] = 1;
    for (i = 1; i < G->n; i++) {
        lowcost[i] = INF;
        p = G->adjlist[0].firstarc;
        while (p != NULL) {
            if (p->adjvex == i && p->weight < lowcost[i]) {
                lowcost[i] = p->weight;
                adjvex[i] = 0;
            }
            p = p->nextarc;
        }
    }
    for (i = 1; i < G->n; i++) {
        min = INF;
        for (j = 1; j < G->n; j++) {
            if (visited[j] == 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
        }
        visited[k] = 1;
        sum += min;
        printf("(%d, %d) ", adjvex[k], k);
        for (j = 1; j < G->n; j++) {
            p = G->adjlist[k].firstarc;
            while (p != NULL) {
                if (p->adjvex == j && visited[j] == 0 && p->weight < lowcost[j]) {
                    lowcost[j] = p->weight;
                    adjvex[j] = k;
                }
                p = p->nextarc;
            }
        }
    }
    printf("\n最小生成树的权值为：%d\n", sum);
}

int main() {
    Graph G;
    int i, j, visited[MAX_VERTEX_NUM];
    InitGraph(&G);
    G.n = 6;
    for (i = 0; i < G.n; i++) {
        G.adjlist[i].data = i + 1;
    }
    InsertEdge(&G, 0, 1, 6);
    InsertEdge(&G, 0, 2, 1);
    InsertEdge(&G, 0, 3, 5);
    InsertEdge(&G, 1, 2, 5);
    InsertEdge(&G, 1, 4, 3);
    InsertEdge(&G, 2, 3, 5);
    InsertEdge(&G, 2, 4, 6);
    InsertEdge(&G, 2, 5, 4);
    InsertEdge(&G, 3, 5, 2);
    InsertEdge(&G, 4, 5, 6);
    printf("深度优先遍历：");
    for (i = 0; i < G.n; i++) {
        visited[i] = 0;
    }
    for (i = 0; i < G.n; i++) {
        if (visited[i] == 0) {
            DFS(&G, i, visited);
        }
    }
    printf("\n最小生成树的边为：");
    Prim(&G);
    return 0;
}

这段代码中，我们定义了邻接表中的边结点和顶点结点，并且定义了无向图的结构体。在初始化无向图时，我们将顶点数和边数都设置为0，并将邻接表中的每个顶点的数据信息和第一条边的指针都设置为NULL。在向无向图中插入一条边时，我们需要创建两个边结点，一个插入到顶点u的边表中，另一个插入到顶点v的边表中。

在求解最小生成树问题时，我们使用了Prim算法。该算法的流程如下：

1. 从顶点0开始，将其标记为已访问，并将邻接点的边权值和邻接点下标分别存储到边权值数组和邻接点数组中。

2. 从未访问的顶点中选择一个距离顶点0最近的顶点k，将其标记为已访问，并输出它的邻接点和顶点k之间的边。

3. 更新边权值数组和邻接点数组。

4. 重复步骤2和步骤3，直到所有顶点都被访问。

在Prim算法中，我们使用了visited数组来标记顶点是否被访问过，使用lowcost数组来存储顶点和它的邻接点之间的最小边权值，使用adjvex数组来存储顶点和它的邻接点之间的最小边的邻接点下标。然后，我们从未访问的顶点中选择一个距离顶点0最近的顶点k，并输出它和它的邻接点之间的边。接着，我们更新边权值数组和邻接点数组，重复上述步骤，直到所有顶点都被访问。