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

1、从出发点v0开始深度优先遍历图G的代码如下：

void DFS(Graph &G, int v, bool visited[], int parent[]) {
visited[v] = true; // 标记v已访问
for (int w = firstAdj(G, v); w >= 0; w = nextAdj(G, v, w)) { // 遍历v的所有邻接点
if (!visited[w]) { // 若w未被访问
parent[w] = v; // 记录v是w的父亲节点
DFS(G, w, visited, parent); // 递归访问w
}
}
}

void DFSTraverse(Graph &G, int v0, bool visited[], int parent[]) {
for (int i = 1; i <= G.VerNum; i++) {
visited[i] = false; // 初始化visited数组
parent[i] = -1; // 初始化parent数组
}
DFS(G, v0, visited, parent); // 从出发点v0开始深度优先遍历
}

2、从出发点v0开始广度优先遍历图G的代码如下：

void BFSTraverse(Graph &G, int v0, bool visited[], int parent[]) {
queue<int> Q; // 定义队列
visited[v0] = true; // 标记v0已访问
Q.push(v0); // 将v0入队
while (!Q.empty()) { // 队列不为空时
int v = Q.front(); // 取队首元素v
Q.pop(); // 将v出队
for (int w = firstAdj(G, v); w >= 0; w = nextAdj(G, v, w)) { // 遍历v的所有邻接点
if (!visited[w]) { // 若w未被访问
visited[w] = true; // 标记w已访问
parent[w] = v; // 记录v是w的父亲节点
Q.push(w); // 将w入队
}
}
}
}

3、Prim算法的代码如下：

typedef struct {
elementType adjvex; // 存储v到U的最短边的邻接点
int lowcost; // 存储v到U的最短边的权值
} closedge[MaxVerNum+1];

void Prim(Graph &G, int v, closedge ce[]) {
for (int i = 1; i <= G.VerNum; i++) { // 初始化closedge数组
if (i != v) {
ce[i].adjvex = v;
ce[i].lowcost = G.AdjMatrix[v][i];
}
}
ce[v].lowcost = -1; // 标记v已加入U中
for (int i = 1; i < G.VerNum; i++) { // 循环n-1次
int min = INF, w;
for (int j = 1; j <= G.VerNum; j++) { // 选取closedge中lowcost最小的边
if (ce[j].lowcost != -1 && ce[j].lowcost < min) {
min = ce[j].lowcost;
w = j;
}
}
ce[w].lowcost = -1; // 标记w已加入U中
for (int j = 1; j <= G.VerNum; j++) { // 更新closedge数组
if (ce[j].lowcost != -1 && G.AdjMatrix[w][j] < ce[j].lowcost) {
ce[j].adjvex = w;
ce[j].lowcost = G.AdjMatrix[w][j];
}
}
}
}

4、Kruskal算法的代码如下：

typedef struct {
int a; // 边的一个顶点
int b; // 边的另一个顶点
int w; // 边的权值
} Edge;

bool cmp(Edge e1, Edge e2) { // 边按权值从小到大排序的比较函数
return e1.w < e2.w;
}

int Find(int parent[], int v) { // 查找v所在的集合
while (parent[v] > 0) {
v = parent[v];
}
return v;
}

void Union(int parent[], int r1, int r2) { // 合并r1和r2所在的集合
int t = parent[r1] + parent[r2];
if (parent[r1] > parent[r2]) {
parent[r1] = r2;
parent[r2] = t;
} else {
parent[r2] = r1;
parent[r1] = t;
}
}

void Kruskal(Graph &G, Edge T[]) {
Edge E[MaxEdgeNum];
int parent[MaxVerNum+1];
int k = 0;
for (int i = 1; i <= G.VerNum; i++) { // 初始化parent数组
parent[i] = -1;
}
for (int i = 1; i <= G.VerNum; i++) { // 提取所有边
for (int j = i+1; j <= G.VerNum; j++) {
if (G.AdjMatrix[i][j] != INF) {
E[k].a = i;
E[k].b = j;
E[k].w = G.AdjMatrix[i][j];
k++;
}
}
}
sort(E, E+k, cmp); // 将边按权值从小到大排序
int cnt = 0; // 统计T中已选边数
for (int i = 0; i < k; i++) { // 遍历所有边
int r1 = Find(parent, E[i].a);
int r2 = Find(parent, E[i].b);
if (r1 != r2) { // 若两个顶点不在同一个集合中
T[cnt++] = E[i]; // 选取该边
Union(parent, r1, r2); // 合并两个集合
if (cnt == G.VerNum-1) { // 已选n-1条边，即可退出循环
break;
}
}
}
}