数据结构——图——存储结构——邻边表

「爱情、让人受尽委屈。」 2023-01-10 14:46 95阅读 0赞

## 数据结构——图——存储结构——邻边表 ##

## 邻接表的处理办法 ##

1.图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。

2.图中每个顶点v的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点v的边表，有向图则称为顶点v作为弧尾的出边表。

例如图7-4-6所示的就是一个无向图的邻接表结构。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70]  
从图中我们知道，顶点表的各个结点由data和 firstedge两个域表示，data是数据域，存储顶点的信息，firstedge是指针域，指向边表的第一个结点，即此顶点的第-一个邻接点。边表结点由adjvex 和 next两个域组成。adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标，next则存储指向边表中下一个结点的指针。比如v顶点与vo、vz互为邻接点，则在v1的边表中，adjvex 分别为vo的0和v的2。

这样的结构，对于我们要获得图的相关信息也是很方便的。比如我们要想知道某个顶点的度，就去查找这个顶点的边表中结点的个数。若要判断顶点v到v是否存在边，只需要测试顶点v的边表中 adjvex是否存在结点v的下标j就行了。若求顶点的所有邻接点，其实就是对此顶点的边表进行遍历，得到的 adjvex 域对应的顶点就是邻.接点。

若是有向图，邻接表结构是类似的，比如图7-4-7中第一幅图的邻接表就是第二幅图。但要注意的是有向图由于有方向，我们是以顶点为弧尾来存储边表的，这样很容易就可以得到每个顶点的出度。但也有时为了便于确定顶点的入度或以顶点为弧头的弧，我们可以建立一个有向图的逆邻接表，即对每个顶点v都建立一个链接为v为弧头的表。如图7-4-7的第三幅图所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 2]  
此时我们很容易就可以算出某个顶点的入度或出度是多少，判断两顶点是否存在弧也很容易实现。

对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可，如图7-4-8所示。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 3]  
有了这些结构的图，下面关于结点定义的代码就很好理解了。

#define MAXVEX 100   /*最大顶点数，应由用户定义*/
    typedef char VertexType;  /*顶点类型应由用户定义*/
    
    typedef int EdgeType;  /*边上的权值类型应由用户定义*/
    
    typedef struct EdgeNode  /*边表结点*/
    {
        
    	int adjvex;  /*邻接点域，存储该顶点对应的下标*/
    	EdgeType weight; /*用于存储权值，对于非网图可以不需要*/
    	struct EdgeNode* next;  /*链域，指向下一个邻接点*/
    } EdgeNode;
    
    typedef struct vertexNode/*顶点表结点*/
    {
        
    	VertexType data;   /*顶点域，存储顶点信息*/
    	EdgeNode* firstedge;   /*边表头指针*/
    
    }vertexNode, AdjList[MAXVEX];
    
    typedef struct
    {
        
    	AdjList adjList;
    	int numvertexes, numEdges;/*图中当前顶点数和边数*/
    
    } GraphAdjList;

对于邻接表的创建，也就是顺理成章之事。无向图的邻接表创建代码如下。

/*建立图的邻接表结构*/
    void CreateALGraph(GraphAdjList* G)
    {
        
    	int i, j, k;
    	EdgeNode* e;
    	printf("输入顶点数和边数：\n");
    	scanf("%d,%d", &G->numvertexes, &G->numEdges);/*输入顶点数和边数*/
    	
    	for (i=0;i<G->numvertexes;i++)        /*读入顶点信息，建立顶点表*/
    	{
        
    		scanf(&G->adjList[i].data);         /*输入顶点信息*/
    		G->adjList[i].firstedge = NULL;     /*将边表置为空表*/
    	}
    
    	for (k=0;k<G->numEdges;k++)       /*建立边表*/
    	{
        
    		printf("输入(Vi,Vj)上的顶点序号：\n");
    
    		scanf("%d, %d",&i,&j);/*输入边(vi,v3)上的顶点序号*/
    
    		e = (EdgeNode*)malloc(sizeof(EdgeNode));   /*向内存申请空间*/
    		                                           /*生成边表结点*/
    		e->adjvex = j;         /*邻接序号为j*/
    
    		e->next = G->adjList[i].firstedge; /*将e指针指向当前顶点指向的结点*/
    		G->adjList[i].firstedge=e;/*将当前顶点的指针指向e*/
    
    		e = (EdgeNode*)malloc(sizeof(EdgeNode));   /*向内存申请空间*/
    												   /*生成边表结点*/
    		e->adjvex = i;         /*邻接序号为i*/
    		e->next = G->adjList[i].firstedge; /*将e指针指向当前顶点指向的结点*/
    		G->adjList[i].firstedge = e;/*将当前顶点的指针指向e*/
    
    	}
    }

由于对于无向图，一条边对应都是两个顶点，所以在循环中，一次就针对i和j分别进行了插入。本算法的时间复杂度，对于n个顶点e条边来说，很容易得出是O(n+e)。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70]: /images/20221119/5b4e1523283940d7a1bac416a3b1ed78.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/202101251006299.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210125100651457.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20210125101221524.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ==,size_16,color_FFFFFF,t_70