基于图（graph）的应用举例
1、统计网络跳数 图在解决许多与网络相关的问题时起到了重要的作用，统计在internet中从一个节点访问其他节点时中间必须经过的最小的节点数，这个消息在internet中非常有用，因为最明显的网络开销直接和所要的遍历的节点数目相关。 下面是采用BFS实现计算网络跳数，使用了前面提供的队列及链表的函数接口。在阅读中希望先把链表和队列的相关的函数接口了解下。
/*bfs.c*/#include <stdlib.h>#include "../include/bfs.h"#include "../include/graph.h"#include "../include/list.h"#include "../include/queue.h"/*********************************************** *广度优先搜索方法实现网络中两个节点之间的跳数 *参数：graph:代表整个网络 * start:代表起始的顶点 * hops:返回的跳数链表 *返回值：成功返回0，失败-1 * *************************************************/int bfs(Graph *graph,BfsVertex *start,List *hops){ Queue queue; Adjlist *adjlist, *clr_adjlist; BfsVertex *clr_vertex, *adj_verex; ListElmt *element, *member; /*初始化图中所有的节点 *当节点是起始节点vstart时，初始化成黑色，跳数为0； *其他初始化位白色，跳数为-1. * */ for (element = list_head(graph->adjlists);element != NULL;element = list_next(element)){ clr_vertex = ((Adjlist *)list_data(element))->vertex; if (graph->match(clr_vertex,start)){ clr_vertex->color = gray; clr_vertex->hops = 0; } else { clr_vertex->color = gray; clr_vertex->hops = 0; } } /*初始化队列*/ queue_init(&queue,NULL); /*获得开始顶点的结构体，并加入到队列中*/ if (graph_adjlit(graph,start,&clr_adjlist) != 0){ queue_destroy(&queue); return -1; } if (queue_enqueue(&queue,clr_adjlist) != 0){ queue_destroy(&queue); return -1; } /*BFS*/ while (queue_size(&queue) > 0){ /*得到队列中的首个节点元素*/ adjlist = queue_peek(&queue); /*以此获得当前顶点的邻接顶点，并着色，和设置跳数*/ for (member = list_head(&adjlist->adjacent);member != NULL; member = list_next(member)){ /*获得顶点*/ adj_verex = list_data(member); /*获得当前顶点的adjlist结构体*/ if (graph_adjlit(graph,adj_verex,&clr_adjlist) != 0){ queue_destroy(&queue); return -1; } clr_vertex = clr_adjlist -> vertex; /*设定顶点的颜色及跳数*/ if (clr_vertex ->color == while ){ clr_vertex -> color = gray; clr_vertex -> hops = ((BfsVertex *)adjlist -> vertex)->hops + 1; /*将当前顶点的adjlist 结构体加入队列*/ if (queue_enqueue (&queue,clr_adjlist) != 0){ queue_destroy(&queue); return -1; } } } /*在队列中将首个元素删除*/ if (queue_dequeue (&queue, (void **)&adjlist) == 0) ((BfsVertex *)adjlist->vertex)->color = black; else { queue_destroy (&queue); return -1; } } /*以上已经将图的所有节点的跳数都已经加载上*/ queue_destroy(&queue); /*下面室将所有跳数不为-1的顶点，保存到链表hops中*/ list_init(hops,NULL); for (member = list_head(&adjlist->adjacent);member != NULL; member = list_next(member)){ clr_vertex = ((Adjlist *)list_data(element)) -> vertex; if (clr_vertex->hops != -1 ){ if (list_ins_next(hops,list_tail(hops),clr_vertex) != 0){ list_destroy(hops); return -1; } } } return 0;}