c++写一个带有virtual的多继承广度优先搜索

以下是一个使用多继承和广度优先搜索实现的简单示例代码：

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

using namespace std;

class Graph {
public:
    virtual void addEdge(int u, int v) = 0;
    virtual void BFS(int s) = 0;
};

class AdjacencyListGraph : public Graph {
private:
    vector<vector<int>> adj_list;

public:
    AdjacencyListGraph(int n) {
        adj_list.resize(n);
    }

    void addEdge(int u, int v) override {
        adj_list[u].push_back(v);
    }

    void BFS(int s) override {
        vector<bool> visited(adj_list.size(), false);
        queue<int> q;
        visited[s] = true;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            cout << u << " ";
            q.pop();
            for (int v : adj_list[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    q.push(v);
                }
            }
        }
    }
};

class IncidenceMatrixGraph : public Graph {
private:
    vector<vector<bool>> inc_matrix;

public:
    IncidenceMatrixGraph(int n, int m) {
        inc_matrix.resize(n, vector<bool>(m));
    }

    void addEdge(int u, int v) override {
        // Assume undirected graph for simplicity
        for (int j = 0; j < inc_matrix[u].size(); j++) {
            if (inc_matrix[u][j] && inc_matrix[v][j]) {
                return; // Edge already exists
            }
        }
        for (int j = 0; j < inc_matrix[u].size(); j++) {
            inc_matrix[u][j] = inc_matrix[v][j] = true;
        }
    }

    void BFS(int s) override {
        vector<bool> visited(inc_matrix[0].size(), false);
        queue<int> q;
        visited[s] = true;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            cout << u << " ";
            q.pop();
            for (int j = 0; j < inc_matrix[u].size(); j++) {
                if (inc_matrix[u][j]) {
                    for (int i = 0; i < inc_matrix.size(); i++) {
                        if (i != u && inc_matrix[i][j] && !visited[i]) {
                            visited[i] = true;
                            q.push(i);
                        }
                    }
                }
            }
        }
    }
};

int main() {
    Graph* g = new AdjacencyListGraph(4);
    g->addEdge(0, 1);
    g->addEdge(0, 2);
    g->addEdge(1, 2);
    g->addEdge(2, 0);
    g->addEdge(2, 3);
    g->addEdge(3, 3);
    g->BFS(2);

    cout << endl;

    g = new IncidenceMatrixGraph(4, 6);
    g->addEdge(0, 1);
    g->addEdge(0, 2);
    g->addEdge(1, 2);
    g->addEdge(2, 0);
    g->addEdge(2, 3);
    g->addEdge(3, 3);
    g->BFS(2);

    return 0;
}

在这个示例中，我们定义了一个抽象的 `Graph` 类，并在其上实现了两个具体的子类： `AdjacencyListGraph` 和 `IncidenceMatrixGraph`，它们分别使用邻接列表和关联矩阵来表示图。我们还实现了 `BFS` 函数来执行广度优先搜索，并在 `Graph` 类中将其声明为虚函数，以便子类可以覆盖它以提供自己的实现。最后，在 `main` 函数中，我们创建了两个不同类型的图，并在它们上运行 `BFS` 函数以展示它们的效果。