时间戳

首页 > 技术文章 > 数据结构 图的接口定义与实现分析（超详细注解）

数据结构 图的接口定义与实现分析（超详细注解）

idreamo 原文

如果您对图的定义尚不清楚，可以点此查看关于图的定义和描述。

我们在这里讨论的图的接口有11个，涉及到8个函数接口和3个宏定义。

函数接口包括初始化图、销毁图、插入顶点、插入边、移除顶点、移除边、取出顶点邻接表、判断顶点是否邻接；宏接口包括返回邻接表的结构链表、返回顶点个数、返回边个数。

graph_init

void graph_init(Graph *graph, int (*match)(const void *key1,const void *key2), void (*destroy)(void *data));

返回值 ：无

描述：初始化由参数gragh指定的图。该函数必须在执行其他与图相关的操作之前调用。

match参数指定用来判断两个顶点是否匹配的函数，该函数会用在其他的图操作中。当key1=key2时，match函数返回1；否则返回0。

destroy参数所指定的函数提供一种释放动态分配数据空间的方法。比如，如果图包含由malloc动态分配的空间，则destroy应该设置为free，当销毁图时以此来释放动态分配的内存。对于包含多个动态分配成员的结构化数据，destroy参数应该设置为一个用户定义的析构函数，用来对每一个动态分配的成员以及结构体自身做资源回收操作。如果图不包含需要动态释放空间的数据，destroy参数应该设置为NULL。

复杂度：O(1)

 graph_destroy

void graph_destroy(Graph *graph);

返回值：无

描述：销毁由参数graph所指定的图。该函数调用后，任何其他的图操作都不允许再执行，除非再次初始化。

graph_destroy将图中所有顶点和边都移除，如果destroy参数不为NULL的话，则调用destroy参数所指定的析构函数针对每个移除的顶点和边做资源回收操作。

复杂度：O（V+E），这里V是图中顶点个数，E是边的个数。

graph_ins_vertex

int graph_ins_vertex(Graph *graph, const void *data);

返回值：如果插入顶点成功则返回0，如果顶点已经存在则返回1，否则返回-1。

描述：将顶点插入由参数graph所指定的图中。

新顶点包含一个指向data的指针，因此只要顶点还在图中，data所引用的内存就必须保持有效。由调用者管理data所引用的存储空间。

复杂度：O（V），这里V代表图中的顶点个数。

graph_ins_edge

int graph_ins_edge(Graph *graph, const void *data1, const void *data2);

返回值：如果插入边成功，返回0；如果边已经存在，返回1；否则返回-1；

描述：将由data1以及data2所指定的顶点构成的边插入图中。data1和data2必须是使用graph_ins_vertex已经插入图中的顶点。新的边由data1所指定的顶点的邻接表中指向data2的指针来表示。因此，只要这条边还在图中，data2所引用的内存就必须合法。由调用者负责维护data2所引用的内存空间。

要在无向图中插入边（u，v），需要调用该函数两次：第一次将插入由u到v的边，第二次插入由v到u的边。这种类型的表示法对于无向图来说很普遍。

复杂度：O（V），这里V代表图中的顶点个数。

graph_rem_vertex

int graph_rem_vertex(Graph *graph,void **data);

返回值：如果移除顶点成功，返回0，否则返回-1。

描述：从graph指定的图中移除与data相匹配的顶点。在调用该函数之前，所有与该顶点相关的边都必须移除。函数返回后，data指向已移除顶点中保存的数据。由调用者负责管理data所引用的存储空间。

复杂度：O（V+E），这里V代表图中顶点个数，而E代表边的个数。

graph_rem_edge

int graph_rem_edge(Graph *graph, const void *data1, void **data2);

返回值：如果移除成功，返回0；否则返回-1。

描述：从graph指定的图中移除从data1到data2的边。函数返回后，data2指向由data1所指定的顶点的邻接表中保存的数据。由调用者管理data2所引用的存储空间。

复杂度：O（V），这里V代表图中的顶点个数。

graph_adjlist

int graph_adjlist(const Graph *graph, const void *data, AdjList **adjlist);

返回值：如果取得邻接表成功，返回0；否则返回-1。

描述：取出graph中由data所指定的顶点的邻接表。返回的邻接表以结构体AdjList的形式保存。

该结构体包含与data相匹配的顶点，以及其他与其邻接的顶点。函数返回后得到一个指向邻接表的指针，因此调用者必须保证不修改该邻接表中的数据，否则将破坏原始图中的数据。

复杂度：O（V），这里V代表图中的顶点的个数。

graph_is_adjacent

int graph_is_adjacent(const Graph *graph, const void *data1, const void *data2);

返回值：如果第二个顶点与第一个顶点邻接，返回1；否则返回0。

描述：判断由data2所指定的顶点是否与graph中由data1所指定的顶点邻接。

复杂度：O（V），这里V代表图中的顶点个数。

graph_adjlists

List graph_adjlists(const Graph *graph);

返回值：由邻接表结构所组成的链表。

描述：这是一个宏，用来返回由参数graph所指定的图中的邻接表结构链表。

该链表中的每一个元素都是AdjList结构体。由于返回的是图中的邻接表结构链表而不是其拷贝，因此用户必须保证不对该链表做其他操作。

复杂度：O（1）

graph_vcount

int graph_vcount(const Graph *graph);

返回值：图中顶点的个数。

描述：这是一个宏，用来返回graph所指定的图中的顶点的个数。

复杂度：O（1）

graph_ecount

int graph_ecount(const Graph *graph);

返回值：图中边的个数。

描述：这是一个宏，用来计算graph指定的图中边的个数。

复杂度：O（1）

 图的实现代码分析

我们通过邻接表链表结构来表示图。

链表中的每个结构体都包含两个成员：一个顶点，以及与该顶点相邻接的顶点的集合。链表中的结点由结构体AdjList表示。

图的数据结构使用Graph代表。这个结构体包含5个成员：vcount代表图中的顶点个数；ecount代表图中边的个数；match、destroy用来封装初始化时传递给graph_init的函数；adjlists代表邻接表链表。

我们为顶点的颜色属性定义枚举类型，这些颜色属性在图的操作中非常常用。

 示例1：图抽象数据类型的头文件

/*graph.h*/
#ifndef GRAPH_H
#define GRAPH_H

#include <stdlib.h>
#include "list.h"
#include "set.h"

/*为邻接表链表定义成员结构体*/
typedef struct AdjList_
{
    void *vertex;
    set adjacent;
}AdjList;

/*为图定义数据结构*/
typedef struct Graph_
{
    int vcount;
    int ecount;
    
    int (*match)(const void *key1,const void *key2);
    void (*destroy)(void *data);
    
    List adjlist;
}Graph;

/*使用枚举类型来定义颜色属性*/
typedef enum VertexColor_{white,gray,black} VertexColor;

/*图的接口部分*/
void graph_init(Graph *graph, int(*match)(const void *key1,const void *key2),void (*destroy)(void *data));
void graph_destroy(Graph *graph);
int graph_ins_vertex(Graph *graph,const void *data);
int graph_ins_edge(Graph *graph,const void *data1,const void *data2);
int graph_rem_vertex(Graph *graph,void **data);
int graph_rem_edge(Graph *graph,void *data1,void **data2);
int graph_adjlist(const Graph *graph,const void *data,AdjList **adjlist);
int graph_is_adjacent(const Graph *graph,const void *data1,const void *data2);
#define graph_adjlists(graph)((graph)->adjlists)
#define graph_vcount(graph)((graph)->vcount)
#define graph_ecount(graph)((graph)->ecount)

#endif // GRAPH_H

 示例2：抽象数据类型图的实现

/*graph.c*/
#include <stdlib.h>
#include <string.h>
#include "graph.h"
#include "list.h"
#include "set.h"

/*graph_init  初始化图*/
void graph_init(Graph *graph,int (*match)(const void *key1,const void key2),void (*destroy)(void *data))
{
    /*初始化图结构*/
    graph->vcount = 0;
    graph->ecount = 0;
    graph->match  = match;
    graph->destroy = destroy;

    /*初始化邻接表链表结构*/
    list_init(&graph->adjlists,NULL);

    return;
}

/*graph_destroy  销毁图结构*/
void graph_destroy(Graph *graph)
{
    AdjList *adjlist;

    /*删除每一个邻接表结构并将其销毁*/
    while(list_size(&graph->lists)>0)
    {
        if(list_rem_next(&graph->adjlists,NULL,(void **)&adjlist)==0)
        {
            /*移除顶点集合*/
            set_destroy(&adjlist->adjacent);
            /*释放顶点成员的内存空间*/
            if(graph->destroy != NULL)
                graph->destroy(adjlist->vertex);
            /*释放邻接表结构*/
            free(adjlist);
        }
    }

    /*销毁邻接表链表结构*/
    list_destroy(&graph->adjlists);

    /*作为预防措施清理数据结构*/
    memset(graph,0,sizeof(Graph));
    return;
}

/*graph_ins_vertex 将顶点插入图中*/
/*该函数会将一个AdjList结构体插入邻接表链表结构中，并将AdjList结构体中的vertex成员指向由调用者传入的数据*/
int graph_ins_vertex(Graph *graph,const void *data)
{
    ListElmt *element;
    AdjList *adjlist;
    int retval;

    /*首先，要确保顶点不存在于列表中，如果顶点已经存在则返回1*/
    for(element=list_head(&graph->adjlists); element != NULL; element=list_next(element))
    {
        if(graph->match(data,((AdjList*)list_data(element))->vertex))
            return 1;
    }
    /*插入顶点，为邻接表分配空间*/
    if((adjlist = (AdjList*)malloc(sizeof(AdjList)))==NULL)
        return -1;
    /*将adjlist结构中的成员指向传入的数据data*/
    adjlist->vertex=(void*)data;
    /*初始化一个顶点的邻接顶点集合*/
    set_init(&adjlist->adjacent,graph->match,NULL);
    /*调用list_ins_next()将结构体插入到邻接表链表中*/
    if((retval = list_ins_next(&graph->adjlists,list_tail(&graph->adjlists),adjlist))!=0)
    {
        return retval;
    }
    /*调整图中的顶点统计数据*/
    graph->vcount++;
    return 0;
}

/*graph_ins_edge 将一条边插入图中*/
/*插入从data1到data2的边，即将data2插入到data1的邻接表中*/
int graph_ins_edge(Graph *graph,const void *data1,const void *data2)
{
    ListElmt *element;
    int retval;

    /*首先，要保证这两个顶点都存在于图中*/
    for(element = list_head(&graph->adjlists); element != NULL; element = list_next(element))
    {
        if(graph->match(data2,((AdjList *)list_data(element))->vertex))
            break;
    }
    if(element == NULL)
        return -1;

    for(element = list_head(&graph->adjlists); element != NULL; element = list_next(element))
    {
        if(graph->match(data2,((AdjList *)list_data(element))->vertex))
            break;
    }
    if(element == NULL)
        return -1;

    /*将data2的顶点插入到data1的邻接顶点集合中*/
    if((retval = set_insert(&((AdjList *)list_data(element))->adjacent,data2)) !=0 )
    {
        return retval;
    }

    /*调整图中图的统计数量*/
    graph->ecount++;
    return 0;
}

/*graph_rem_vertex  将顶点从图中移除*/
/*该函数将一个AdjList结构体从邻接表结构链表中移除*/
int graph_rem_vertex(Graph *graph,void **data)
{
    ListElmt *element, *temp, *prev;
    AdjList *adjlist;
    int found;

    /*首先确保顶点不存在于任何邻接表中，但顶点要存在于邻接表结构链表里，且它的邻接表为空*/
    prev=NULL;
    found=0;
    
    for(element = list_head(&graph->adjlists); element != NULL; element = list_next(element))
    {
        /*不允许移除邻接表中的顶点*/
        if(set_is_member(&((AdjList *)list_data(element))->adjacent,*data))
            return -1;
        /*找到将要移除的顶点，标记found=1,并使指针temp指向顶点*/
        if(graph->match(*data,((AdjList *)list_data(element))->vertex))
        {
            temp=element;
            found=1;
        }
        
        /*使prev指向目标元素之前的元素*/
        if(!found)
            prev = element;
    }
    
    /*如果未找到要移除的顶点，返回*/
    if(!found)
        return -1;
        
    /*如果顶点的邻接表不为空，返回*/
    if(set_size(&((AdjList *)list_data(temp))->adjacent)>0)
        return -1;
        
    /*满足移除条件，移除顶点*/
    if(list_rem_next(&graph->adjlists,prev,(void **)&adjlist) != 0)
        return -1;
        
    /*使*data指向被移除的顶点，释放邻接表数据结构的空间*/
    *data=adjlist->vertex;
    free(adjlist);
    
    /*调整图中的顶点统计数*/
    graph->vcount--;
    return 0;
}

/*graph_rem_edge  将一条边从图中移除*/
/*该函数将由data2指定的顶点从data1所指定的顶点的邻接表中移除*/
int graph_rem_edge(Graph *graph, void *data1, void **data2)
{
    ListElmt *element;
    
    /*首先，确保顶点1存在于图中*/
    for(element = list_head(&graph->adjlists); element != NULL; element = list_next(element))
    {
        if(graph->match(data1,((AdjList *)list_data(element))->vertex))
            break;
    }
    
    if(element==NULL)
        return -1;
    
    /*通过验证，调用set_remove()来将data2从data1的邻接表中移除*/
    if(set_remove(&((AdjList *)list_data(element))->adjacent,data2)!=0)
        return -1;
    
    /*最后调整图中边的数量*/
    graph->ecount--;
    return 0;
}
    
/*graph->adjlist  返回一个AdjList结构体*/
/*返回一个AdjList结构体，其中包含指定顶点的邻接顶点集合*/
int graph_adjlist(const Graph *graph, const void *data, AdjList **adjlist)
{
    ListElmt *element,*prev;
    
    /*找到包含顶点的链表元素*/
    prev = NULL;
    for(element = list_head(&graph->adjlists); element != NULL; element = list_next(element))
    {
        if(graph->match(data,((AdjList *)list_data(element))->vertex))
            break;
        
        prev = element;
    }
    
    if(element == NULL)
        return -1;
    
    /*返回的邻接表保存到*adjlist*/
    *adjlist = list_data(element);
    return 0;
}

/*graph_is_adjacent  判断两个顶点是否有邻接关系*/
int graph_is_adjacent(const Graph *graph, const void *data1, const void *data2)
{
    ListElmt *element, *prev;
    
    /*首先，在邻接表链表结构中定位data1所指定的顶点*/
    prev=NULL;
    for(element = list_head(&graph->adjlists); element != NULL; element = list_next(element))
    {
        if(graph->match(data1,((AdjList *)list_data(element))->vertex))
            break;
        
        prev=element;
    }
    
    if(element==NULL)
        return 0;
    
    /*调用set_is_member来查看data2是否存在于data1的邻接顶点集合中*/
    return set_is_member(&((AdjList *)list_data(element))->adjacent,data2);
}

推荐阅读