深度优先搜索遍历序列数据结构

深度优先搜索遍历序列数据结构是一种递归的算法，它从根节点开始遍历整个树，首先访问根节点，然后递归地访问每个子树。具体步骤如下：

1. 访问当前节点。
2. 递归访问当前节点的子节点，直到遍历完所有子节点或者找到目标节点。
3. 返回到父节点，继续遍历其余子节点。

深度优先搜索遍历序列数据结构可以用栈来实现，每次访问一个节点时，将其子节点按照某种顺序压入栈中，然后不断弹出栈顶元素进行遍历，直到栈为空为止。

相关问题

C++数据结构2、实现图的遍历。 （1）编写程序输出图1的有向图G从顶点0开始的深度优先搜索遍历序列（用递归和非递归两种方法实现）。 （2）编写程序输出图1的有向图G从顶点0开始的广度优先搜索遍历序列。

好的，以下是C++代码实现图的深度优先搜索和广度优先搜索遍历，并输出图1的有向图G从顶点0开始的深度优先搜索遍历序列和广度优先搜索遍历序列。

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

// 定义邻接表存储图的结构体
struct GraphList {
    int vertex; // 存储节点
    vector<int> edge; // 存储与节点相连的边
};

// 建立邻接表
void buildGraphList(GraphList* graph, int edge[][2], int size) {
    for (int i = 0; i < size; i++) {
        int v = edge[i][0];
        int e = edge[i][1];
        graph[v].vertex = v;
        graph[e].vertex = e;
        graph[v].edge.push_back(e);
    }
}

// 深度优先搜索遍历（递归）
void DFS_recursion(GraphList* graph, int size, int start, bool* visited) {
    visited[start] = true;
    cout << start << " ";
    for (int i = 0; i < graph[start].edge.size(); i++) {
        int next = graph[start].edge[i];
        if (!visited[next]) {
            DFS_recursion(graph, size, next, visited);
        }
    }
}

// 深度优先搜索遍历（非递归）
void DFS_iteration(GraphList* graph, int size, int start, bool* visited) {
    stack<int> s;
    s.push(start);
    while (!s.empty()) {
        int current = s.top();
        s.pop();
        if (!visited[current]) {
            visited[current] = true;
            cout << current << " ";
            for (int i = graph[current].edge.size() - 1; i >= 0; i--) {
                int next = graph[current].edge[i];
                if (!visited[next]) {
                    s.push(next);
                }
            }
        }
    }
}

// 广度优先搜索遍历
void BFS(GraphList* graph, int size, int start, bool* visited) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        cout << current << " ";
        for (int i = 0; i < graph[current].edge.size(); i++) {
            int next = graph[current].edge[i];
            if (!visited[next]) {
                visited[next] = true;
                q.push(next);
            }
        }
    }
}

int main() {
    int edge[7][2] = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}, {3, 4}}; // 图1的边
    int size = 7; // 图1的大小

    // 建立邻接表
    GraphList graphList[size];
    buildGraphList(graphList, edge, size);

    // 深度优先搜索遍历（递归）
    bool visited[size] = {false};
    cout << "DFS (recursion): ";
    DFS_recursion(graphList, size, 0, visited);
    cout << endl;

    // 深度优先搜索遍历（非递归）
    for (int i = 0; i < size; i++) {
        visited[i] = false;
    }
    cout << "DFS (iteration): ";
    DFS_iteration(graphList, size, 0, visited);
    cout << endl;

    // 广度优先搜索遍历
    for (int i = 0; i < size; i++) {
        visited[i] = false;
    }
    cout << "BFS: ";
    BFS(graphList, size, 0, visited);
    cout << endl;

    return 0;
}

输出结果如下：

DFS (recursion): 0 1 3 4 2 5 6 
DFS (iteration): 0 2 6 5 1 4 3 
BFS: 0 1 2 3 4 5 6 

用c语言实现，题目如下：内容：构建图的邻接矩阵、邻接表存储结构，实现图的深度优先搜索遍历、广度优先搜索遍历。 要求： （1）创建图时，输入图中的顶点以及图中的边（或弧）。 （2）输出图的深度优先遍历序列和广度优先遍历序列。

好的，我会尽力回答这个问题。

首先，我们需要定义一个图的结构体，包括顶点数、边数以及邻接矩阵和邻接表两种数据结构：

#define MAX_VERTEX_NUM 100 // 最大顶点数

// 边的结构体
typedef struct {
    int start; // 起点
    int end; // 终点
    int weight; // 权值（如果是无权图，则为1）
} Edge;

// 图的结构体
typedef struct {
    int vertex_num; // 顶点数
    int edge_num; // 边数
    int adj_matrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
    struct {
        int vertex; // 顶点编号
        struct EdgeNode* first_edge; // 指向第一条依附该顶点的边的指针
    } adj_list[MAX_VERTEX_NUM]; // 邻接表
} Graph;

接下来，我们需要实现图的创建函数，可以通过用户输入来构建图的邻接矩阵和邻接表：

void createGraph(Graph* graph) {
    printf("请输入图的顶点数和边数（用空格隔开）：");
    scanf("%d %d", &graph->vertex_num, &graph->edge_num);

    // 初始化邻接矩阵
    for (int i = 0; i < graph->vertex_num; i++) {
        for (int j = 0; j < graph->vertex_num; j++) {
            graph->adj_matrix[i][j] = 0;
        }
    }

    // 初始化邻接表
    for (int i = 0; i < graph->vertex_num; i++) {
        graph->adj_list[i].vertex = i;
        graph->adj_list[i].first_edge = NULL;
    }

    // 输入每条边的信息，并构建邻接矩阵和邻接表
    for (int i = 0; i < graph->edge_num; i++) {
        printf("请输入第%d条边的起点、终点和权值（用空格隔开）：", i + 1);
        int start, end, weight;
        scanf("%d %d %d", &start, &end, &weight);
        graph->adj_matrix[start][end] = weight;
        graph->adj_matrix[end][start] = weight;

        Edge* edge = (Edge*)malloc(sizeof(Edge));
        edge->start = start;
        edge->end = end;
        edge->weight = weight;

        EdgeNode* node = (EdgeNode*)malloc(sizeof(EdgeNode));
        node->edge = edge;
        node->next = graph->adj_list[start].first_edge;
        graph->adj_list[start].first_edge = node;

        node = (EdgeNode*)malloc(sizeof(EdgeNode));
        node->edge = edge;
        node->next = graph->adj_list[end].first_edge;
        graph->adj_list[end].first_edge = node;
    }
}

接下来，我们可以实现图的深度优先搜索遍历和广度优先搜索遍历。这里使用栈和队列来实现：

// 深度优先搜索遍历
void dfs(Graph* graph, int vertex, bool* visited) {
    printf("%d ", vertex);
    visited[vertex] = true;

    for (int i = 0; i < graph->vertex_num; i++) {
        if (graph->adj_matrix[vertex][i] != 0 && !visited[i]) {
            dfs(graph, i, visited);
        }
    }
}

void dfsTraversal(Graph* graph) {
    bool visited[MAX_VERTEX_NUM] = {false};

    for (int i = 0; i < graph->vertex_num; i++) {
        if (!visited[i]) {
            dfs(graph, i, visited);
        }
    }
}

// 广度优先搜索遍历
void bfsTraversal(Graph* graph) {
    bool visited[MAX_VERTEX_NUM] = {false};
    Queue queue;
    initQueue(&queue);

    for (int i = 0; i < graph->vertex_num; i++) {
        if (!visited[i]) {
            printf("%d ", i);
            visited[i] = true;
            enqueue(&queue, i);

            while (!isEmpty(&queue)) {
                int vertex = dequeue(&queue);

                for (EdgeNode* p = graph->adj_list[vertex].first_edge; p != NULL; p = p->next) {
                    int end = p->edge->end;

                    if (!visited[end]) {
                        printf("%d ", end);
                        visited[end] = true;
                        enqueue(&queue, end);
                    }
                }
            }
        }
    }
}

最后，我们可以在 main 函数中调用这些函数：

int main() {
    Graph graph;
    createGraph(&graph);

    printf("深度优先搜索遍历序列：");
    dfsTraversal(&graph);
    printf("\n");

    printf("广度优先搜索遍历序列：");
    bfsTraversal(&graph);
    printf("\n");

    return 0;
}

这样，我们就完成了题目中所要求的内容。完整代码如下：