图的邻接表存储结构之深度优先遍历和广度优先遍历
程序员文章站
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;
}
}
}
}
}
无论是邻接表存储方式,还是邻接矩阵的存储方式,其遍历方式程序结构都是相似的,主要用到基础知识有递归思想,队列的用法(实质是链表的插入和删除),基础知识的灵活运用。
上一篇: ACM入门题(一)
推荐阅读
-
【数据结构】图的遍历——深度优先搜索DFS、广度优先搜索BFS
-
数据结构与算法————图的遍历DFS深度优先搜索和BFS广度优先搜索
-
(浙大-19-夏-数据结构学习笔记+代码)图的遍历+深度优先+广度优先(Graph)
-
图的遍历---广度优先遍历和深度优先遍历
-
[PHP] 算法-邻接矩阵图的广度和深度优先遍历的PHP实现
-
实验3.4:以邻接表为存储结构的图的深度、宽度优先遍历
-
实验3.2:以邻接矩阵为存储结构的图的深度、宽度优先遍历
-
邻接表为存储结构 | 实现图的深度、宽度优先遍历
-
数据结构(图)——简单无向图的邻接矩阵,实现广度优先遍历
-
数据结构之图:邻接矩阵和邻接表、深度优先遍历和广度优先遍历