邻接表与邻接矩阵的对比，邻接表的C语言实现

图有多种表示方法，最简单的是邻接矩阵。但是邻接矩阵占用空间很大。对于稀疏图，邻接矩阵会浪费大量空间，遍历邻接矩阵时也会浪费大量时间。而邻接表就解决了这个问题。下面我们就要用链表实现邻接表，也就是需要使用指针了。邻接表是实现拓扑排序、关键路径、Dijkstra算法的优化、Prim算法的优化、Bellman-Ford算法的优化的关键。

如果使用邻接矩阵，下面这个图就需要用右边的6 * 6 = 36个数据的矩阵表示。例如，与0号结点直接相连的结点只有3个，但是却不得不遍历n个结点，并判断权重 < inf (inf表示无穷大) 之后才能确定哪些点与0号结点直接相连。

用邻接表表示是这样的：

我们先直观的看一下邻接表的输出情况：
1、左边的一列结点都存放在一个数组中；
2、数组中的结点可以有多个子节点，例如0号结点可以同时指向1、2、3号结点。虽然在邻接表中1-3号之间有指向关系，但实际上这些结点是平级的。仅仅是用指针将它们链接到0号结点罢了。
3、一共只需要26个数据即可。如果对于稀疏图，占用的空间更少。如果需要遍历，遍历的时间复杂度也要小很多。

邻接表的指针方式实现如下：

#include <stdio.h>
#include <stdlib.h>

int size = 6;

//声明结点的结构体 
struct LinkNode{
	int index = 0; //结点的编号 
	int weight = 0;
	struct LinkNode * next = NULL; //结点指向下一个结点 
};


struct ArrayNode{
	struct LinkNode * next = NULL; //结点指向第一个链表结点 
};

//用一个数组存放首元素。每个首元素后面用指针连接各个结点 
struct ArrayNode arrNode[6];

//头插法添加数据，得到的结果的次序是反的 
void addNode(int parentIndex, int nodeIndex, int weight)
{
	struct ArrayNode * myArrayNode;
	myArrayNode = &arrNode[parentIndex];
	
	//要向操作系统申请空间 
	struct LinkNode *temp = (struct LinkNode *)(malloc(sizeof(struct LinkNode)));
	temp->index = nodeIndex;
	temp->weight = weight;
	temp->next = myArrayNode->next;
	myArrayNode->next = temp; 
}

//通过首元素的index，在数组中找到首元素。然后遍历到最后一个结点，再插入新节点 
//这是尾插法。效率显然比头插法要低。但是得到的结果的次序是正的
void addNode2(int parentIndex, int nodeIndex)
{
	struct ArrayNode * currentNode; //声明一个指针变量
	currentNode = &arrNode[parentIndex]; //获得arrNode中第parentIndex个元素的指针
	
	struct LinkNode * node = currentNode->next;
	//找到链表的最后一个结点 
	while(node->next != NULL)
	{
		node = node->next;
	}
	
	//要向操作系统申请空间，并强制转化成Node指针
	struct LinkNode *temp = (struct LinkNode *)(malloc(sizeof(struct LinkNode)));
	temp->index = nodeIndex;//指针变量的赋值
	temp->next = NULL; //指针变量的赋值
	node->next = temp; //在最后一个结点后面插入temp结点 
}

//遍历一个结点，和它的所有相连的结点 
void traverse(int parentIndex)
{
	struct ArrayNode * myArrayNode = &arrNode[parentIndex];
	struct LinkNode * node = myArrayNode->next;
	
	printf("%d --> ", parentIndex);
	while(node != NULL)
	{
		printf("%d (%d) --> ", node->index, node->weight);
		node = node->next;
	}
	printf("\r\n");
}

//释放资源 
void releaseResource()
{
	struct LinkNode * temp; 
	for(int i = 0; i < size; i++) //把数组中每个点的相邻结点的指针全部释放掉 
	{
		while(arrNode[i].next != NULL)
		{
			temp = arrNode[i].next; //用temp接手相邻结点。 
			arrNode[i].next = arrNode[i].next->next; //数组中的结点接手孙子结点 
			free(temp); //这时就可以free2号结点了 
		}
	}
}

int main()
{
	//插入数据 
	addNode(0, 1, 10); addNode(0, 2, 16); addNode(0, 3, 14); addNode(1, 0, 10); 
	addNode(1, 3, 15); addNode(1, 4, 24); addNode(2, 0, 16); addNode(2, 3, 14); 
	addNode(2, 5, 16); addNode(3, 0, 14); addNode(3, 1, 15); addNode(3, 2, 14);
	addNode(3, 4, 23); addNode(3, 5, 8); addNode(4, 1, 24); addNode(4, 3, 23); 
	addNode(4, 5, 22); addNode(5, 2, 16); addNode(5, 3, 8);  addNode(5, 4, 22);
	
	for(int i = 0; i < size; i++) //对每个节点遍历它的相邻节点
	{
		traverse(i);
	}
	
	releaseResource();//释放资源
	 
	printf("Hello\r\n");
	return 0;
}

这里一共定义了两种插入结点的方法，分别是头插法 (addNode) 和尾插法 (addNode2)。头插法的效率比较高，得到的链表的结果是反的。尾插法的效率比较低，但是得到的链表是正的。链表的正反对计算没有影响，所以以后统一采用头插法进行添加结点。运行结果见上图。