c++ 用单链表存储图的顶点实现图的BFS算法和DFS算法

首先，我们需要定义一个图的节点类，包含节点值和指向下一个节点的指针：

class Node {
public:
    int val;
    Node* next;
    Node(int v) : val(v), next(nullptr) {}
};

接着，我们需要定义一个图类，包括节点数和指向节点的数组。这里使用邻接表来存储图。

class Graph {
public:
    int V;
    Node** adjList;
    Graph(int v) : V(v) {
        adjList = new Node*[V];
        for (int i = 0; i < V; i++) {
            adjList[i] = nullptr;
        }
    }
    ~Graph() {
        for (int i = 0; i < V; i++) {
            Node* cur = adjList[i];
            while (cur) {
                Node* next = cur->next;
                delete cur;
                cur = next;
            }
        }
        delete[] adjList;
    }
    void addEdge(int src, int dest) {
        Node* newNode = new Node(dest);
        newNode->next = adjList[src];
        adjList[src] = newNode;
    }
};

接下来，我们可以实现BFS算法。BFS算法使用队列来遍历图，首先将起始节点入队，然后将其标记为已访问，然后从队列中弹出节点并访问其所有未访问的相邻节点，并将它们全部入队。

void BFS(Graph* graph, int start) {
    bool* visited = new bool[graph->V];
    for (int i = 0; i < graph->V; i++) {
        visited[i] = false;
    }
    std::queue<int> q;
    visited[start] = true;
    q.push(start);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        std::cout << cur << " ";
        Node* adj = graph->adjList[cur];
        while (adj) {
            int v = adj->val;
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
            adj = adj->next;
        }
    }
    std::cout << std::endl;
    delete[] visited;
}

最后，我们可以实现DFS算法。DFS算法使用递归来遍历图，首先将起始节点标记为已访问，然后访问其相邻节点，并对每个未访问的相邻节点递归调用DFS算法。

void DFS(Graph* graph, int cur, bool* visited) {
    visited[cur] = true;
    std::cout << cur << " ";
    Node* adj = graph->adjList[cur];
    while (adj) {
        int v = adj->val;
        if (!visited[v]) {
            DFS(graph, v, visited);
        }
        adj = adj->next;
    }
}

void DFS(Graph* graph, int start) {
    bool* visited = new bool[graph->V];
    for (int i = 0; i < graph->V; i++) {
        visited[i] = false;
    }
    DFS(graph, start, visited);
    std::cout << std::endl;
    delete[] visited;
}

完整代码如下：

#include <iostream>
#include <queue>

class Node {
public:
    int val;
    Node* next;
    Node(int v) : val(v), next(nullptr) {}
};

class Graph {
public:
    int V;
    Node** adjList;
    Graph(int v) : V(v) {
        adjList = new Node*[V];
        for (int i = 0; i < V; i++) {
            adjList[i] = nullptr;
        }
    }
    ~Graph() {
        for (int i = 0; i < V; i++) {
            Node* cur = adjList[i];
            while (cur) {
                Node* next = cur->next;
                delete cur;
                cur = next;
            }
        }
        delete[] adjList;
    }
    void addEdge(int src, int dest) {
        Node* newNode = new Node(dest);
        newNode->next = adjList[src];
        adjList[src] = newNode;
    }
};

void BFS(Graph* graph, int start) {
    bool* visited = new bool[graph->V];
    for (int i = 0; i < graph->V; i++) {
        visited[i] = false;
    }
    std::queue<int> q;
    visited[start] = true;
    q.push(start);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        std::cout << cur << " ";
        Node* adj = graph->adjList[cur];
        while (adj) {
            int v = adj->val;
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
            adj = adj->next;
        }
    }
    std::cout << std::endl;
    delete[] visited;
}

void DFS(Graph* graph, int cur, bool* visited) {
    visited[cur] = true;
    std::cout << cur << " ";
    Node* adj = graph->adjList[cur];
    while (adj) {
        int v = adj->val;
        if (!visited[v]) {
            DFS(graph, v, visited);
        }
        adj = adj->next;
    }
}

void DFS(Graph* graph, int start) {
    bool* visited = new bool[graph->V];
    for (int i = 0; i < graph->V; i++) {
        visited[i] = false;
    }
    DFS(graph, start, visited);
    std::cout << std::endl;
    delete[] visited;
}

int main() {
    Graph* graph = new Graph(4);
    graph->addEdge(0, 1);
    graph->addEdge(0, 2);
    graph->addEdge(1, 2);
    graph->addEdge(2, 0);
    graph->addEdge(2, 3);
    graph->addEdge(3, 3);
    std::cout << "BFS: ";
    BFS(graph, 2);
    std::cout << "DFS: ";
    DFS(graph, 2);
    delete graph;
    return 0;
}