（1）题目1-基础实验 根据图的抽象数据类型的定义，使用邻接矩阵或邻接表实现一个图。 图的基本功能： ①图的建立； ②图的销毁； ③深度优先遍历图； ④广度优先遍历图； ⑤其他（比如连通性判断等自定义操作）。 编写main（）函数测试图的正确性。 思考问题（选做）： 若测试数据量较大，如何使得栈不溢出？使用非递归方式编写新的深度优先遍历函数。提示：可以使用STL中的stack来辅助实现。

以下是使用邻接矩阵实现图的代码：

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

const int MAXN = 100;
const int INF = 0x3f3f3f3f;

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

// 创建图
void createGraph(Graph& g) {
    cout << "请输入顶点数和边数（以空格分隔）：" << endl;
    cin >> g.n >> g.e;
    // 初始化邻接矩阵
    for (int i = 1; i <= g.n; i++) {
        for (int j = 1; j <= g.n; j++) {
            g.g[i][j] = INF;
        }
    }
    // 输入边的信息
    cout << "请输入每条边的起点、终点、权重（以空格分隔）：" << endl;
    for (int i = 0; i < g.e; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g.g[u][v] = w;
        g.g[v][u] = w; // 无向图需要加上这一行
    }
}

// 销毁图
void destroyGraph(Graph& g) {
    g.n = 0;
    g.e = 0;
    for (int i = 1; i <= g.n; i++) {
        for (int j = 1; j <= g.n; j++) {
            g.g[i][j] = INF;
        }
    }
}

// 深度优先遍历
void dfs(Graph& g, int v, bool visited[]) {
    visited[v] = true;
    cout << v << " ";
    for (int i = 1; i <= g.n; i++) {
        if (g.g[v][i] != INF && !visited[i]) {
            dfs(g, i, visited);
        }
    }
}

void dfs(Graph& g, int start) {
    bool visited[MAXN];
    for (int i = 1; i <= g.n; i++) {
        visited[i] = false;
    }
    dfs(g, start, visited);
    cout << endl;
}

// 广度优先遍历
void bfs(Graph& g, int start) {
    bool visited[MAXN];
    for (int i = 1; i <= g.n; i++) {
        visited[i] = false;
    }
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int v = q.front();
        cout << v << " ";
        q.pop();
        for (int i = 1; i <= g.n; i++) {
            if (g.g[v][i] != INF && !visited[i]) {
                q.push(i);
                visited[i] = true;
            }
        }
    }
    cout << endl;
}

// 连通性判断（使用深度优先遍历）
bool isConnected(Graph& g) {
    bool visited[MAXN];
    for (int i = 1; i <= g.n; i++) {
        visited[i] = false;
    }
    dfs(g, 1, visited);
    for (int i = 1; i <= g.n; i++) {
        if (!visited[i]) {
            return false;
        }
    }
    return true;
}

int main() {
    Graph g;
    createGraph(g);
    cout << "深度优先遍历结果：" << endl;
    dfs(g, 1);
    cout << "广度优先遍历结果：" << endl;
    bfs(g, 1);
    cout << "图的连通性：" << isConnected(g) << endl;
    destroyGraph(g);
    return 0;
}

对于数据量较大的情况，我们可以使用非递归方式实现深度优先遍历。具体实现方式是使用一个栈来代替递归，将每个节点的邻接点入栈，并在遍历完一个节点的所有邻接点后弹出栈顶元素。

以下是使用非递归方式实现深度优先遍历的代码：

void dfs(Graph& g, int start) {
    bool visited[MAXN];
    for (int i = 1; i <= g.n; i++) {
        visited[i] = false;
    }
    stack<int> s;
    s.push(start);
    while (!s.empty()) {
        int v = s.top();
        s.pop();
        if (!visited[v]) {
            cout << v << " ";
            visited[v] = true;
            for (int i = g.n; i >= 1; i--) { // 注意遍历顺序
                if (g.g[v][i] != INF && !visited[i]) {
                    s.push(i);
                }
            }
        }
    }
    cout << endl;
}