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

邻接表是一种图的表示方法，其中每个节点都与其相邻的节点列表相关联。深度优先遍历和广度优先遍历是两种常见的图遍历算法。

以下是使用邻接表表示图，并实现深度优先遍历和广度优先遍历的C代码：

#include <stdio.h>
#include <stdlib.h>

// 邻接表节点
struct AdjListNode {
    int dest;
    struct AdjListNode* next;
};

// 邻接表
struct AdjList {
    struct AdjListNode* head;
};

// 图
struct Graph {
    int V;
    struct AdjList* array;
};

// 创建节点
struct AdjListNode* newAdjListNode(int dest) {
    struct AdjListNode* newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// 创建图
struct Graph* createGraph(int V) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->V = V;
    graph->array = (struct AdjList*)malloc(V * sizeof(struct AdjList));
    for (int i = 0; i < V; ++i) {
        graph->array[i].head = NULL;
    }
    return graph;
}

// 添加边
void addEdge(struct Graph* graph, int src, int dest) {
    struct AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// 深度优先遍历
void DFS(struct Graph* graph, int v, int visited[]) {
    visited[v] = 1;
    printf("%d ", v);

    struct AdjListNode* node = graph->array[v].head;
    while (node != NULL) {
        if (!visited[node->dest]) {
            DFS(graph, node->dest, visited);
        }
        node = node->next;
    }
}

// 广度优先遍历
void BFS(struct Graph* graph, int v, int visited[]) {
    int queue[graph->V], front = 0, rear = 0;
    visited[v] = 1;
    queue[rear++] = v;

    while (front != rear) {
        v = queue[front++];
        printf("%d ", v);

        struct AdjListNode* node = graph->array[v].head;
        while (node != NULL) {
            if (!visited[node->dest]) {
                visited[node->dest] = 1;
                queue[rear++] = node->dest;
            }
            node = node->next;
        }
    }
}

// 测试
int main() {
    int V = 5;
    struct Graph* graph = createGraph(V);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    int visited[V];
    for (int i = 0; i < V; ++i) {
        visited[i] = 0;
    }

    printf("深度优先遍历: ");
    DFS(graph, 0, visited);

    for (int i = 0; i < V; ++i) {
        visited[i] = 0;
    }

    printf("\n广度优先遍历: ");
    BFS(graph, 0, visited);

    return 0;
}

在上面的代码中，我们首先定义了一个邻接表节点 `AdjListNode`，其中包含了节点的 `dest` 和 `next`。然后定义了邻接表 `AdjList` 和图 `Graph`，其中邻接表包含了头节点指针 `head`，图包含了节点数 `V` 和邻接表数组 `array`。

在创建图时，我们首先分配内存给图和邻接表数组，然后将每个邻接表的头节点指针初始化为 `NULL`。

在添加边时，我们首先创建一个新的邻接表节点，然后将其添加到源节点的邻接表中，同时将其添加到目标节点的邻接表中。

在深度优先遍历时，我们首先将当前节点标记为已访问，然后遍历与其相邻的节点列表，如果该节点未被访问，则递归访问该节点。这个过程类似于树的深度优先遍历。

在广度优先遍历时，我们首先将当前节点标记为已访问，然后将其添加到队列中。然后我们从队列中取出队首元素，并遍历其相邻节点，如果该节点未被访问，则将其添加到队列中。这个过程类似于树的广度优先遍历。

在测试代码中，我们首先创建一个具有5个节点的图，并添加了6条边。然后分别进行深度优先遍历和广度优先遍历，并输出结果。