ToB企服应用市场:ToB评测及商务社交产业平台

标题: 图的邻接表实现代解析【数据结构】 [打印本页]

---

作者: 饭宝    时间: 2025-2-17 09:07
标题: 图的邻接表实现代解析【数据结构】
引言

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

1. 头文件和宏界说

1. #include<iostream>
2. #define N 105
4. using namespace std;

复制代码

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

2. 结构体界说

1. typedef struct node {
2.     int date;
3.     struct node* next;
4. }edg;
6. typedef struct nodea {
7.     char date;
8.     edg* firstedg;
9. }vhead;
11. typedef struct {
12.     vhead adj[N];//存点
13.     int n, m;//点数，边数
14. }Adj;

复制代码

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

3. 图的创建函数 creatTu

1. void creatTu(Adj* g, int st)//图，是否为双向图
2. {
3.     edg* p;
4.     if (!st) cout << "无向图\n";
5.     else cout << "有向图\n";
6.     cin >> g->n;
7.     for (int i = 1; i <= g->n; i++){
8.         cin >> g->adj[i].date;//点
9.         g->adj[i].firstedg = NULL;
10.     }
11.     cin >>g-> m;
12.     for(int k=0;k<g->m;k++)
13.     {
14.         int i, j;
15.         cin >> i >> j;//建立i->j;
16.         p = (edg*)malloc(sizeof(edg));
17.         p->date = j;
18.         p->next=g->adj[i].firstedg;
19.         g->adj[i].firstedg = p;
20.         if (st)
21.         {
22.             p = (edg*)malloc(sizeof(edg));
23.             swap(i, j);
24.             p->date = j;
25.             p->next = g->adj[i].firstedg;
26.             g->adj[i].firstedg = p;
27.         }
28.     }
29. }

复制代码

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

4. 图的打印函数 print

1. void print(Adj* g)
2. {
3.     edg* p;
4.     for (int i = 1; i <= g->n; i++){
5.         cout << g->adj[i].date<<" ";
6.         p = g->adj[i].firstedg;
7.         while (p != NULL){
8.             //cout << "66";
9.             cout << g->adj[p->date].date<<" ";
10.             p = p->next;
11.         }
12.         cout << endl;
13.     }
14. }

复制代码

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

5. 主函数 main

1. int main() {
2.     Adj* T = (Adj*)malloc(sizeof(Adj));
3.     creatTu(T, 0);
4.     print(T);
5.     return 0;
6. }
7. input:
8. 3
9. a b c
10. 4
11. 1 2
12. 1 3
13. 2 3
14. 3 2
15. 运行结果如下：

复制代码

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

总结

通过这段代码，我们可以看到如何使用邻接表来存储和表示图的结构。邻接表的优点是空间效率高，适合存储稀疏图。同时，我们也应该注意代码中的一些潜伏问题，如拼写错误、数组越界和内存管理等，以确保代码的精确性和健壮性。
希望本文的解析能够资助读者更好地明白图的邻接表实现，同时也为读者在现实应用中使用图数据结构提供一些参考。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4