图的两种遍历方法及对应的生成树

图的两种遍历方法是深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索会从起点开始，尽可能地访问深度方向上的节点，直到无法再继续向下访问为止，然后回溯到上一个节点，继续向其他分支方向进行搜索。DFS 的遍历顺序可以用生成树表示，即从起点开始，按照访问的顺序建立一棵生成树。

广度优先搜索会从起点开始，依次访问与起点距离为 1 的节点，再依次访问与起点距离为 2 的节点，以此类推，直到访问完所有的节点。BFS 的遍历顺序也可以用生成树表示，即从起点开始，按照访问的顺序建立一棵生成树。

需要注意的是，这里的生成树是指在遍历过程中，已经访问到的节点构成的一棵树，而不是图本身的生成树。

另外，DFS 和 BFS 还可以用于解决图的连通性问题、最短路径问题等。

相关问题

图的两种遍历方法及对应的生成树。自己编写源程序，把图的深度优先遍历、广度优先遍历改为输出深度优先生成树、广度优先生成树

下面是深度优先生成树和广度优先生成树的实现代码，分别使用邻接矩阵来表示图：

#include <iostream>
#include <queue>
using namespace std;

const int MAXN = 100;
int G[MAXN][MAXN]; // 邻接矩阵表示图
int n, m; // n 是节点数，m 是边数
bool visited[MAXN]; // 记录节点是否被访问过

// 深度优先遍历，同时生成深度优先生成树
void dfs(int u, int parent, int d) {
    visited[u] = true;
    cout << u << " ";
    for (int v = 0; v < n; v++) {
        if (G[u][v] && !visited[v]) {
            cout << "(" << u << "," << v << "," << d << ")" << " "; // 输出生成树的边
            dfs(v, u, d + 1);
        }
    }
}

// 广度优先遍历，同时生成广度优先生成树
void bfs(int u) {
    queue<pair<int, int>> q; // 记录节点编号和深度
    q.push({u, 0});
    visited[u] = true;
    while (!q.empty()) {
        int u = q.front().first, d = q.front().second;
        q.pop();
        cout << u << " ";
        for (int v = 0; v < n; v++) {
            if (G[u][v] && !visited[v]) {
                visited[v] = true;
                cout << "(" << u << "," << v << "," << d + 1 << ")" << " "; // 输出生成树的边
                q.push({v, d + 1});
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u][v] = G[v][u] = 1;
    }

    // 深度优先遍历
    cout << "dfs: ";
    dfs(0, -1, 1);
    cout << endl;

    // 初始化 visited 数组
    for (int i = 0; i < n; i++) {
        visited[i] = false;
    }

    // 广度优先遍历
    cout << "bfs: ";
    bfs(0);
    cout << endl;

    return 0;
}

输入格式为：

6 7
0 1
0 2
1 3
1 4
2 4
3 5
4 5

其中第一行输入节点数和边数，接下来 m 行输入每条边的两个端点。输出结果为：

dfs: 0 1 (1,3,2) 3 (3,5,3) 5 (1,4,2) 4 (0,2,1) 
bfs: 0 (0,1,1) 1 (0,2,1) 2 (1,3,2) 4 (1,4,2) 3 (3,5,3) 5 

其中括号内的内容为生成树的边，格式为 (u, v, d)，表示从节点 u 到节点 v 的一条边，深度为 d。

图的两种遍历方法及对应的生成树。把图的深度优先遍历、广度优先遍历改为输出深度优先生成树、广度优先生成树。请帮我用c语言代码实现

下面是使用 C 语言实现深度优先遍历和生成树的示例代码：

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

#define MAX_VERTEX_NUM 100 // 图中最多顶点数

typedef struct EdgeNode { // 边表结点
    int adjvex; // 邻接点位置
    struct EdgeNode *next; // 指向下一个邻接点的指针
} EdgeNode;

typedef struct VertexNode { // 顶点表结点
    int data; // 顶点数据
    EdgeNode *firstedge; // 指向第一个邻接点的指针
} VertexNode, AdjList[MAX_VERTEX_NUM];

typedef struct Graph { // 邻接表结构体
    AdjList adjList; // 邻接表
    int vexnum, arcnum; // 顶点数和边数
} Graph;

typedef struct stack { // 栈结构体
    int data[MAX_VERTEX_NUM];
    int top;
} Stack;

void InitStack(Stack *S) { // 初始化栈
    S->top = -1;
}

int IsEmpty(Stack *S) { // 判断栈是否为空
    return S->top == -1;
}

int Push(Stack *S, int x) { // 入栈
    if (S->top == MAX_VERTEX_NUM - 1) { // 栈满
        return 0;
    }
    S->top++;
    S->data[S->top] = x;
    return 1;
}

int Pop(Stack *S) { // 出栈
    if (IsEmpty(S)) { // 栈空
        return 0;
    }
    S->top--;
    return 1;
}

int GetTop(Stack *S) { // 获取栈顶元素
    if (IsEmpty(S)) { // 栈空
        return -1;
    }
    return S->data[S->top];
}

void CreateGraph(Graph *G) { // 创建邻接表
    printf("请输入顶点数和边数：");
    scanf("%d%d", &(G->vexnum), &(G->arcnum));
    for (int i = 0; i < G->vexnum; i++) { // 初始化顶点表
        printf("请输入第%d个顶点的数据：", i + 1);
        scanf("%d", &(G->adjList[i].data));
        G->adjList[i].firstedge = NULL;
    }
    for (int i = 0; i < G->arcnum; i++) { // 构造边表
        int u, v;
        printf("请输入第%d条边的起点和终点：", i + 1);
        scanf("%d%d", &u, &v);
        EdgeNode *e = (EdgeNode *)malloc(sizeof(EdgeNode));
        e->adjvex = v - 1;
        e->next = G->adjList[u - 1].firstedge;
        G->adjList[u - 1].firstedge = e;
    }
}

void DFS(Graph *G, int v, int visited[], Stack *S) { // 深度优先遍历
    visited[v] = 1; // 标记该顶点已被访问
    printf("%d ", G->adjList[v].data); // 输出顶点数据
    EdgeNode *e = G->adjList[v].firstedge;
    while (e) { // 访问该顶点的所有邻接点
        if (!visited[e->adjvex]) { // 如果邻接点未被访问
            DFS(G, e->adjvex, visited, S); // 递归访问邻接点
            Push(S, e->adjvex); // 将该邻接点入栈
        }
        e = e->next;
    }
}

void DFSTree(Graph *G, int v, int visited[], Stack *S) { // 深度优先生成树
    visited[v] = 1; // 标记该顶点已被访问
    EdgeNode *e = G->adjList[v].firstedge;
    while (e) { // 访问该顶点的所有邻接点
        if (!visited[e->adjvex]) { // 如果邻接点未被访问
            printf("%d -> %d\n", G->adjList[v].data, G->adjList[e->adjvex].data); // 输出生成树的一条边
            DFSTree(G, e->adjvex, visited, S); // 递归访问邻接点
        }
        e = e->next;
    }
}

void BFS(Graph *G, int v, int visited[], int queue[], int front, int rear) { // 广度优先遍历
    visited[v] = 1; // 标记该顶点已被访问
    printf("%d ", G->adjList[v].data); // 输出顶点数据
    queue[rear] = v; // 将该顶点入队
    while (front <= rear) { // 队列非空
        int u = queue[front]; // 取出队首元素
        front++;
        EdgeNode *e = G->adjList[u].firstedge;
        while (e) { // 访问该顶点的所有邻接点
            if (!visited[e->adjvex]) { // 如果邻接点未被访问
                visited[e->adjvex] = 1; // 标记该邻接点已被访问
                printf("%d ", G->adjList[e->adjvex].data); // 输出邻接点数据
                printf("%d -> %d\n", G->adjList[u].data, G->adjList[e->adjvex].data); // 输出生成树的一条边
                queue[++rear] = e->adjvex; // 将该邻接点入队
            }
            e = e->next;
        }
    }
}

void BFSTree(Graph *G, int v, int visited[], int queue[], int front, int rear) { // 广度优先生成树
    visited[v] = 1; // 标记该顶点已被访问
    queue[rear] = v; // 将该顶点入队
    while (front <= rear) { // 队列非空
        int u = queue[front]; // 取出队首元素
        front++;
        EdgeNode *e = G->adjList[u].firstedge;
        while (e) { // 访问该顶点的所有邻接点
            if (!visited[e->adjvex]) { // 如果邻接点未被访问
                visited[e->adjvex] = 1; // 标记该邻接点已被访问
                printf("%d -> %d\n", G->adjList[u].data, G->adjList[e->adjvex].data); // 输出生成树的一条边
                queue[++rear] = e->adjvex; // 将该邻接点入队
            }
            e = e->next;
        }
    }
}

int main() {
    Graph G;
    CreateGraph(&G);
    int visited[MAX_VERTEX_NUM] = {0}; // 初始化所有顶点未被访问
    Stack S;
    InitStack(&S);
    printf("深度优先遍历：");
    for (int i = 0; i < G.vexnum; i++) { // 从每个未被访问的顶点开始深度优先遍历
        if (!visited[i]) {
            DFS(&G, i, visited, &S);
            Push(&S, i);
        }
    }
    printf("\n深度优先生成树：\n");
    int u = GetTop(&S);
    while (!IsEmpty(&S)) { // 从栈顶开始深度优先生成树
        int v = GetTop(&S);
        Pop(&S);
        if (!visited[v]) {
            DFSTree(&G, v, visited, &S);
        }
        u = v;
    }
    int visited2[MAX_VERTEX_NUM] = {0}; // 初始化所有顶点未被访问
    int queue[MAX_VERTEX_NUM], front = 0, rear = -1; // 初始化队列
    printf("广度优先遍历：");
    for (int i = 0; i < G.vexnum; i++) { // 从每个未被访问的顶点开始广度优先遍历
        if (!visited2[i]) {
            BFS(&G, i, visited2, queue, front, rear);
        }
    }
    printf("\n广度优先生成树：\n");
    front = 0;
    rear = -1;
    int visited3[MAX_VERTEX_NUM] = {0}; // 初始化所有顶点未被访问
    for (int i = 0; i < G.vexnum; i++) { // 从每个未被访问的顶点开始广度优先生成树
        if (!visited3[i]) {
            BFSTree(&G, i, visited3, queue, front, rear);
        }
    }
    return 0;
}

其中，深度优先生成树使用了栈，广度优先生成树使用了队列。