前言

最近要求基于给定的语料实现一个简单的搜索引擎，那么提到搜索引擎第一反应肯定是图论了。然而翻遍了所有允许我用的代码，都没有找到使用邻接链表储存图的，于是只好自己写一个了。

图的储存方式

1. 邻接矩阵
2. 邻接链表
3. 边集数组（前向星/类前向星）

邻接链表

类似与邻接矩阵，但是邻接链表并不关心那些不连通的定点。对于邻接矩阵来说，若两个顶点i, j之间并不相互连接，那么访问g[i][j]将会得到∞或者-1等特殊值。但是对于邻接链表来说，这样的“边”根本就不会被存入。这样一来在处理稀疏图的时候，其时空效率都会比使用邻接矩阵储存数据更优。下图比较直观地显示了邻接链表这一个数据结构。

实现

其基本的实现原理是这样的：

1. 顶点结构：数据域 + 第一条出道的内存地址域
2. 边（出/入道）结构：指向顶点的内存地址域 + 下一条出道的内存地址域
3. 图结构：顶点个数 + 保存所有顶点的数组

顶点结构可以看成是保存数据的同时提供该顶点其中一条出道，这个出道其实就是边了，通过这条出道，既可以找到这个顶点指向的顶点，也可以顺着这条边提供的下一个内存地址来找到这个顶点的下一条出道。这样一来就可以实现从一个顶点出发，遍历所有可以到达的顶点。同时图结构使用一个数组来按照一定顺序来保存每个顶点，使其可以被索引，方便了访问。

注意

• 顶点和边的使用互相包含在对方的定义里，需要使用typedef来防止报错。
• 图结构中的数组在一开始并不会直接被定义成确定的大小，而是需要通过calloc的方式根据实际情况一次性定义出需要的大小
• 由于数据是URL/char *，小心内存泄漏……
• 初始化的时候需要把应该指向NULL的地方指向NULL，防止编译出Waring
• 顶点在数组中的ID不一定和其保存的数据一致

代码

不存在的，还没写完呢，下个月再说吧

参考

极客学院
Wiki

• Shell - 空格的处理
• C - scanf的内存管理