C++代码关于1、创建无向图的邻接表存储结构 2、完成图的深度优先遍历 3、完成图的广度优先遍历

1. 创建无向图的邻接表存储结构

#include <iostream>
#include <vector>

using namespace std;

class Graph {
private:
    int V; // 图的顶点数
    vector<vector<int>> adj; // 邻接表存储结构
public:
    Graph(int V) {
        this->V = V;
        adj.resize(V);
    }
    
    void addEdge(int v, int w) {
        adj[v].push_back(w);
        adj[w].push_back(v);
    }
    
    void printGraph() {
        for(int i = 0; i < V; i++) {
            cout << "顶点 " << i << " 的邻接表: ";
            for(int j = 0; j < adj[i].size(); j++) {
                cout << adj[i][j] << " ";
            }
            cout << endl;
        }
    }
};

2. 完成图的深度优先遍历

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

using namespace std;

class Graph {
private:
    int V; // 图的顶点数
    vector<vector<int>> adj; // 邻接表存储结构
public:
    Graph(int V) {
        this->V = V;
        adj.resize(V);
    }
    
    void addEdge(int v, int w) {
        adj[v].push_back(w);
        adj[w].push_back(v);
    }
    
    void DFS(int start) {
        vector<bool> visited(V, false); // 标记是否访问过
        stack<int> s; // 用栈来实现
        s.push(start);
        visited[start] = true;
        while(!s.empty()) {
            int cur = s.top();
            cout << cur << " ";
            s.pop();
            for(int i = 0; i < adj[cur].size(); i++) {
                int next = adj[cur][i];
                if(!visited[next]) {
                    s.push(next);
                    visited[next] = true;
                }
            }
        }
    }
};

3. 完成图的广度优先遍历

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Graph {
private:
    int V; // 图的顶点数
    vector<vector<int>> adj; // 邻接表存储结构
public:
    Graph(int V) {
        this->V = V;
        adj.resize(V);
    }
    
    void addEdge(int v, int w) {
        adj[v].push_back(w);
        adj[w].push_back(v);
    }
    
    void BFS(int start) {
        vector<bool> visited(V, false); // 标记是否访问过
        queue<int> q; // 用队列来实现
        q.push(start);
        visited[start] = true;
        while(!q.empty()) {
            int cur = q.front();
            cout << cur << " ";
            q.pop();
            for(int i = 0; i < adj[cur].size(); i++) {
                int next = adj[cur][i];
                if(!visited[next]) {
                    q.push(next);
                    visited[next] = true;
                }
            }
        }
    }
};