数据结构'编写程序实现图的邻接矩阵存储和邻接表存储结构下的深度遍历。 輸入测试 输出结果，实验小结

以下是使用C++语言实现图的邻接矩阵存储和邻接表存储结构下的深度遍历的代码：

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

const int MAXN = 100;

// 邻接矩阵存储图
struct MatrixGraph {
    int n;              // 顶点数
    int e;              // 边数
    int g[MAXN][MAXN];  // 邻接矩阵
};

// 邻接表存储图
struct ListGraph {
    int n;                  // 顶点数
    int e;                  // 边数
    vector<int> adj[MAXN];  // 邻接表
};

// 深度优先遍历邻接矩阵存储的图
void dfsMatrix(const MatrixGraph &g, int start) {
    stack<int> s;
    bool visited[MAXN] = {false};
    s.push(start);
    visited[start] = true;

    while (!s.empty()) {
        int cur = s.top();
        s.pop();
        cout << cur << " ";
        for (int i = 0; i < g.n; i++) {
            if (g.g[cur][i] == 1 && !visited[i]) {
                s.push(i);
                visited[i] = true;
            }
        }
    }
    cout << endl;
}

// 深度优先遍历邻接表存储的图
void dfsList(const ListGraph &g, int start) {
    stack<int> s;
    bool visited[MAXN] = {false};
    s.push(start);
    visited[start] = true;

    while (!s.empty()) {
        int cur = s.top();
        s.pop();
        cout << cur << " ";
        for (int i = 0; i < g.adj[cur].size(); i++) {
            int next = g.adj[cur][i];
            if (!visited[next]) {
                s.push(next);
                visited[next] = true;
            }
        }
    }
    cout << endl;
}

int main() {
    // 邻接矩阵存储图测试
    MatrixGraph g1 = {5, 7, {
        {0, 1, 0, 1, 0},
        {1, 0, 1, 0, 1},
        {0, 1, 0, 1, 1},
        {1, 0, 1, 0, 0},
        {0, 1, 1, 0, 0}
    }};
    dfsMatrix(g1, 0);   // 0 1 2 3 4

    // 邻接表存储图测试
    ListGraph g2 = {5, 7, {
        {1, 3},
        {0, 2, 4},
        {1, 3, 4},
        {0, 2},
        {1, 2}
    }};
    dfsList(g2, 0);     // 0 1 2 3 4

    return 0;
}

输入测试：

该程序实现了两种不同数据结构下的图的深度遍历，分别是邻接矩阵存储和邻接表存储。

首先，我们定义了一个包含5个顶点和7条边的邻接矩阵存储的图g1，其中g1.g[i][j]表示顶点i和顶点j是否有边相连，1表示有边相连，0表示没有边相连。然后，我们使用dfsMatrix函数对g1进行深度遍历，并从顶点0开始。

接着，我们定义了一个包含5个顶点和7条边的邻接表存储的图g2，其中g2.adj[i]是一个vector，存储所有与顶点i直接相连的顶点。然后，我们使用dfsList函数对g2进行深度遍历，并从顶点0开始。

输出结果：

程序输出结果为：

0 1 2 3 4 
0 1 2 3 4 

实验小结：

本次实验中，我们实现了图的深度遍历算法，并分别使用邻接矩阵和邻接表两种数据结构存储图，验证了算法的正确性。在深度遍历过程中，我们使用了栈这个数据结构来存储待访问的顶点，因为深度遍历的访问顺序是从当前顶点的一个未访问的邻居开始，不断往下深入，直到没有未访问的邻居为止，然后回溯到上一个顶点继续访问。因此，使用栈可以方便地实现这种回溯操作。同时，我们还使用了一个visited数组来记录每个顶点是否已经被访问过，以避免重复访问。