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

该结构体包含与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