图的邻接表实现代解析【数据结构】

引言

在图论中，图是一种重要的数据结构，用于表示对象之间的关系。邻接表是一种常用的图的存储方式，它通过链表来表示图中顶点之间的连接关系。本文将详细解析一段使用 C++ 实现的图的邻接表代码，帮助读者理解其实现原理和使用方法。

代码实现

1. 头文件和宏定义

#include<iostream>
#define N 105

using namespace std;

• #include<iostream>：引入标准输入输出流库，用于程序中的输入输出操作。
• #define N 105：定义一个宏 N，表示图中顶点的最大数量为 105。
• using namespace std;：使用标准命名空间，方便后续使用标准库中的函数和对象。

2. 结构体定义

typedef struct node {
    int date;
    struct node* next;
}edg;

typedef struct nodea {
    char date;
    edg* firstedg;
}vhead;

typedef struct {
    vhead adj[N];//存点
    int n, m;//点数，边数
}Adj;

• edg 结构体：表示图中的边节点，包含一个整数 date 用于存储边所指向的顶点编号，以及一个指向下一个边节点的指针 next。
• vhead 结构体：表示图中的顶点节点，包含一个字符 date 用于存储顶点的数据，以及一个指向该顶点第一条边的指针 firstedg。
• Adj 结构体：表示整个图，包含一个 vhead 类型的数组 adj 用于存储所有顶点，以及两个整数 n 和 m 分别表示图的顶点数和边数。

3. 图的创建函数 creatTu

void creatTu(Adj* g, int st)//图，是否为双向图
{
    edg* p;
    if (!st) cout << "无向图\n";
    else cout << "有向图\n";
    cin >> g->n;
    for (int i = 1; i <= g->n; i++){
        cin >> g->adj[i].date;//点
        g->adj[i].firstedg = NULL;
    }
    cin >>g-> m;
    for(int k=0;k<g->m;k++)
    {
        int i, j;
        cin >> i >> j;//建立i->j;
        p = (edg*)malloc(sizeof(edg));
        p->date = j;
        p->next=g->adj[i].firstedg;
        g->adj[i].firstedg = p;
        if (st)
        {
            p = (edg*)malloc(sizeof(edg));
            swap(i, j);
            p->date = j;
            p->next = g->adj[i].firstedg;
            g->adj[i].firstedg = p;
        }
    }
}

• 该函数接受一个指向 Adj 结构体的指针 g 和一个整数 st，用于判断图是否为双向图。
• 首先根据 st 的值输出图的类型信息。
• 然后读取图的顶点数 g->n，并依次读取每个顶点的数据，同时将每个顶点的第一条边指针初始化为 NULL。
• 接着读取图的边数 g->m，并循环读取每条边的起点 i 和终点 j。
• 对于每条边，创建一个新的边节点 p，将其 date 设为 j，并将其插入到起点 i 的邻接表头部。
• 如果图是双向图（st 为真），则交换 i 和 j，再创建一个新的边节点并插入到 i 的邻接表头部。

4. 图的打印函数 print

void print(Adj* g)
{
    edg* p;
    for (int i = 1; i <= g->n; i++){
        cout << g->adj[i].date<<" ";
        p = g->adj[i].firstedg;
        while (p != NULL){
            //cout << "66";
            cout << g->adj[p->date].date<<" ";
            p = p->next;
        }
        cout << endl;
    }
}

• 该函数接受一个指向 Adj 结构体的指针 g，用于打印图的邻接表。
• 遍历每个顶点，先输出该顶点的数据，然后遍历该顶点的邻接表，依次输出每个邻接顶点的数据。

5. 主函数 main

int main() {
    Adj* T = (Adj*)malloc(sizeof(Adj));
    creatTu(T, 0);
    print(T);
    return 0;
}
input:
3
a b c
4
1 2
1 3
2 3
3 2
运行结果如下：

• 在主函数中，首先使用 malloc 动态分配一个 Adj 结构体的内存空间，并将其指针赋值给 T。
• 然后调用 creatTu 函数创建一个无向图（st 为 0）。
• 最后调用 print 函数打印图的邻接表。

总结

通过这段代码，我们可以看到如何使用邻接表来存储和表示图的结构。邻接表的优点是空间效率高，适合存储稀疏图。同时，我们也应该注意代码中的一些潜在问题，如拼写错误、数组越界和内存管理等，以确保代码的正确性和健壮性。

希望本文的解析能够帮助读者更好地理解图的邻接表实现，同时也为读者在实际应用中使用图数据结构提供一些参考。