搜索

图的类

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

class Graph {
    int V; // 图的顶点数
    vector<list<int>> adj; // 邻接表
public:
    Graph(int V); // 构造函数
    void addEdge(int v, int w); // 添加边
    void DFSUtil(int v, bool visited[]); // 用于DFS的辅助递归函数
    void DFS(int v); // 深度优先遍历函数
    void BFS(int s); // 宽度优先遍历函数
};

Graph::Graph(int V) {
    this->V = V;
    adj.resize(V);
}

void Graph::addEdge(int v, int w) {
    adj[v].push_back(w); // 添加w到v的邻接表中
}

DFS

void Graph::DFSUtil(int v, bool visited[]) {
    // 标记当前节点为已访问
    visited[v] = true;
    cout << v << " ";

    // 递归访问所有未访问过的相邻节点
    for (int i : adj[v]) {
        if (!visited[i])
            DFSUtil(i, visited);
    }
}

void Graph::DFS(int v) {
    // 初始化所有顶点为未访问状态
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;

    // 调用递归辅助函数进行DFS
    DFSUtil(v, visited);

    delete[] visited; // 清理内存
}

BFS

void Graph::BFS(int s) {
    // 记录是否访问过
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;

    // 创建一个队列用于BFS
    queue<int> queue;

    // 标记当前节点为已访问并入队
    visited[s] = true;
    queue.push(s);

    while (!queue.empty()) {
        // 出队一个顶点
        s = queue.front();
        cout << s << " ";
        queue.pop();

        // 获取刚出队的顶点的所有相邻的顶点
        for (int i : adj[s]) {
            if (!visited[i]) {
                visited[i] = true;
                queue.push(i);
            }
        }
    }

    delete[] visited; // 清理内存
}

测试

int main() {
    // 创建一个图
    Graph g(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);

    cout << "Following is Depth First Traversal (starting from vertex 2): \n";
    g.DFS(2);

    return 0;
}

拓扑排序

只有有向无环图能够进行拓扑排序

Kahn算法

Kahn算法步骤：
1.计算所有顶点的入度：入度是指指向该顶点的边的数量。
2.将所有入度为0的顶点加入队列。
3.从队列中取出一个顶点，将其加入结果列表。
4.对于该顶点的所有邻接顶点，减少它们的入度。如果某个邻接顶点的入度变为 0，将其加入队列。
5.重复步骤3和4，直到队列为空。
6.检查结果列表中的顶点数量是否等于图中的顶点数量。如果相等，则图是DAG，结果列表即为拓扑排序；否则，图中存在环，无法进行拓扑排序。

代码实现

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

using namespace std;

class Graph {
    int V; // 图的顶点数
    vector<list<int>> adj; // 邻接表
public:
    Graph(int V); // 构造函数
    void addEdge(int v, int w); // 添加边
    vector<int> topologicalSort(); // 拓扑排序函数
};

Graph::Graph(int V) {
    this->V = V;
    adj.resize(V);
}

void Graph::addEdge(int v, int w) {
    adj[v].push_back(w); // 添加w到v的邻接表中
}

vector<int> Graph::topologicalSort() {
    vector<int> inDegree(V, 0); // 记录入度
    for (int u = 0; u < V; ++u) {
        for (int v : adj[u]) {//遍历邻接表
            ++inDegree[v];
        }
    }

    queue<int> q;
    for (int i = 0; i < V; ++i) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    vector<int> topoOrder;//保存拓扑排序后的结果
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topoOrder.push_back(u);

        for (int v : adj[u]) {//把与u相邻的所有顶点都入队
            --inDegree[v];//删除顶点u后相邻顶点入度减一
            if (inDegree[v] == 0) {
                q.push(v);
            }
        }
    }

    if (topoOrder.size() != V) {
        // 图中存在环，无法进行拓扑排序
        return {};
    }

    return topoOrder;
}

int main() {
    Graph g(6);
    g.addEdge(5, 2);
    g.addEdge(5, 0);
    g.addEdge(4, 0);
    g.addEdge(4, 1);
    g.addEdge(2, 3);
    g.addEdge(3, 1);

    vector<int> topoOrder = g.topologicalSort();

    if (topoOrder.empty()) {
        cout << "Graph has at least one cycle. Topological sorting is not possible.\n";
    } else {
        cout << "Topological order: ";
        for (int v : topoOrder) {
            cout << v << " ";
        }
        cout << endl;
    }

    return 0;
}