1、图的定义

图：是一种灵活的数据结构，一般作为一种模型用来定义对象之间的关系或者联系。对象由顶点表示，而对象之间的关系或关联则通过顶点之间的边来表示。

２、图的应用

图算法、统计网络跳数、拓扑排序、图着色、哈密顿圈问题、分团问题、可序列化冲突

３、图的代码实现

/*graph.h*/#ifndef	GRAPH_H#define GRAPH_H#include <stdlib.h>#include "list.h"#include "set.h"/*define a structure for adjacency lists*/typedef struct AdjList_{	void *vertex;	Set adjacent;}AdjList;/*define structure for graphs*/typedef struct Graph_{	int		vcount;	int		ecount;	int		(*match)(const void *key1,const void *key2);	void	(*destroy)(void *data);	List	adjlists;}Graph;/*define colors for vertices in graphs*/typedef	enum VertexColor_ {white,gray,black}  VertexColor;/*public interface*/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)->dajlists)#define	graph_vcount(graph) ((graph)->vcount)#define	graph_ecount(graph) ((graph)->ecount)#endif

/*graph.c*/#include<stdlib.h>#include<string.h>#include"graph.h"#include"list.h"#include"set.h"void graph_init(Graph *graph,int (*match)(const void *key1,const void *key2),void (*destroy)(void *data)){	/*initialize the graph*/	graph->vcount=0;	graph->ecount=0;	graph->match=match;	graph->destroy=destroy;	/*initialize the list of adjacentcy-list structure*/	list_init(&graph->adjlists,NULL);	return ;}void graph_destroy(Graph *graph){	AdjList	*adjlist;	/*remove each adjacency-list structure and destroy its adjacency list*/	while(list_size(&graph->adjlists)>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);		}	}	/*destroy the list of adjacency-list structures,which is now empty*/	list_destroy(&graph->adjlists);	/*clear the structure*/	memset(graph,0,sizeof(Graph));	return ;}int graph_ins_vertex(Graph *graph,const void *data){	ListElmt *element;	AdjList	 *adjlist;	int retval;	/*do not allow the insertion of duplicate vertices*/	for(element=list_head(&graph->adjlists);element !=NULL;element=list_next(element))	{		if(graph->match(data,((AdjList *)list_data(element))->vertex))			return 1;	}	/*insert the vertex*/	if((adjlist=(AdjList *)malloc(sizeof(AdjList)))==NULL)		return -1;	adjlist->vertex=(void *)data;	set_init(&adjlist->adjacent,graph->match,NULL);	if((retval=list_ins_next(&graph->adjlists,list_tail(&graph->adjlists),adjlist))!=0)	{		return retval;	}	/*adjust the vertex count to account for the inserted vetex*/	graph->vcount++;	return 0;}int graph_ins_edge(Graph *graph,const void *data1,const void *data2){	ListElmt *element;	int retval;	/*do not allow insertion of an edge without both its vertices in the graph*/	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(data1,((AdjList *)list_data(element))->vertex))			break;		}	if(element==NULL)		return -1;	/*insert the second vertex into the adjacency list of the first vertex*/	if((retval=set_insert(&((AdjList *)list_data(element))->adjacent,data2))!=0)	{		return retval;	}	/*Adjust the edge count to account for the inserted edge*/	graph->ecount++;	return 0;}int graph_rem_vertex(Graph *graph,void **data){	ListElmt *element,*temp,*prev;	AdjList *adjlist;	int found;	/*traverse each adjacency list and the vertice it contains*/	prev=NULL;	found=0;	for(element=list_head(&graph->adjlists);element !=NULL;element=list_next(element))	{		/*do not allow removal of the vertex if it is in an adjacency list*/		if(set_is_member(&((AdjList *)list_data(element))->adjacent,*data))			return -1;		/*keep a pointer to the vertex to be removed*/		if(graph->match(*data,((AdjList *)list_data(element))->vertex))		{			temp=element;			found=1;		}		/*keep a pointer to the vertex before the vertex to be removed*/		if(!found)			prev=element;	}		/*return if the vertex was not found*/	if(!found)		return -1;	/*do not allow removal of the tex if its adjacency list is not empty*/	if(set_size(&((AdjList *)list_data(temp))->adjacent)>0)		return -1;	/*remove the vertex*/	if(list_rem_next(&graph->adjlists,prev,(void **)&adjlist)!=0)		return -1;	/*free the storage allocated by the abstract datatype*/	*data=http://www.mamicode.com/adjlist->vertex;>

 
应用实例：
后续补上