数据结构之邻接表

数据结构之邻接表

• 一、C 语言实现邻接表及源码详解
• 二、C++ 语言实现邻接表及源码详解
• 三、Java 语言实现邻接表及源码详解

邻接表是一种表示图的数据结构，它通过链表的形式，将每个节点的邻居节点记录下来。具体原理如下：

1. 对于每个节点，我们创建一个链表。链表中存储该节点所连接的所有边的信息。

2. 对于每条边，我们在两个节点之间的链表中分别存储该边的信息。例如，如果节点A和节点B之间有一条边，我们会在节点A的链表中存储一条指向节点B的边，同时在节点B的链表中存储一条指向节点A的边。

3. 通过邻接表，我们可以轻松地获取任意节点的邻居节点列表。只需访问该节点的链表即可。同时，我们也可以方便地实现图的遍历和搜索算法，如深度优先搜索和广度优先搜索。

邻接表相对于邻接矩阵，可以更好地处理稀疏图（即边数相对于节点数很小的图），因为邻接矩阵需要存储所有节点之间的连通情况，当图的边数远小于节点数时，会浪费很多空间。

一、C 语言实现邻接表及源码详解

邻接表是一种常用的图的表示方法，可以用来存储无向图和有向图。C语言可以通过结构体和指针来实现邻接表，以下是一个简单的示例代码：

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

#define MAX_VERTEX_NUM 20

// 边表结点
typedef struct ArcNode {
    int adjvex;  // 该边所指向的顶点的位置
    struct ArcNode *next;  // 指向下一条边的指针
} ArcNode;

// 顶点表结点
typedef struct VertexNode {
    int data;  // 顶点的数据
    ArcNode *firstarc;  // 指向第一条边的指针
} VertexNode;

// 邻接表结构
typedef struct {
    VertexNode vertex[MAX_VERTEX_NUM];  // 顶点表
    int vexnum;                         // 顶点数
    int arcnum;                         // 边数
} Graph;

// 创建邻接表
void CreateGraph(Graph *G) {
    printf("请输入顶点数和边数：");
    scanf("%d %d", &(G->vexnum), &(G->arcnum));
    getchar();

    printf("请输入各顶点的值：");
    for (int i = 0; i < G->vexnum; i++) {
        scanf("%d", &(G->vertex[i].data));
        G->vertex[i].firstarc = NULL;
    }
    getchar();

    printf("请输入各边的顶点序号（如：3 5）：\n");
    for (int i = 0; i < G->arcnum; i++) {
        int v1, v2;
        scanf("%d %d", &v1, &v2);
        ArcNode *arc1 = (ArcNode *)malloc(sizeof(ArcNode));
        arc1->adjvex = v2;
        arc1->next = G->vertex[v1].firstarc;
        G->vertex[v1].firstarc = arc1;

        ArcNode *arc2 = (ArcNode *)malloc(sizeof(ArcNode));
        arc2->adjvex = v1;
        arc2->next = G->vertex[v2].firstarc;
        G->vertex[v2].firstarc = arc2;
    }
}

// 打印邻接表
void PrintGraph(Graph G) {
    printf("打印邻接表：\n");
    for (int i = 0; i < G.vexnum; i++) {
        printf("%d：", G.vertex[i].data);
        ArcNode *p = G.vertex[i].firstarc;
        while (p) {
            printf("%d ", G.vertex[p->adjvex].data);
            p = p->next;
        }
        printf("\n");
    }
}

// 主函数
int main() {
    Graph G;
    CreateGraph(&G);
    PrintGraph(G);
    return 0;
}

以上代码实现了邻接表的创建和打印，其中结构体 ArcNode 表示边表结点， VertexNode 表示顶点表结点， Graph 表示邻接表结构体。在 CreateGraph 函数中，通过循环输入各顶点的值和边的顶点序号，并利用指针连接边表和顶点表，最终构造出邻接表。在 PrintGraph 函数中，循环打印出每个顶点对应的边表。

二、C++ 语言实现邻接表及源码详解

邻接表是一种用于表示图的数据结构，它使用链表来表示每个顶点连接的边。C++语言中可以使用结构体和指针来实现邻接表，下面是一个简单的实现示例：

#include <iostream>
#include <vector>

using namespace std;

// 邻接表中每个节点的结构体
struct Node {
    int val; // 存储顶点的值
    Node* next; // 指向下一个节点
};

// 邻接表类
class AdjacencyList {
private:
    vector<Node*> graph; // 存储邻接表
public:
    AdjacencyList(int n) {
        graph.resize(n, nullptr); // 初始化邻接表
    }

    // 插入一条边
    void addEdge(int u, int v) {
        Node* node = new Node();
        node->val = v;
        node->next = graph[u];
        graph[u] = node;
    }

    // 打印邻接表
    void print() {
        for (int i = 0; i < graph.size(); i++) {
            Node* node = graph[i];
            cout << i << "->";
            while (node != nullptr) {
                cout << node->val << "->";
                node = node->next;
            }
            cout << "null" << endl;
        }
    }
};

int main() {
    AdjacencyList graph(5);
    graph.addEdge(0, 1);
    graph.addEdge(0, 4);
    graph.addEdge(1, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);
    graph.print();
    return 0;
}

在这个实现中，我们定义了一个Node结构体，表示邻接表中的一个节点，包含该顶点的值val和指向下一个节点的指针next。我们还定义了AdjacencyList类来表示整个邻接表，其中使用一个vector数组来存储每个顶点的链表。

在addEdge函数中，我们通过创建一个新的节点，将其插入到u节点的链表头部，表示u和v之间存在一条边。

在print函数中，我们遍历整个邻接表，对于每个顶点，遍历其链表并输出相邻的顶点。

三、Java 语言实现邻接表及源码详解

邻接表是一种表示图的数据结构，它将每个节点的相邻节点存储为一个链表。在 Java 中，我们可以使用集合和链表来实现邻接表。

以下是 Java 实现邻接表的代码：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class AdjacencyList {
    private List<List<Integer>> adjacencyList;

    public AdjacencyList(int numberOfNodes) {
        adjacencyList = new ArrayList<>(numberOfNodes);
        for (int i = 0; i < numberOfNodes; i++) {
            adjacencyList.add(new LinkedList<>());
        }
    }

    public void addEdge(int source, int destination) {
        List<Integer> sourceList = adjacencyList.get(source);
        sourceList.add(destination);

        List<Integer> destinationList = adjacencyList.get(destination);
        destinationList.add(source);
    }

    public List<Integer> getAdjacentNodes(int node) {
        return adjacencyList.get(node);
    }
}

在这个实现中，我们使用了一个 List 嵌套 List 的数据结构。从行的角度来看，我们将每个节点储存在主列表中。从列的角度来看，我们将每个节点的相邻节点储存在该节点的子列表中。

在构造函数中，我们初始化主列表，使其包含指定数量的节点，并为每个节点创建一个空子列表。在 addEdge() 方法中，我们将一条边添加到邻接表中。具体来说，我们将目标节点添加到源节点的子列表中，并将源节点添加到目标节点的子列表中。这个步骤是必需的，因为图是无向的，所以每条边都可以双向通行。

最后，在 getAdjacentNodes() 方法中，我们返回指定节点的子列表，它包含了该节点的所有相邻节点。

邻接表有许多用途，例如在图遍历算法中，它可以帮助我们查找每个节点的相邻节点。它还可以用于表示稀疏的图，因为它只存储相邻节点，而不是所有节点的组合。