引言
在图论中，图是一种重要的数据结构，用于表示对象之间的关系。邻接表是一种常用的图的存储方式，它通过链表来表示图中顶点之间的连接关系。本文将详细解析一段使用 C++ 实现的图的邻接表代码，帮助读者理解其实现原理和使用方法。
代码实现
1. 头文件和宏定义
#include<iostream>
#define N 105using 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函数打印图的邻接表。
总结
通过这段代码，我们可以看到如何使用邻接表来存储和表示图的结构。邻接表的优点是空间效率高，适合存储稀疏图。同时，我们也应该注意代码中的一些潜在问题，如拼写错误、数组越界和内存管理等，以确保代码的正确性和健壮性。
希望本文的解析能够帮助读者更好地理解图的邻接表实现，同时也为读者在实际应用中使用图数据结构提供一些参考。
