数据结构之邻接表

数据结构之邻接表

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

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

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

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

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

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

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

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

  #include #include #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 vexnum; i++) {        scanf("%d", &(G->vertex[i].data));        G->vertex[i].firstarc = NULL;    }    getchar();    printf("请输入各边的顶点序号（如：3 5）：\n");    for (int i = 0; i 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 adjvex].data);            p = p->next;        }        printf("\n");    }}// 主函数int main() {    Graph G;    CreateGraph(&G);    PrintGraph(G);    return 0;}

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

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

  #include #include using namespace std;// 邻接表中每个节点的结构体struct Node {    int val; // 存储顶点的值    Node* next; // 指向下一个节点};// 邻接表类class AdjacencyList {private:    vector 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