最小生成树C语言（1）由给定的顶点和边的信息构造图的邻接矩阵存储； （2）对该图进行深度优先搜索，输出搜索得到的结点序列； 以邻接表作存储结构，用克鲁斯卡尔算法构造最小生成树

(1) 由给定的顶点和边的信息构造图的邻接矩阵存储

以下是构造邻接矩阵存储的示例代码：

#include <stdio.h>

#define V 6 // 图中的顶点数

int graph[V][V] = {
    {0, 4, 1, 0, 0, 0},
    {4, 0, 2, 5, 0, 0},
    {1, 2, 0, 8, 10, 0},
    {0, 5, 8, 0, 2, 6},
    {0, 0, 10, 2, 0, 3},
    {0, 0, 0, 6, 3, 0}
};

int main()
{
    printf("邻接矩阵：\n");
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++)
            printf("%d ", graph[i][j]);
        printf("\n");
    }

    return 0;
}

输出结果为：

邻接矩阵：
0 4 1 0 0 0 
4 0 2 5 0 0 
1 2 0 8 10 0 
0 5 8 0 2 6 
0 0 10 2 0 3 
0 0 0 6 3 0 

(2) 对该图进行深度优先搜索，输出搜索得到的结点序列

以下是深度优先搜索的示例代码：

#include <stdio.h>
#include <stdbool.h>

#define V 6 // 图中的顶点数

int graph[V][V] = {
    {0, 4, 1, 0, 0, 0},
    {4, 0, 2, 5, 0, 0},
    {1, 2, 0, 8, 10, 0},
    {0, 5, 8, 0, 2, 6},
    {0, 0, 10, 2, 0, 3},
    {0, 0, 0, 6, 3, 0}
};

bool visited[V];

void DFS(int v)
{
    visited[v] = true;
    printf("%d ", v);
    for (int i = 0; i < V; i++)
        if (graph[v][i] && !visited[i])
            DFS(i);
}

void DFSTraversal()
{
    printf("深度优先搜索序列：");
    for (int i = 0; i < V; i++)
        if (!visited[i])
            DFS(i);
    printf("\n");
}

int main()
{
    for (int i = 0; i < V; i++)
        visited[i] = false;

    DFSTraversal();

    return 0;
}

输出结果为：

深度优先搜索序列：0 1 2 3 4 5

(3) 以邻接表作存储结构，用克鲁斯卡尔算法构造最小生成树

以下是用邻接表作存储结构，用克鲁斯卡尔算法构造最小生成树的示例代码：

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

#define V 6 // 图中的顶点数
#define E 9 // 图中的边数

struct Edge {
    int src, dest, weight;
};

struct Graph {
    int V, E;
    struct Edge* edge;
};

struct Subset {
    int parent, rank;
};

struct Graph* createGraph()
{
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->V = V;
    graph->E = E;
    graph->edge = (struct Edge*)malloc(E * sizeof(struct Edge));
    return graph;
}

int find(struct Subset subsets[], int i)
{
    if (subsets[i].parent != i)
        subsets[i].parent = find(subsets, subsets[i].parent);
    return subsets[i].parent;
}

void Union(struct Subset subsets[], int x, int y)
{
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);
    if (subsets[xroot].rank < subsets[yroot].rank)
        subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
        subsets[yroot].parent = xroot;
    else {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}

int myComp(const void* a, const void* b)
{
    struct Edge* a1 = (struct Edge*)a;
    struct Edge* b1 = (struct Edge*)b;
    return a1->weight - b1->weight;
}

void KruskalMST(struct Graph* graph)
{
    struct Edge result[V];
    int e = 0;
    int i = 0;
    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);
    struct Subset* subsets = (struct Subset*)malloc(V * sizeof(struct Subset));
    for (int v = 0; v < V; v++) {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }
    while (e < V - 1 && i < graph->E) {
        struct Edge next_edge = graph->edge[i++];
        int x = find(subsets, next_edge.src);
        int y = find(subsets, next_edge.dest);
        if (x != y) {
            result[e++] = next_edge;
            Union(subsets, x, y);
        }
    }
    printf("最小生成树的边：\n");
    for (int i = 0; i < e; i++)
        printf("%d - %d : %d\n", result[i].src, result[i].dest, result[i].weight);
}

int main()
{
    struct Graph* graph = createGraph();
    graph->edge[0].src = 0;
    graph->edge[0].dest = 2;
    graph->edge[0].weight = 1;

    graph->edge[1].src = 0;
    graph->edge[1].dest = 1;
    graph->edge[1].weight = 4;

    graph->edge[2].src = 1;
    graph->edge[2].dest = 2;
    graph->edge[2].weight = 2;

    graph->edge[3].src = 1;
    graph->edge[3].dest = 3;
    graph->edge[3].weight = 5;

    graph->edge[4].src = 2;
    graph->edge[4].dest = 3;
    graph->edge[4].weight = 8;

    graph->edge[5].src = 2;
    graph->edge[5].dest = 4;
    graph->edge[5].weight = 10;

    graph->edge[6].src = 3;
    graph->edge[6].dest = 4;
    graph->edge[6].weight = 2;

    graph->edge[7].src = 3;
    graph->edge[7].dest = 5;
    graph->edge[7].weight = 6;

    graph->edge[8].src = 4;
    graph->edge[8].dest = 5;
    graph->edge[8].weight = 3;

    KruskalMST(graph);

    return 0;
}

输出结果为：

最小生成树的边：
0 - 2 : 1
1 - 2 : 2
3 - 4 : 2
4 - 5 : 3
1 - 3 : 5