C语言如何创建邻接表

C语言如何创建邻接表

C语言创建邻接表的方法包括：定义数据结构、初始化邻接表、添加边、遍历邻接表。在本文中，我们将详细探讨如何使用C语言创建和操作邻接表，并深入讨论每个步骤的具体实现和注意事项。

一、定义数据结构

在C语言中，创建邻接表需要定义适当的数据结构。通常使用链表来表示每个顶点的邻接点列表。下面是定义数据结构的步骤：

1.1 定义节点结构

首先，我们需要定义一个结构体来表示链表中的节点。这个结构体包含两个部分：一个是顶点的编号，另一个是指向下一个节点的指针。

typedef struct AdjListNode {
    int dest;
    struct AdjListNode* next;
} AdjListNode;

1.2 定义邻接表结构

接下来，我们需要定义一个结构体来表示邻接表。这个结构体包含一个指针数组，其中每个指针指向一个链表的头节点。

typedef struct AdjList {
    AdjListNode* head;
} AdjList;

1.3 定义图结构

最后，我们定义一个结构体来表示图。这个结构体包含顶点的数量和一个邻接表数组。

typedef struct Graph {
    int V;
    AdjList* array;
} Graph;

二、初始化邻接表

在定义了数据结构之后，我们需要编写函数来初始化邻接表。

2.1 创建节点

首先，我们需要一个函数来创建新的节点。

AdjListNode* newAdjListNode(int dest) {
    AdjListNode* newNode = (AdjListNode*) malloc(sizeof(AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

2.2 创建图

接下来，我们需要一个函数来创建图并初始化邻接表。

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

三、添加边

在初始化邻接表之后，我们需要编写函数来向图中添加边。

3.1 添加有向边

对于有向图，我们只需要在一个方向上添加边。

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

3.2 添加无向边

对于无向图，我们需要在两个方向上都添加边。

void addUndirectedEdge(Graph* graph, int src, int dest) {
    addEdge(graph, src, dest);
    addEdge(graph, dest, src);
}

四、遍历邻接表

为了验证我们的邻接表是否正确，我们需要编写一个函数来遍历邻接表并打印每个顶点的邻接点。

4.1 打印图

下面的函数遍历图并打印每个顶点的邻接点列表。

void printGraph(Graph* graph) {
    for (int v = 0; v < graph->V; ++v) {
        AdjListNode* pCrawl = graph->array[v].head;
        printf("\n Adjacency list of vertex %d\n head ", v);
        while (pCrawl) {
            printf("-> %d", pCrawl->dest);
            pCrawl = pCrawl->next;
        }
        printf("\n");
    }
}

五、应用实例

为了更好地理解如何使用上述函数，我们来看一个具体的例子。

5.1 示例代码

下面是一个完整的示例代码，它创建一个图，添加一些边，并打印邻接表。

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

typedef struct AdjListNode {
    int dest;
    struct AdjListNode* next;
} AdjListNode;

typedef struct AdjList {
    AdjListNode* head;
} AdjList;

typedef struct Graph {
    int V;
    AdjList* array;
} Graph;

AdjListNode* newAdjListNode(int dest) {
    AdjListNode* newNode = (AdjListNode*) malloc(sizeof(AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

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

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

void addUndirectedEdge(Graph* graph, int src, int dest) {
    addEdge(graph, src, dest);
    addEdge(graph, dest, src);
}

void printGraph(Graph* graph) {
    for (int v = 0; v < graph->V; ++v) {
        AdjListNode* pCrawl = graph->array[v].head;
        printf("\n Adjacency list of vertex %d\n head ", v);
        while (pCrawl) {
            printf("-> %d", pCrawl->dest);
            pCrawl = pCrawl->next;
        }
        printf("\n");
    }
}

int main() {
    int V = 5;
    Graph* graph = createGraph(V);
    addUndirectedEdge(graph, 0, 1);
    addUndirectedEdge(graph, 0, 4);
    addUndirectedEdge(graph, 1, 2);
    addUndirectedEdge(graph, 1, 3);
    addUndirectedEdge(graph, 1, 4);
    addUndirectedEdge(graph, 2, 3);
    addUndirectedEdge(graph, 3, 4);
    printGraph(graph);
    return 0;
}

5.2 运行结果

运行上述代码，输出如下：

 Adjacency list of vertex 0
 head -> 4 -> 1
 Adjacency list of vertex 1
 head -> 4 -> 3 -> 2 -> 0
 Adjacency list of vertex 2
 head -> 3 -> 1
 Adjacency list of vertex 3
 head -> 4 -> 2 -> 1
 Adjacency list of vertex 4
 head -> 3 -> 1 -> 0

六、总结

通过本文，我们详细探讨了如何在C语言中创建邻接表。我们首先定义了数据结构，然后编写了初始化、添加边和遍历邻接表的函数，最后通过一个具体的示例展示了如何使用这些函数。邻接表是一种高效的图表示方式，适用于稀疏图的表示和处理。希望本文能够帮助你更好地理解和应用邻接表。