本文共 2326 字，大约阅读时间需要 7 分钟。

试实现邻接表存储图的广度优先遍历。

函数接口定义：

void BFS ( LGraph Graph, Vertex S, void (*Visit)(Vertex) );

其中LGraph是邻接表存储的图，定义如下：

/* 邻接点的定义 */typedef struct AdjVNode *PtrToAdjVNode; struct AdjVNode{    Vertex AdjV;        /* 邻接点下标 */    PtrToAdjVNode Next; /* 指向下一个邻接点的指针 */};/* 顶点表头结点的定义 */typedef struct Vnode{    PtrToAdjVNode FirstEdge; /* 边表头指针 */} AdjList[MaxVertexNum];     /* AdjList是邻接表类型 *//* 图结点的定义 */typedef struct GNode *PtrToGNode;struct GNode{      int Nv;     /* 顶点数 */    int Ne;     /* 边数   */    AdjList G;  /* 邻接表 */};typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */

函数BFS应从第S个顶点出发对邻接表存储的图Graph进行广度优先搜索，遍历时用裁判定义的函数Visit访问每个顶点。当访问邻接点时，要求按邻接表顺序访问。题目保证S是图中的合法顶点。

裁判测试程序样例：

#include 
   
    typedef enum {false, true} bool;#define MaxVertexNum 10   /* 最大顶点数设为10 */typedef int Vertex;       /* 用顶点下标表示顶点,为整型 *//* 邻接点的定义 */typedef struct AdjVNode *PtrToAdjVNode; struct AdjVNode{    Vertex AdjV;        /* 邻接点下标 */    PtrToAdjVNode Next; /* 指向下一个邻接点的指针 */};/* 顶点表头结点的定义 */typedef struct Vnode{    PtrToAdjVNode FirstEdge; /* 边表头指针 */} AdjList[MaxVertexNum];     /* AdjList是邻接表类型 *//* 图结点的定义 */typedef struct GNode *PtrToGNode;struct GNode{      int Nv;     /* 顶点数 */    int Ne;     /* 边数   */    AdjList G;  /* 邻接表 */};typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */bool Visited[MaxVertexNum]; /* 顶点的访问标记 */LGraph CreateGraph(); /* 创建图并且将Visited初始化为false；裁判实现，细节不表 */void Visit( Vertex V ){    printf(" %d", V);}void BFS ( LGraph Graph, Vertex S, void (*Visit)(Vertex) );int main(){    LGraph G;    Vertex S;    G = CreateGraph();    scanf("%d", &S);    printf("BFS from %d:", S);    BFS(G, S, Visit);    return 0;}
   

/* 你的代码将被嵌在这里 */

2

输出样例：

BFS from 2: 2 0 3 5 4 1 6

这个题，自己效率很低。原因如下：

1. 关于邻接表的存储。自己先想，到底是节点大的在前，还是小的在前。想一下题目要求先输出小的节点，于是就是小的节点在前。如果是大的在前，那岂不是找茬？而且也实现不了。
2. 还有就是这个题明显用队列。我就想，为啥这题没有给队列的定义?难道是不用队列？想想，还是得用，所以需要自己手打。
3. 最后就是那个数组AdjList[MaxVertexNum]，引用元素要AdjList[i].FirstEdge,是一个点，而不是->。还有FirstEdge是保存节点的，而不是指向下一个有效节点。

void BFS ( LGraph Graph, Vertex S, void (*Visit)(Vertex) ){//s起始点， 		PtrToAdjVNode p;	Visit(S);	Visited[S]=true;	int queue[10000]={0};	int front,rear;	front=rear=0;	queue[rear++]=S;//简单队列	while(front
   
    G[queue[front++]].FirstEdge;		//若 写成.FirstEdge->Next,段错误。		while(p)		{			if(Visited[p->AdjV]==false)			{				Visit(p->AdjV);				Visited[p->AdjV]=true;				queue[rear++]=p->AdjV;			}			p=p->Next;		}	}}
   

转载地址：http://nlkwi.baihongyu.com/