#include
#define ElemType char #define TRUE 1 #define FALSE 0 #define MaxVerNum 100
//邻接表的数据结构 typedef struct Node {
int adjvex; //邻接点下标
struct Node *next; //指向下一个邻接点
} EdgeNode, *ENode;
typedef struct VNode {
ElemType data; //顶点域
ENode firstedge; //边表头指针
} dataNode;
typedef dataNode AdjList[MaxVerNum];
typedef struct {
AdjList adjlist;
int n, e;
int vexnum, arcnum; //顶点数、边弧数
} AlGraph;
int visited[MaxVerNum];
typedef struct LoopQueue{
int data[MaxVerNum];
int front;
int rear;
}Queue, *LQueue;
int menu_select(); void Create(AlGraph *G); void BFSTraverse(AlGraph *G);
int main() {
int v = 0;
AlGraph *G = (AlGraph *) malloc(sizeof(AlGraph));
for (;;) {
switch (menu_select()) {
case 1:
printf("1、邻接表存储无向图的建立\n"); //建立树的函数调用
Create(G);
break;
case 2:
printf("2、邻接表存储无向图广度优先遍历\n");
BFSTraverse(G);
break;
case 0:
printf("再见！！\n");
return 0;
}
}
} // main()函数结束
//菜单驱动程序 int menu_select() {
int sn;
printf(" 基于邻接表存储无向图的广度优先遍历\n"); //显示菜单
printf("==============================\n");
printf(" 1、邻接表存储无向图的建立\n");
printf(" 2、邻接表存储无向图广度优先遍历\n");
printf(" 0、退出程序\n");
printf("==============================\n");
printf(" 请选择0--2:");
for (;;) {
scanf("%d", &sn);
getchar();
if (sn < 0 || sn > 2)
printf("\n输入选择错误，请重新选择 0--2：");
else
break;
}
return sn;
}
// 换行 void LineFeed() {
printf("\n");
}
// 数据展示 void PVisit(ElemType data) {
printf("%2c", data);
} /* 以图的邻接表表示法为存储结构建立无向图 */ void Create(AlGraph *G) {
int i, j, k;
EdgeNode *s, *r;
printf("请依次输入无向图顶点个数和边的个数\n");
scanf("%d %d", &(G->vexnum), &(G->arcnum));
getchar();
printf("请输入各顶点信息\n");
for (i = 0; i < G->vexnum; i++) {
scanf(" %c", &(G->adjlist[i].data));
getchar();
G->adjlist[i].firstedge = NULL;
}
printf("请输入各边(Vi,Vj)的信息，输入格式为i j\n");
for (k = 0; k < G->arcnum; k++) {
scanf("%d%d", &i, &j);
s = (EdgeNode *) malloc(sizeof(EdgeNode));
s->adjvex = j;
s->next = G->adjlist[i].firstedge;
G->adjlist[i].firstedge = s;
r = (EdgeNode *) malloc(sizeof(EdgeNode));
r->adjvex = i;
r->next = G->adjlist[j].firstedge;
G->adjlist[j].firstedge = r;
}
}
//初始化队列 void InitQueue(LQueue Q) {
Q->front = Q->rear = 0;
}
//判断队列是否满 int QueueisFull(LQueue Q) {
if ((Q->rear + 1) % MaxVerNum == Q->front) {
return TRUE; //已满
}
else{
return FALSE;
}
}
//判断队列是否为空 int QueueisEmpty(LQueue Q) {
if (Q->front == Q->rear) {
return TRUE;
}
return FALSE;
}
//入队列 void EnQueue(LQueue Q, int i) {
if (QueueisFull(Q) == FALSE) {
Q->data[Q->rear] = i;
Q->rear = (Q->rear + 1) % MaxVerNum;
}
}
//出队列 void DeQueue(LQueue Q, int *k) {
if (QueueisEmpty(Q) == FALSE) {
*k=Q -> data[Q -> front];
Q -> front = (Q -> front + 1) % MaxVerNum;
}
}
/*TODO: 功能描述：对邻接表表示的无向图进行广度优先遍历 1、顶点标志数组visited[]，数组存放成员TRUE，FALSE。
初始化为FALSE，其中TRUE表示已经访问过。
2、从初始位置顶点开始，遍历所有的邻接顶点并将其加入队列，
当一个顶点的所有邻接点都遍历完了之后就把该顶点出队列，
拿出下一个顶点，然后不断的重复该过程
3、遍历结束后调用换行函数 4、换行：
调用函数 void LineFeed()
数据打印：
调用函数 void PVisit(ElemType data)
参数说明：AlGraph *G 图的指针 返回值： void */ void BFSTraverse(AlGraph *G) {
int i, j;
ENode p;
Queue q;
InitQueue(&q); //初始化队列
for(i = 0;i < G->vexnum;++i){
visited[i] = FALSE; //初始化visited[]数组
}
for(i=0;i<G->vexnum;++i){ //对每个未被访问过的节点进行处理
if(!visited[i]){ //如果当前节点未被访问过
visited[i]=TRUE; //设置为已访问
EnQueue(&q,i); //入队列
while(!QueueisEmpty(&q)){ //队列非空
DeQueue(&q,&j); //出队列
PVisit(G->adjlist[j].data);//访问节点
for(p=G->adjlist[j].firstedge;p;p=p->next){//遍历邻接节点
if(!visited[p->adjvex]){ //如果当前邻接点未被访问过
visited[p->adjvex]=TRUE; //设置为已访问
EnQueue(&q,p->adjvex); //入队列
}
}
}
}
}
LineFeed();
}
