已知图结构定义：typedef struct GraphAdjMatrix { elementType Data[MaxVerNum+1]; cellType AdjMatrix[MaxVerNum+1][MaxVerNum+1]; int VerNum; int ArcNum; GraphKind gKind; } Graph;试写出下列问题的代码：1、对给定的图G及出发点v0，设计算法从V0出发深度优先遍历图G，并构造出相应的生成树或生成森林。2、对给定的图G及出发点v0，设计算法从V0出发广度优先遍历图G，并构造出相应的生成树或生成森林。3、实现Prim算法，求解下列给定图G的最小生成树。4、实现Kruskal算法，求解下列给定图G的最小生成树。

1、深度优先遍历并构造生成树的代码实现：

bool visited[MaxVerNum+1]; // 记录节点是否被访问
Graph DFS(Graph G, Vertex v) {
    Graph T;
    T.VerNum = G.VerNum;
    T.ArcNum = 0;
    T.gKind = G.gKind;
    for (Vertex i = 1; i <= G.VerNum; i++) {
        T.Data[i] = G.Data[i];
        visited[i] = false;
    }
    DFS_Traversal(G, v, &T);
    return T;
}

void DFS_Traversal(Graph G, Vertex v, Graph *T) {
    visited[v] = true;
    for (Vertex w = 1; w <= G.VerNum; w++) {
        if (G.AdjMatrix[v][w] != INFINITY && !visited[w]) {
            InsertArc(T, v, w, G.AdjMatrix[v][w]); // 将遍历到的边加入生成树中
            DFS_Traversal(G, w, T);
        }
    }
}

2、广度优先遍历并构造生成树的代码实现：

bool visited[MaxVerNum+1]; // 记录节点是否被访问
Graph BFS(Graph G, Vertex v) {
    Graph T;
    T.VerNum = G.VerNum;
    T.ArcNum = 0;
    T.gKind = G.gKind;
    for (Vertex i = 1; i <= G.VerNum; i++) {
        T.Data[i] = G.Data[i];
        visited[i] = false;
    }
    BFS_Traversal(G, v, &T);
    return T;
}

void BFS_Traversal(Graph G, Vertex v, Graph *T) {
    visited[v] = true;
    Queue Q = CreateQueue(MaxVerNum);
    Enqueue(Q, v);
    while (!IsEmpty(Q)) {
        Vertex w = Dequeue(Q);
        for (Vertex x = 1; x <= G.VerNum; x++) {
            if (G.AdjMatrix[w][x] != INFINITY && !visited[x]) {
                InsertArc(T, w, x, G.AdjMatrix[w][x]); // 将遍历到的边加入生成树中
                visited[x] = true;
                Enqueue(Q, x);
            }
        }
    }
}

3、Prim算法求最小生成树的代码实现：

void Prim(Graph G, Vertex v, Graph *T) {
    int dist[MaxVerNum+1];
    Vertex parent[MaxVerNum+1];
    bool visited[MaxVerNum+1];
    for (Vertex i = 1; i <= G.VerNum; i++) {
        visited[i] = false;
        dist[i] = INFINITY;
    }
    dist[v] = 0;
    while (1) {
        Vertex w = FindMinDist(G, visited, dist);
        if (w == -1) break;
        visited[w] = true;
        for (Vertex x = 1; x <= G.VerNum; x++) {
            if (G.AdjMatrix[w][x] != INFINITY && !visited[x]) {
                if (G.AdjMatrix[w][x] < dist[x]) {
                    dist[x] = G.AdjMatrix[w][x];
                    parent[x] = w;
                }
            }
        }
    }
    for (Vertex i = 1; i <= G.VerNum; i++) {
        if (i == v) continue;
        InsertArc(T, parent[i], i, G.AdjMatrix[parent[i]][i]);
    }
}

Vertex FindMinDist(Graph G, bool visited[], int dist[]) {
    Vertex v = -1;
    int minDist = INFINITY;
    for (Vertex i = 1; i <= G.VerNum; i++) {
        if (!visited[i] && dist[i] < minDist) {
            v = i;
            minDist = dist[i];
        }
    }
    return v;
}

4、Kruskal算法求最小生成树的代码实现：

void Kruskal(Graph G, Graph *T) {
    int n = G.VerNum;
    int m = G.ArcNum;
    Edge E[m];
    int count = 0;
    for (Vertex i = 1; i <= n; i++) {
        for (Vertex j = i+1; j <= n; j++) {
            if (G.AdjMatrix[i][j] != INFINITY) {
                E[count].u = i;
                E[count].v = j;
                E[count].weight = G.AdjMatrix[i][j];
                count++;
            }
        }
    }
    qsort(E, m, sizeof(Edge), cmp); // 将边按照权重从小到大排序
    Set S = InitSet(n);
    for (int i = 0; i < m; i++) {
        SetType s1 = Find(S, E[i].u);
        SetType s2 = Find(S, E[i].v);
        if (s1 != s2) {
            InsertArc(T, E[i].u, E[i].v, E[i].weight); // 将边加入生成树中
            Union(S, s1, s2);
        }
    }
}

int cmp(const void *a, const void *b) {
    return ((Edge*)a)->weight - ((Edge*)b)->weight;
}