6-2 邻接表存储图的广度优先遍历 (20 分)

2023-10-08 21:29:34

6-2 邻接表存储图的广度优先遍历 (20 分)
试实现邻接表存储图的广度优先遍历。

函数接口定义：
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 <stdio.h>

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
广度遍历就是利用队列，先让第一个点入队，再对队列做循环，队列不空就出队，找这个结点的第一条边，再通过这个边找到它的邻接点，再让邻接点依次入队，它所有的邻接点都找完后就开始第二轮循环了

void BFS(LGraph Graph,Vertex S,void (*Visit)(Vertex))
{
    int queue[100];
    int front=0,rear=0;
    queue[rear++]=S;
    Visit(S);
    Visited[S]=true;//做已访问标记
    PtrToAdjVNode temp;
    while(front!=rear)
    {
        temp=Graph->G[queue[front++]].FirstEdge;//出队后找它的第一条边
        while(temp)//把这个结点所有的邻接边循环一遍
        {
            Vertex pos=temp->AdjV;//邻接点
            if(!Visited[pos])//如果这个点没被访问过的话再进队
            {
                Visit(pos);
                Visited[pos]=true;
                queue[rear++]=pos;
            }
            temp=temp->Next;
        }
    }
}

完整代码

#include<stdio.h>
#include<stdlib.h>
typedef enum{false,true}bool;
#define MaxVerNum 10
typedef int Vertex;

typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{
Vertex AdjV;
PtrToAdjVNode Next;
};

typedef struct Vnode
{
    PtrToAdjVNode FirstEdge;

}AdjList[MaxVerNum];

typedef struct GNode*PtrToGNode;
struct GNode{
int Nv;
int Ve;
AdjList G;
};
typedef PtrToGNode LGraph;

bool Visited[MaxVerNum];
LGraph CreateGraph();
LGraph CreateGraph()
{
    LGraph T;
    T=(LGraph)malloc(sizeof(struct GNode));
    int i,j,k;
    PtrToAdjVNode s;
    scanf("%d %d",&T->Nv,&T->Ve);
    for(i=0;i<T->Nv;i++)
    {
        T->G[i].FirstEdge=NULL;
        Visited[i]=false;
    }
    for(k=0;k<T->Ve;k++)
    {
        scanf("%d %d",&i,&j);
        s=(PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
        s->AdjV=j;
        s->Next=T->G[i].FirstEdge;
        T->G[i].FirstEdge=s;

         s=(PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
        s->AdjV=i;
        s->Next=T->G[j].FirstEdge;
        T->G[j].FirstEdge=s;
    }
return T;
}
void Visit(Vertex V){
               printf(" %d",V);
}
void BFS(LGraph Graph,Vertex S,void (*Visit)(Vertex));
void BFS(LGraph Graph,Vertex S,void (*Visit)(Vertex))
{
    int queue[100];
    int front=0,rear=0;
    queue[rear++]=S;
    Visit(S);
    Visited[S]=true;
    PtrToAdjVNode temp;
    while(front!=rear)
    {
        temp=Graph->G[queue[front++]].FirstEdge;
        while(temp)
        {
            Vertex pos=temp->AdjV;
            if(!Visited[pos])
            {
                Visit(pos);
                Visited[pos]=true;
                queue[rear++]=pos;
            }
            temp=temp->Next;
        }
    }
}
int main()
{
    LGraph G;
    Vertex S;
    G=CreateGraph();
    scanf("%d",&S);
    printf("BFS from %d:",S);
    BFS(G,S,Visit);
    return 0;

}

书上的广度遍历

int flag[N]=0;
void BFSTraverse(Graph *G,int v)
{InitQueue(Q);
if(!flag[v])
{EnQueue(Q,v);
flag[v]=1;
while(!QueueEmpty(Q))
{DeQueue(Q,u);
Visit(u);
for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))
if(!flag[w])
{EnQueue(Q,w);
flag[w]=1;
}
}
}
}

int FirstAdj(VNode G[],int v)
{if(G[v].firstarc!=NULL)
return (G[v].firstarc)->adjvex;
return -1;

int NextAdj(VNode G[],int v,int w)
{ArcNode*p;
p=G[v].firstarc;
while(p->adjvex!=w)//先到达w的位置
p=p->next;
if(p->next==NULL)return -1;
else p=p->next;//从w的下一条边开始
while(p!=NULL)
{if(visited[p->adjvex])p=p->next;
else return p->adjvex;
}
return -1;

#define MaxVerNum
int flag[MaxVerNum]={0};
void BFSM(MGraph*G,int i)
{int j;
int Q[MaxVerNum],front,rear;
front=0;rear=-1;
Visited(G->vexs[i]);
flag[i]=1;
rear++;
Q[rear]=i;
while(front<=rear)
{i=Q[front];front++;
for(j=0;j<G->vnum;j++)
if(G->edges[i][j]==1&&!flag[j])
{Visited(G->vexs[j]);
flag[j]=1;
rear++;
Q[rear]=j;
}
}
}

void BFSTraverseAL(MGraph*G)
{
int i;
for(i=0;i<G->vnum;i++)
if(!flag[i])
BFS(G,i);
}

码农公寓

相关文章