邻接表的深度和优先广度优先遍历实现c++

邻接表是一种图的表示方法，可以用于图的深度优先遍历和广度优先遍历。下面是邻接表的深度优先遍历和广度优先遍历的实现代码。

假设我们要遍历的图的邻接表如下：

struct GraphNode {
    int value;
    struct GraphNode* next;
};

struct Graph {
    int vertices;
    struct GraphNode** adjList;
};

其中，`Graph.vertices` 表示图中顶点的数量，`Graph.adjList` 是一个数组，每个元素是一个指向 `GraphNode` 的指针，表示该顶点的邻接表。

接下来是深度优先遍历的实现代码：

void dfs(struct Graph* graph, int vertex, bool* visited) {
    visited[vertex] = true;
    printf("%d ", vertex);

    struct GraphNode* adjNode = graph->adjList[vertex];
    while (adjNode != NULL) {
        int adjVertex = adjNode->value;
        if (!visited[adjVertex]) {
            dfs(graph, adjVertex, visited);
        }
        adjNode = adjNode->next;
    }
}

void dfsTraversal(struct Graph* graph, int startVertex) {
    bool visited[graph->vertices];
    memset(visited, false, sizeof(visited));

    dfs(graph, startVertex, visited);
}

其中，`dfs` 函数表示深度优先遍历，`dfsTraversal` 函数表示整个图的深度优先遍历。`visited` 数组用于判断顶点是否已经被访问过。

接下来是广度优先遍历的实现代码：

void bfsTraversal(struct Graph* graph, int startVertex) {
    bool visited[graph->vertices];
    memset(visited, false, sizeof(visited));

    struct Queue* queue = createQueue();
    visited[startVertex] = true;
    enqueue(queue, startVertex);

    while (!isEmpty(queue)) {
        int vertex = dequeue(queue);
        printf("%d ", vertex);

        struct GraphNode* adjNode = graph->adjList[vertex];
        while (adjNode != NULL) {
            int adjVertex = adjNode->value;
            if (!visited[adjVertex]) {
                visited[adjVertex] = true;
                enqueue(queue, adjVertex);
            }
            adjNode = adjNode->next;
        }
    }
}

其中，`bfsTraversal` 函数表示整个图的广度优先遍历。`visited` 数组用于判断顶点是否已经被访问过，`Queue` 是一个队列，用于存储待访问的顶点。在遍历过程中，每访问一个顶点，就将其未被访问的邻接点加入到队列中，并将其标记为已访问。