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

素颜马尾好姑娘i 2023-03-01 05:34 53阅读 0赞

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]用邻接表表示是这样的：

![在这里插入图片描述][20200722110323718.png]

我们先直观的看一下邻接表的输出情况：  
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)。头插法的效率比较高，得到的链表的结果是反的。尾插法的效率比较低，但是得到的链表是正的。链表的正反对计算没有影响，所以以后统一采用头插法进行添加结点。运行结果见上图。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]: /images/20230209/56b585d64e1b41bd98880e5bca9b0cb5.png
[20200722110323718.png]: /images/20230209/43021245e5b9433b94e56726d23209c5.png