数据结构之图的存储结构一及其实现

桃扇骨 2022-05-31 14:27 286阅读 0赞

**图的存储结构**

由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在存储区中的物理位置来表示元素之间的关系，即图没有顺序映像的存储结构，但可以借助数组的数据类型表示元素之间的关系。另一方面，用多重链表表示图是自然的事，它是一种最简单的链式映像结构，即以一个右一个数据域和多个指针域组成的结点表示图中的一个顶点，其中数据域存储该顶点的信息，指针域存储指向其邻接点的指针。但是，由于图中各个结点的度数各不相同，最大度数和最小度数可能相差很多，因此，若按度数最大的顶点设计结点结构，则会浪费很多存储单元；反之，若按每个顶点的度数设计不同的结点结构，又会给操作带来不便。因此，和数类似，在实际应用汇总不宜采用这种结构，而应根据具体的图和需要进行的操作，设计何时的结点结构和表结构。常用的有邻接表、邻接多重表和十字链表。下面我们讨论一下邻接矩阵法及其C语言实现方式。

**邻接矩阵法（数组表示法）**

基本思想：

1.用一维数组存储顶点 **–** 描述顶点相关的数据；

**2.** 用二维数组存储边 **–** 描述顶点间的边。

设图 G = (V,E) 是一个有 n 个顶点的图, 图的邻接矩阵为 Edge\[n\]\[n\]，则：

![70][]

W为权值，当不需要权值时，取W为1表示结点间连接。

无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。如下图所示：

![70 1][]

显然，借助于邻接矩阵容易判定任意两个顶点之间是否有边相连，并容易求得各个顶点的度。对于无向图，顶点vi的度是邻接矩阵中第行（或第i列）的元素之和，对于有向图，第i行的元素之和为顶点vi的出度OD(vi), 第j列的元素之和为顶点vj的入度ID(vj)。

下面我们讲解一下通过邻接矩阵法使用C语言实现代码，讲解代码之前我们先dingyiyi：邻接矩阵法的头结点

邻接矩阵法的头结点：

1. 记录顶点个数；

2. 记录与顶点相关的数据描述；

3. 记录描述边集的二维数组。

// 定义图结点结构体
    typedef struct _tag_MGraph
    {
        int count;             // 存放图顶点个数
        MVertex** v;           // 存放顶点内容相关描述
        int** matrix;          // 记录描述边集的二维数组
    } TMGraph;

看了上面定义的结构体，那么问题就来了，如何根据顶点数目，动态创建二维数组。

动态申请二维数组原理：

1. 通过二级指针动态申请一维指针数组；

2. 通过一级指针申请数据空间；

3. 将一维指针数组中的指针连接到数据空间。

如下图：

![70 2][]

下面讲解代码：

1.创建图

/* 创建并返回有n个顶点的图 */
    MGraph* MGraph_Create(MVertex** v, int n)  // O(n)
    {
        // 定义图结点结构体变量
        TMGraph* ret = NULL;
        // 入口参数检测OK
        if( (v != NULL ) && (n > 0) )
        {
        	// 申请图结点结构体内存
            ret = (TMGraph*)malloc(sizeof(TMGraph));
            // 内存申请成功
            if( ret != NULL )
            {
                // 定义一个一级指针用于辅助申请数据空间
                int* p = NULL;
                // 根据参数初始化图顶点个数
                ret->count = n;
                // 根据顶点个数，为保存顶点内容相关描述申请内存，
                ret->v = (MVertex**)malloc(sizeof(MVertex*) * n);
                // 根据顶点个数，为记录描述边集的二维数组申请内存
                ret->matrix = (int**)malloc(sizeof(int*) * n);
                // 根据顶点个数，申请数据空间并初始化申请的内存
                p = (int*)calloc(n * n, sizeof(int));
                // 申请内存成功
                if( (ret->v != NULL) && (ret->matrix != NULL) && (p != NULL) )
                {
                    int i = 0;
                    // 连接数据空间
                    for(i=0; i<n; i++)
                    {
                        ret->v[i] = v[i];                    // 保存图顶点相关描述
                        ret->matrix[i] = p + i * n;          // 将一维指针数组中的指针空间连接到数据空间
                    }
                }
                // 申请内存失败，释放内存，防止内存泄漏
                else
                {
                    free(p);
                    free(ret->matrix);
                    free(ret->v);
                    free(ret);
                    
                    ret = NULL;
                }
            }
        }
        
        return ret;
    }

从如上代码我们得知，创建图时，使用了动态申请二维数组原理了。还有一个亮点就是使用了calloc()函数来申请数据空间，这样就减少了后续初始化申请空间的操作了。

2.销毁图

/* 销毁graph所指向的图 */
    void MGraph_Destroy(MGraph* graph) // O(1)
    {
        // 定义图结构体变量，并进行强制转换入口参数
        TMGraph* tGraph = (TMGraph*)graph;    
        // 合法性检查OK
        if( tGraph != NULL )
        {
            free(tGraph->v);            // 释放顶点内容空间
            free(tGraph->matrix[0]);    // 释放数据空间，数据空间的首地址存放在ret->matrix[0]中
            free(tGraph->matrix);       // 释放矩阵指针空间
            free(tGraph);               // 释放图结构空间
        }
    }

通过代码，我们看到销毁图其实就是相应内存空间的释放，但是也不能任意释放，也得要按照一定的顺序释放。

3.清空图

/* 将graph所指图的边集合清空 */
    void MGraph_Clear(MGraph* graph) // O(n*n)
    {
    	  // 定义图结构体变量，并进行强制转换入口参数
        TMGraph* tGraph = (TMGraph*)graph;
        // 合法性检查OK
        if( tGraph != NULL )
        {
            int i = 0;
            int j = 0;
            // 将邻接矩阵中的所有元素清零
            for(i=0; i<tGraph->count; i++)
            {
                for(j=0; j<tGraph->count; j++)
                {
                    tGraph->matrix[i][j] = 0;
                }
            }
        }
    }

清空图其实就是将邻接矩阵中的所有元素清零，因为是矩阵，二维数组，所以使用了双层循环。

4.在图的两定点间添加边

/* 在graph所指图中的v1和v2之间加上边，且边的权为w
    v1：顶点1
    v2：顶点2
     */
    int MGraph_AddEdge(MGraph* graph, int v1, int v2, int w) // O(1)
    {
        // 定义图结构体变量，并进行强制转换入口参数
        TMGraph* tGraph = (TMGraph*)graph;    
        // 定义返回变量，并检查入口参数合法性
        int ret = (tGraph != NULL);
        
        ret = ret && (0 <= v1) && (v1 < tGraph->count);
        ret = ret && (0 <= v2) && (v2 < tGraph->count);
        ret = ret && (0 <= w);
        // 合法性OK，将权值赋给两个顶点相应位置的邻接矩阵
        if( ret )
        {
            tGraph->matrix[v1][v2] = w;
        }
        
        return ret;
    }

这个比较简单，就是将权值赋值给两定点确定的位置的邻接矩阵即可。

5.删除两顶点间的边

再删除之前，首先得先找到要删除的边，只有在边存在的情况下删除才有意义，寻找边代码如下：

/* 将graph所指图中v1和v2之间的边的权值返回 */
    int MGraph_GetEdge(MGraph* graph, int v1, int v2) // O(1)
    {
        // 定义图结构体变量，并进行强制转换入口参数
        TMGraph* tGraph = (TMGraph*)graph;    
        // 定义返回变量
        int ret = 0;
        // 定义中间变量，用于合法性检查
        int condition = (tGraph != NULL);
        
        condition = condition && (0 <= v1) && (v1 < tGraph->count);
        condition = condition && (0 <= v2) && (v2 < tGraph->count);
        // 合法性检查OK，返回指定顶点位置的边的权值
        if( condition )
        {
            ret = tGraph->matrix[v1][v2];
        }
        
        return ret;
    }

删除代码如下：

/* 将graph所指图中v1和v2之间的边删除，返回权值 */
    int MGraph_RemoveEdge(MGraph* graph, int v1, int v2) // O(1)
    {
        // 获取图指定位置的边
        int ret = MGraph_GetEdge(graph, v1, v2);
        // 获取成功，将相对应的邻接矩阵位置设为0
        if( ret != 0 )
        {
            ((TMGraph*)graph)->matrix[v1][v2] = 0;
        }
        
        return ret;
    }

6.获取的图的度数

/* 将graph所指图中v顶点的度数 */
    int MGraph_TD(MGraph* graph, int v) // O(n)
    {
        // 定义图结构体变量，并进行强制转换入口参数
        TMGraph* tGraph = (TMGraph*)graph;
        // 定义返回变量
        int ret = 0;
        // 定义中间变量，用于合法性检查
        int condition = (tGraph != NULL);    
        condition = condition && (0 <= v) && (v < tGraph->count);    
        // 合法性检查OK
        if( condition )
        {
            int i = 0;
            // 遍历顶点v所在邻接矩阵行和列
            for(i=0; i<tGraph->count; i++)
            {
                // 求顶点V的出度
                if( tGraph->matrix[v][i] != 0 )
                {
                    ret++;
                }
                
            	  // 求顶点V的入度
                if( tGraph->matrix[i][v] != 0 )
                {
                    ret++;
                }
            }
        }
        // 返回顶点度数
        return ret;
    }

至此，可能有人就要问了，这不是针对有向图的吗，要是无向图算出来的度不是翻倍了吗？怎么办？其实，无向图就是特殊的有向图，如果没有说明，你就直接当做有向图使用即可，当然，你能确认是无向图时，你只要将返回的值除以2不就可以了。不仅是这里，后面要讲到的返回图的变数也是如此操作。

7.返回图顶点数

/* 将graph所指图中的顶点数返回 */
    int MGraph_VertexCount(MGraph* graph) // O(1)
    {
        // 定义图结构体变量，并进行强制转换入口参数
        TMGraph* tGraph = (TMGraph*)graph;
        int ret = 0;
        // 入口参数合法，直接返回创建图时图的个数
        if( tGraph != NULL )
        {
            ret = tGraph->count;
        }
        
        return ret;
    }

这没有什么好解释的。

8.返回图中的边数

/* 将graph所指图中的边数返回 */
    int MGraph_EdgeCount(MGraph* graph) // O(n*n)
    {
        // 定义图结构体变量，并进行强制转换入口参数
        TMGraph* tGraph = (TMGraph*)graph;
        int ret = 0;    
        // 入口参数合法
        if( tGraph != NULL )
        {
            int i = 0;
            int j = 0;
            // 遍历整个邻接矩阵
            for(i=0; i<tGraph->count; i++)
            {
                for(j=0; j<tGraph->count; j++)
                {
                	// 权值不为0的点就是图的边
                    if( tGraph->matrix[i][j] != 0 )
                    {
                        ret++;
                    }
                }
            }
        }
        
        return ret;
    }

返回图中边的个数，其实就是要返回邻接矩阵中所有取值不为0的元素个数，所以需要遍历整个邻接矩阵。至于有向图与无向图的具体操作可以参考上面的返回图的度数操作方式。

到这里，或许有人就要问了，上面实现了这么多的图的操作，我们如何验证它的正确性，可靠性呢？不要急，下面我们就通过显示函数显示图来验证它的正确性、可靠性。

9.图的显示函数

// 图打印函数
    void MGraph_Display(MGraph* graph, MGraph_Printf* pFunc) // O(n*n)
    {
        // 定义图结构体变量，并进行强制转换入口参数
        TMGraph* tGraph = (TMGraph*)graph;
        // 入口参数合法性检查OK
        if( (tGraph != NULL) && (pFunc != NULL) )
        {
            int i = 0;
            int j = 0;
            // 打印图的顶点
            for(i=0; i<tGraph->count; i++)
            {
                printf("%d:", i);
                pFunc(tGraph->v[i]);
                printf(" ");
            }
            
            printf("\n");
            // 打印图的边
            // 遍历邻接矩阵，将权值不为0的边打印出来
            // 有向图边格式 <i,j> 
            for(i=0; i<tGraph->count; i++)
            {
                for(j=0; j<tGraph->count; j++)
                {
                    if( tGraph->matrix[i][j] != 0 )
                    {
                        printf("<");
                        pFunc(tGraph->v[i]);
                        printf(", ");
                        pFunc(tGraph->v[j]);
                        printf(", %d", tGraph->matrix[i][j]);      // 取值，及边的耗费
                        printf(">");
                        printf(" ");
                    }
                }
            }
            
            printf("\n");
        }
    }

从代码可知，既然打印图，不仅要打印出顶点，还要将边及权值也打印出来。

下面我们就赶紧看一下测试代码

#include <stdio.h>
    #include <stdlib.h>
    #include "MGraph.h"
    
    /* run this program using the console pauser or add your own getch, system("pause") or input loop */
    
    void print_data(MVertex* v)
    {
        printf("%s", (char*)v);
    }
    
    int main(int argc, char *argv[])
    {
        MVertex* v[] = {"A", "B", "C", "D", "E", "F"};
        MGraph* graph = MGraph_Create(v, 6);
        
        MGraph_AddEdge(graph, 0, 1, 1);
        MGraph_AddEdge(graph, 0, 2, 1);
        MGraph_AddEdge(graph, 0, 3, 1);
        MGraph_AddEdge(graph, 1, 5, 1);
        MGraph_AddEdge(graph, 1, 4, 1);
        MGraph_AddEdge(graph, 2, 1, 1);
        MGraph_AddEdge(graph, 3, 4, 1);
        MGraph_AddEdge(graph, 4, 2, 1);
        
        MGraph_Display(graph, print_data);   
        
        MGraph_Destroy(graph);
        
    	return 0;
    }

测试效果如下：

![70 3][]

至此，我们已经讲完了图的邻接矩阵实现方法及代码。但是，我们发现邻接矩阵的每个元素就代表着图的一个边，显然申请的二维数组并不是每次都能使用完的，所以这就造成了内存的浪费。当然，邻接矩阵法也是与优点的，那就是实现起来比较方便。那么，有没有不这么浪费内存的实现方法呢？当然有了，我们下节将会讲解图的另一种实现方法：邻接表。

最后贴上整体代码：[邻接矩阵法实现图C代码][C]

[70]: /images/20220531/14bf74dae4a947e49217f8a5585a3859.png
[70 1]: /images/20220531/cdd8c900efab40ed9ba75f9022bc2d84.png
[70 2]: /images/20220531/6eaa95f192664c67b80cb791dbb69a2f.png
[70 3]: /images/20220531/df9fb1530cc84c3cb53503e00ba61503.png
[C]: http://download.csdn.net/download/u014754841/10262098