欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图的邻接表存储结构之深度优先遍历和广度优先遍历

程序员文章站 2022-05-22 09:57:32
...

前面的博客已经写了关于邻接表的源代码,下面简单讨论下邻接表存储的特点,方便下面讨论遍历的方式,

邻接表是图的一种链式存储结构,顶点表是顺序存储,每个顶点及其邻接点组成一条链表,即n个顶点共有n条链表,顶点表中每个元素是由顶点信息和指向边结点的指针组成。

深度优先遍历:代码可在之前博客的源代码下直接修改,具体如下:

//////////////////////////////////深度优先搜索遍历//////////////////////////////

void DFS(DGraph *G,int n)
{
	flag[n] = TRUE;
	printf("%s\t",G->list[n].data);

	edgenod *e = G->list[n].next;         //指向第一个邻接点
	if (e)
	{
		n = local_vex(*G, G->list[e->adjvex].data);
	}
	while ( e && flag[n] == FLASE)
	{
		n = local_vex(*G,G->list[n].data);
		DFS(G, n);
		e = e->next;
	}
}

void DFSTravers(DGraph *G)
{
	int i;
	for  (i = 0; i < G->vexnum; i++)
	{
		flag[i] = FLASE;
	}
	for ( i = 0; i < G->vexnum; i++)
	{
		if (flag[i]==FLASE)
		{
			DFS(G,i);
		}
	}
}
////////////////////////////////////////////////////////////////////////////////

广度优先遍历:代码如下,可在之前邻接表存储结构中的源代码中直接添加一下函数,手敲下代码会有不一样的收获噢:

///////////////////////////////////////////广度优先搜索遍历////////////////////、
typedef struct queuenode {
	int loc;
	queuenode *next;
}queuenode;

typedef struct {
	queuenode *first;
	queuenode *final;
}queue;

void queue_init(queue *bfsqueue)     //初始化队列
{
	queuenode *p = (queuenode *)malloc(sizeof(queuenode));
	p->loc = -1;
	p->next = NULL;

	bfsqueue->final = p;
	bfsqueue->first = p;
}

void enter_queue(queue *bfsqueue, int loc)
{
	queuenode *p = (queuenode *)malloc(sizeof(queuenode));
	p->loc = loc;
	p->next = NULL;
	bfsqueue->final->next = p;
	bfsqueue->final = p;
}
int out_queue(queue *bfsqueue)
{
	int i;
	queuenode *p;
	p = bfsqueue->first->next;
	i = p->loc;
	bfsqueue->first->next = p->next;
	if (p->next==NULL)
	{
		 bfsqueue->final=bfsqueue->first;
	}
	free(p);
	return i;	
}
int empty_queue(queue bfsqueue)
{
	if (bfsqueue.final==bfsqueue.first)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

void BFS(queue *bfsqueue,DGraph G)
{
	edgenod *p;
	queue_init(bfsqueue);
	for (int i = 0; i < G.vexnum; i++)
	{
		flag[i] = FLASE;
	}
	for (int i = 0; i < G.vexnum; i++)
	{
		if (flag[i]==FLASE)
		{
           enter_queue(bfsqueue,i);              //进入队列即需要把相应标志位置1,否则会重复进去队列
		   flag[i] = TRUE;	
            while(empty_queue(*bfsqueue))         //队列不为空时,连续出队列
			{
				int loc=out_queue(bfsqueue);      

				printf("%s\t",G.list[loc].data);  //执行相应操作

				p = G.list[loc].next;                   //出队列同时将其所有的邻接点放入队列
				while (p&& flag[p->adjvex]==FLASE)
				{
					enter_queue(bfsqueue,p->adjvex);
					flag[p->adjvex]=TRUE;
					p = p->next;
				}
			}
		}				
		
		
	}
}

       无论是邻接表存储方式,还是邻接矩阵的存储方式,其遍历方式程序结构都是相似的,主要用到基础知识有递归思想,队列的用法(实质是链表的插入和删除),基础知识的灵活运用。