用深度优先遍历解决最小生成树问题

深度优先遍历算法并不适用于解决最小生成树问题。最小生成树问题通常使用贪心算法来解决，其中包括 Prim算法和Kruskal算法。这两种算法都是基于贪心策略的，Prim算法从一个顶点开始，不断选择与当前集合距离最小的节点加入集合，直到所有节点都被加入为止，而Kruskal算法则是从边出发，按照边权值从小到大的顺序加入边，直到加入n-1条边为止。这两种算法都可以求解最小生成树问题，而深度优先遍历算法并不适用于此问题。

相关问题

用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，并输出它和它的邻接点之间的边。接着，我们更新边权值数组和邻接点数组，重复上述步骤，直到所有顶点都被访问。

深度优先遍历与广度优先遍历的不同

深度优先遍历（Depth-First Search，简称 DFS）和广度优先遍历（Breadth-First Search，简称 BFS）都是图的遍历算法。

深度优先遍历是一种先深度后广度的遍历方式，它从起点开始，访问一个未访问过的相邻节点，然后沿着这个节点继续访问下去，直到这条路径访问完为止，然后回溯到上一个节点，再继续访问其它相邻节点，以此类推。如果某个节点的所有相邻节点都已经访问过了，那么就回溯到上一个节点，直到所有的节点都被访问过。

广度优先遍历是一种先广度后深度的遍历方式，它从起点开始，先访问起点的所有相邻节点，然后再依次访问这些节点的相邻节点，以此类推。广度优先遍历通常使用队列来实现，每个节点访问完后都将其相邻节点加入队列中，直到队列为空为止。

总的来说，深度优先遍历适用于解决连通性问题，如求解连通块、拓扑排序等问题；广度优先遍历适用于求解最短路径、最小生成树等问题。