3.2 图的邻接表表示和实现

本节将介绍如何使用邻接表表示图的原理，并通过C语言和汇编语言实现邻接表的建立，最后在1B硬件开发平台上对设计进行调试。

3.2.1 图的邻接表表示方法

图是一种数据结构，由节点和边两部分组成。需要注意，在有向图中，边是有方向的，即（ u , v ）和（ v , u ）并不相同。在有向图中，（ u , v ）表示节点 u 到节点 v 的边，而（ v , u ）表示节点 v 到节点 u 的边。显然，这种表示具有方向性。此外，这个边可能包含权重、值和距离等信息。

在现实生活中，图有很多代表性的应用。例如，图经常被用来表示网络，如城市之间的道路交通网、电话网或电网。此外，图也经常用于微信和QQ等社交网络，如在微信中用一个节点来表示一个人，每个节点都是包含身份证号、名字、性别，以及其家庭住址的结构体。

图3.8为包含5个节点的无向图。一般使用邻接矩阵和邻接列表来表示图的结构。当然，也可以使用其他的表示方式，如入射矩阵和入射列表。选择何种表示方式要根据具体情况决定，这完全取决于图的用途和要执行的操作类型。

1.邻接矩阵

假设图中共有 V 个节点，那么邻接矩阵就是一个大小为 V × V 的二维数组。如果用数组adj［］［］表示该二维数组，则数组中的元素adj［ i ］［ j ］=1就表示存在一条从节点 i 到节点 j 的边。显然，用邻接矩阵表示无向图始终是对称的。如果数据中的元素adj［ i ］［ j ］= w ，则表示从节点 i 到节点 j 的路径权重为 w 。

用下面的邻接矩阵来表示图3.8中给出的无向图，即

采用邻接矩阵的表示方法具有容易实现和遍历的优点。当删除一条边时，只需要花费一个单位的时间，时间复杂度为 O (1)。此外，当查询从节点 u 到节点 v 是否存在路径的效率也非常高，也只需要花费一个单位的时间，时间复杂度为 O (1)。

但是采用邻接矩阵的方法也有其缺点，即邻接矩阵要消耗更多的存储空间。对于 V 个节点的图，则需要个 V ² 个存储空间，空间复杂度为 O （ V ² ）。显然，即使这个图很分散（节点之间的边很少），但也还是需要 V ² 个存储空间。此外，构建这个邻接矩阵（添加节点）也需要消耗 V ² 个单位时间，时间复杂度为 O （ V ² ）。

2.邻接表

邻接表是一个列表数组，该数组是一个大小等于节点数的一维数组。数组array［ i ］中存放的是一个链表，该链表中的 n 个数据表示的就是连接到第 i 个节点的 n 个节点。邻接表也可以用来表示加权图，边的权重可以用一对列表来表示。对于图3.8给出的图，用邻接表表示的方法如图3.9所示。

从图3.9可知，节点0分别连接节点1和节点4，节点1分别连接节点0、节点4、节点2和节点3，节点2分别连接节点1和节点3，节点3分别连接节点1、节点4和节点2，节点4分别连接节点3、节点0和节点1。

对于一个图，应该如何恰当地选择邻接矩阵和邻接表呢？表3.1给出了一些可参考的规则。

3.2.2 基于链表的邻接表设计思路

本节将详细介绍如何使用C语言实现邻接表的思路。

1.构建邻接表存储类型

构建邻接表存储类型的主要步骤如下所示。

（1）用结构体graph表示图。其中，graph结构体中包含两部分信息，即图的节点数和链表数组array［ i ］。其中，array［ i ］对应的就是第 i 个节点的邻接表，从array［0］到array［ V -1］组成的整体就是整个图的邻接表， V 为第 V 个节点的数字编号。

（2）观察表示邻接表的结构体graph->array［ i ］，该结构体中只包含一个指向节点的指针，称为“头指针”（本质上是链表中第一个节点的存储地址）。

（3）观察表示邻接表节点的结构体。由于邻接表是以链表形式存储的，因此每个节点结构体都包含两部分内容，即当前节点的值（dest）与下一个节点的存储位置（next）。

2.构建图

构建图的主要步骤如下所示。

（1）声明图中有 V 个节点，根据节点的个数 V 用createGraph函数构建一个空的图。

① 声明graph是指向图结构体的指针，对该指针指向的地址分配空间，大小是(struct Graph)的一个单元，并强制类型转换，graph-> V = V ，对节点数赋值。

② 在图结构体中已经声明array是指向邻接表结构体的指针，因此不用再次声明，对该指针指向的地址分配空间，大小是（struct AdjList）的 V 个单元，并强制类型转换。

③ 将每个graph->array［ i ］.head赋值为空，表示各个链表中均无节点，当前邻接表为空。

（2）通过addEdge()函数为创建的图添加边（向邻接表中添加节点），该函数传入参数为两个整型数据“源节点”（src）与“目标节点”（dest）。

① 创建一个空节点（check）检验链表末尾，找到合适的节点插入位置。

② 由于传入的dest并不是节点而是整型数据，所以要先用dest的值构建一个新的节点（newNode）来插入链表。

③ 如果源节点src对应的链表头为空，那么就将目标节点直接放在该链表的第一个（头指针指向该新节点，新节点的下一个节点为空），否则用check查找该链表的最后一个节点，并将新节点挂在之后。

④ 由于是无向图，节点之间的连接是双向的，因此将原来的源节点（src）当作目标节点，将原来的目标节点（dest）当作源节点，继续一次步骤③的操作。

3.无向图的遍历

无向图的遍历较为简单，具体步骤如下所示。

（1）输出某源节点，访问该源节点对应的链表，依次打印链表中的节点直至结束即可。

（2）换下一个源节点，重复步骤（1），等到遍历完所有的源节点为止。

3.2.3 C语言程序设计-邻接表的链表实现

基于链表结构构建邻接表的C语言代码如代码清单3-6所示。

注 ：读者可以定位到本书提供资源的\loongson1B_training_example\example_3_3目录中，使用LoongIDE软件工具打开example_3_3.lxp工程文件。

3.2.4 C语言编译和调试-邻接表的链表实现

本节将介绍如何对设计工程进行编译，并将设计下载到龙芯1B开发板进行验证。具体实现步骤如下所示。

（1）编译程序代码，并给龙芯1B硬件开发平台上电。

（2）启动并配置PuTTY（64-bit）软件工具。

（3）在LoongIDE主界面主菜单下，选择Debug->Run，进入调试器模式，开始运行程序，在PuTTY命令行界面中即可打印出建立的邻接表信息，如图3.10所示。

3.2.5 基于数组的邻接表设计思路

在代码清单3-6给出的C语言代码中，包含动态分配内存空间的函数malloc()。由于使用该函数会对基于汇编语言构建邻接表造成困难。因此，在分析代码中链表存储结构的基础上，使用数组代替链表实现相同操作。这种修改有如下要求：

（1）要删除函数malloc()与结构体，改为使用数组实现的方法。显然，采用数组就失去了随机动态存储的优点。

（2）不能改变链表最重要的特点，即每个节点都包含本节点的值与指向下一节点的地址，并且还要保持链表存储的无序性。

根据上面的要求和限制，在使用数组实现邻接表时：

（1）用一维数组代替结构体graph。

（2）该数组中的前 V 个存储单元即是 V 个节点的头指针，初始值为0表示为空。

（3）后面每两个存储单元表示一个节点。其中，第一个存储单元是下一个节点在数组中的存储位置（指向下一个单元的指针，也是存储地址），第二个存储单元是当前节点的值。

（4）不难算出，如果一个无向图有 V 个节点和 i 条边，总共需要 V 个头指针和2× i 个节点，一个节点需要两个存储单元，因此需要使用（ V +4× i ）个存储单元。在本节所介绍的实现中，共使用了5+4×7=33个存储单元。

3.2.6 C语言程序设计-邻接表的数组实现

基于数组结构构建邻接表的C语言代码如代码清单3-7所示。

注 ：读者可以定位到本书提供资源的\loongson1B_training_example\example_3_4目录中，使用LoongIDE软件工具打开example_3_4.lxp工程文件。

3.2.7 C语言编译和调试-邻接表的数组实现

本节将介绍如何对设计工程进行编译，并将设计下载到龙芯1B开发板进行验证。具体实现步骤如下所示。

（1）编译程序代码，给龙芯1B硬件开发平台上电。

（2）启动并配置PuTTY（64-bit）软件工具。

（3）在LoongIDE主界面主菜单下，选择Debug->Run，进入调试器模式，开始运行程序，在PuTTY命令行界面中打印出建立的邻接表信息，如图3.11所示。

3.2.8 汇编语言程序设计

构建邻接表的汇编语言代码如代码清单3-8所示。

注 ：读者可以定位到本书提供资源的\loongson1B_training_example\example_3_5目录中，使用LoongIDE软件工具打开example_3_5.lxp工程文件。

3.2.9 汇编语言编译并调试

本节将介绍如何对前面所设计的汇编语言代码进行编译，并在龙芯1B硬件开发平台上进行调试和验证。具体实现步骤如下所示。

（1）编译设计代码，并给龙芯1B硬件开发平台上电。

（2）如图3.12所示，在代码清单3-8中设置断点。

（3）在LoongIDE主界面主菜单下，选择Debug->Run，进入调试器界面，程序自动停到设置断点的位置。

（4）在LoongIDE调试器界面右侧的“CPU Register”标签页中，找到并用鼠标左键双击寄存器名字为“s1”的一行。

（5）弹出“View Memory”对话框，如图3.13所示。在该对话框中，按如下设置参数。

① Count：33（通过在“Count”标题右侧的文本框输入数字）。

② Data Type：short（通过选中“short”前面的复选框设置）。

（6）单击“Fetch”按钮，在图3.13中即可给出邻接表的存储格式，即乱序的链表形式。因为数据采用半字类型存储，因此一个半字占用两个字节。

（7）单击图3.13中的按钮图标 ，退出“View Memory”对话框。

（8）在LoongIDE调试器界面右侧的“CPU Register”标签页中，找到并用鼠标左键双击寄存器名字为“s2”的一行。

（9）弹出“View Memory”对话框，如图3.14所示。图3.14中，邻接表以两个连续的0作为间隔符。从图3.14推导出的邻接表格式如图3.15所示。