图的邻接表表示法及遍历c语言代码实现

邻接表是一种常用的图的表示方法，它将每个顶点的出边存储为一个链表，因此可以节省空间。下面是邻接表的C语言实现代码：

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

// 定义邻接表结点
typedef struct ListNode {
    int vertex;             // 邻接点下标
    struct ListNode* next;  // 指向下一个邻接点的指针
} ListNode;

// 定义邻接表
typedef struct AdjList {
    int numVertices;        // 顶点数
    ListNode** adjLists;    // 指向邻接表头结点的指针数组
} AdjList;

// 创建邻接表结点
ListNode* createListNode(int v) {
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    node->vertex = v;
    node->next = NULL;
    return node;
}

// 创建邻接表
AdjList* createAdjList(int numVertices) {
    AdjList* adjList = (AdjList*)malloc(sizeof(AdjList));
    adjList->numVertices = numVertices;
    adjList->adjLists = (ListNode**)malloc(numVertices * sizeof(ListNode*));
    for (int i = 0; i < numVertices; i++) {
        adjList->adjLists[i] = NULL;
    }
    return adjList;
}

// 添加边
void addEdge(AdjList* adjList, int src, int dest) {
    // 添加从src到dest的边
    ListNode* node = createListNode(dest);
    node->next = adjList->adjLists[src];
    adjList->adjLists[src] = node;
    // 添加从dest到src的边（如果是无向图）
    /*ListNode* node1 = createListNode(src);
    node1->next = adjList->adjLists[dest];
    adjList->adjLists[dest] = node1;*/
}

// 遍历邻接表
void printGraph(AdjList* adjList) {
    for (int i = 0; i < adjList->numVertices; i++) {
        ListNode* node = adjList->adjLists[i];
        printf("Vertex %d: ", i);
        while (node != NULL) {
            printf("%d -> ", node->vertex);
            node = node->next;
        }
        printf("NULL\n");
    }
}

// 深度优先遍历
void dfs(AdjList* adjList, int v, int* visited) {
    visited[v] = 1;
    printf("%d ", v);
    ListNode* node = adjList->adjLists[v];
    while (node != NULL) {
        int adjVertex = node->vertex;
        if (!visited[adjVertex]) {
            dfs(adjList, adjVertex, visited);
        }
        node = node->next;
    }
}

// 广度优先遍历
void bfs(AdjList* adjList, int startVertex, int* visited) {
    int queue[adjList->numVertices];
    int front = -1, rear = -1;

    visited[startVertex] = 1;
    queue[++rear] = startVertex;

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

        ListNode* node = adjList->adjLists[currentVertex];
        while (node != NULL) {
            int adjVertex = node->vertex;
            if (!visited[adjVertex]) {
                visited[adjVertex] = 1;
                queue[++rear] = adjVertex;
            }
            node = node->next;
        }
    }
}

int main() {
    // 创建邻接表
    AdjList* adjList = createAdjList(5);

    // 添加边
    addEdge(adjList, 0, 1);
    addEdge(adjList, 0, 4);
    addEdge(adjList, 1, 2);
    addEdge(adjList, 1, 3);
    addEdge(adjList, 1, 4);
    addEdge(adjList, 2, 3);
    addEdge(adjList, 3, 4);

    // 输出邻接表
    printGraph(adjList);

    // 深度优先遍历
    printf("DFS: ");
    int visited[5] = { 0 };
    dfs(adjList, 0, visited);
    printf("\n");

    // 广度优先遍历
    printf("BFS: ");
    int visited1[5] = { 0 };
    bfs(adjList, 0, visited1);
    printf("\n");

    return 0;
}

在这个示例代码中，我们创建了一个包含5个顶点的邻接表，并添加了一些边。然后我们遍历这个邻接表，实现了深度优先遍历和广度优先遍历。