采用邻接表存储结构实现图的广度优先遍历。

课程设计题目九：图的广度优先遍历

基本要求：

采用邻接表存储结构实现图的广度优先遍历。

（

2

）对任意给定的图（顶点数和边数自定）

，建立它的邻接表并输出；

（

3

）实现图的广度优先遍历

*/

#include

#include

#include

#define MAX_NUM 20

int visited[MAX_NUM]={0};

typedef int VertexType;

typedef enum {DG=1,UDG}GraphKind;

typedef struct ArcNode

{

int adjvex;

int weight;

struct ArcNode *nextarc;

ArcNode *info;

}ArcNode;

typedef struct VNode

{

VertexType data;

ArcNode *firstarc;

}VNode,AdjList[MAX_NUM];

typedef struct

{

AdjList vertices;

int vexnum,arcnum;

GraphKind kind;

}ALGraph;

void PRIN(ALGraph &G);

void Creat_adjgraph(ALGraph &G);

void bfs(ALGraph &G,int v);

void Creat_adjgraphDG(ALGraph &G);

void Creat_adjgraphUDG(ALGraph &G);

void Creat_adjgraph(ALGraph &G);

void Creat_adjgraphDG(ALGraph &G)

{

int i,s,d;

ArcNode *p=NULL,*q=NULL;=DG;

printf(

请输入顶点数和边数 ：

scanf(

for(i=0;i<;++i)

{

printf(

第

< br>%d

个顶点信息：

scanf(

es[i].firstarc=NULL;}

for(i=0;i<;++i)

{

printf(

第

< br>%d

条边的起始顶点编号和终止顶点编号：

scanf(

while(s<1||s>||d<1||d>)

{

pri ntf(

编号超出范围，重新输入

scanf(

s--;

d--;

p=new(ArcNode);

p->adjvex=d;

p->nextarc=es[s].firstarc;

es[s].firstarc=p;

}

}

void Creat_adjgraphUDG(ALGraph &G)

{

int i,s,d;

ArcNode *p,*q;

=UDG;

printf(

请输入顶点数和边数：

scanf(

for(i=0;i<;++i)

{

printf(

第

< br>%d

个顶点信息：

scanf(

es[i].firstarc=NULL;}

for(i=0;i<;++i)

{

printf(

第

< br>%d

条边的起始顶点编号和终止顶点编号：

scanf(

while(s<1||s>||d<1||d>)

{

pri ntf(

编号超出范围，重新输入

scanf(

s--;