ZBLOG

#include #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 {...

#include #include

#define ElemType char #define TRUE 1 #define FALSE 0 #define MaxVerNum 100

//邻接表的数据结构 typedef struct Node {

  1. int adjvex; //邻接点下标
  2. struct Node *next; //指向下一个邻接点

} EdgeNode, *ENode;

typedef struct VNode {

  1. ElemType data; //顶点域
  2. ENode firstedge; //边表头指针

} dataNode;

typedef dataNode AdjList[MaxVerNum];

typedef struct {

  1. AdjList adjlist;
  2. int n, e;
  3. int vexnum, arcnum; //顶点数、边弧数

} AlGraph;

int visited[MaxVerNum];

typedef struct LoopQueue{

  1. int data[MaxVerNum];
  2. int front;
  3. int rear;

}Queue, *LQueue;

int menu_select(); void Create(AlGraph *G); void BFSTraverse(AlGraph *G);

int main() {

  1. int v = 0;
  2. AlGraph *G = (AlGraph *) malloc(sizeof(AlGraph));
  3. for (;;) {
  4. switch (menu_select()) {
  5. case 1:
  6. printf("1、邻接表存储无向图的建立\n"); //建立树的函数调用
  7. Create(G);
  8. break;
  9. case 2:
  10. printf("2、邻接表存储无向图广度优先遍历\n");
  11. BFSTraverse(G);
  12. break;
  13. case 0:
  14. printf("再见!!\n");
  15. return 0;
  16. }
  17. }

} // main()函数结束

//菜单驱动程序 int menu_select() {

  1. int sn;
  2. printf(" 基于邻接表存储无向图的广度优先遍历\n"); //显示菜单
  3. printf("==============================\n");
  4. printf(" 1、邻接表存储无向图的建立\n");
  5. printf(" 2、邻接表存储无向图广度优先遍历\n");
  6. printf(" 0、退出程序\n");
  7. printf("==============================\n");
  8. printf(" 请选择0--2:");
  9. for (;;) {
  10. scanf("%d", &sn);
  11. getchar();
  12. if (sn < 0 || sn > 2)
  13. printf("\n输入选择错误,请重新选择 0--2:");
  14. else
  15. break;
  16. }
  17. return sn;

}

// 换行 void LineFeed() {

  1. printf("\n");

}

// 数据展示 void PVisit(ElemType data) {

  1. printf("%2c", data);

} /* 以图的邻接表表示法为存储结构建立无向图 */ void Create(AlGraph *G) {

  1. int i, j, k;
  2. EdgeNode *s, *r;
  3. printf("请依次输入无向图顶点个数和边的个数\n");
  4. scanf("%d %d", &(G->vexnum), &(G->arcnum));
  5. getchar();
  6. printf("请输入各顶点信息\n");
  7. for (i = 0; i < G->vexnum; i++) {
  8. scanf(" %c", &(G->adjlist[i].data));
  9. getchar();
  10. G->adjlist[i].firstedge = NULL;
  11. }
  12. printf("请输入各边(Vi,Vj)的信息,输入格式为i j\n");
  13. for (k = 0; k < G->arcnum; k++) {
  14. scanf("%d%d", &i, &j);
  15. s = (EdgeNode *) malloc(sizeof(EdgeNode));
  16. s->adjvex = j;
  17. s->next = G->adjlist[i].firstedge;
  18. G->adjlist[i].firstedge = s;
  19. r = (EdgeNode *) malloc(sizeof(EdgeNode));
  20. r->adjvex = i;
  21. r->next = G->adjlist[j].firstedge;
  22. G->adjlist[j].firstedge = r;
  23. }

}

//初始化队列 void InitQueue(LQueue Q) {

  1. Q->front = Q->rear = 0;

}

//判断队列是否满 int QueueisFull(LQueue Q) {

  1. if ((Q->rear + 1) % MaxVerNum == Q->front) {
  2. return TRUE; //已满
  3. }
  4. else{
  5. return FALSE;
  6. }

}

//判断队列是否为空 int QueueisEmpty(LQueue Q) {

  1. if (Q->front == Q->rear) {
  2. return TRUE;
  3. }
  4. return FALSE;

}

//入队列 void EnQueue(LQueue Q, int i) {

  1. if (QueueisFull(Q) == FALSE) {
  2. Q->data[Q->rear] = i;
  3. Q->rear = (Q->rear + 1) % MaxVerNum;
  4. }

}

//出队列 void DeQueue(LQueue Q, int *k) {

  1. if (QueueisEmpty(Q) == FALSE) {
  2. *k=Q -> data[Q -> front];
  3. Q -> front = (Q -> front + 1) % MaxVerNum;
  4. }

}

/*TODO: 功能描述:对邻接表表示的无向图进行广度优先遍历 1、顶点标志数组visited[],数组存放成员TRUE,FALSE。

  1. 初始化为FALSE,其中TRUE表示已经访问过。

2、从初始位置顶点开始,遍历所有的邻接顶点并将其加入队列,

  1. 当一个顶点的所有邻接点都遍历完了之后就把该顶点出队列,
  2. 拿出下一个顶点,然后不断的重复该过程

3、遍历结束后调用换行函数 4、换行:

  1. 调用函数 void LineFeed()
  2. 数据打印:
  3. 调用函数 void PVisit(ElemType data)

参数说明:AlGraph *G 图的指针 返回值: void */ void BFSTraverse(AlGraph *G) {

  1. int i, j;
  2. ENode p;
  3. Queue q;
  4. InitQueue(&q); //初始化队列
  5. for(i = 0;i < G->vexnum;++i){
  6. visited[i] = FALSE; //初始化visited[]数组
  7. }
  8. for(i=0;i<G->vexnum;++i){ //对每个未被访问过的节点进行处理
  9. if(!visited[i]){ //如果当前节点未被访问过
  10. visited[i]=TRUE; //设置为已访问
  11. EnQueue(&q,i); //入队列
  12. while(!QueueisEmpty(&q)){ //队列非空
  13. DeQueue(&q,&j); //出队列
  14. PVisit(G->adjlist[j].data);//访问节点
  15. for(p=G->adjlist[j].firstedge;p;p=p->next){//遍历邻接节点
  16. if(!visited[p->adjvex]){ //如果当前邻接点未被访问过
  17. visited[p->adjvex]=TRUE; //设置为已访问
  18. EnQueue(&q,p->adjvex); //入队列
  19. }
  20. }
  21. }
  22. }
  23. }
  24. LineFeed();

}

本站部分文章来源于网络,版权归原作者所有,如有侵权请联系站长删除。
转载请注明出处:https://golang.0voice.com/?id=5181

分享:
扫描分享到社交APP
上一篇
下一篇
发表列表
游客 游客
此处应有掌声~
评论列表

还没有评论,快来说点什么吧~

联系我们

在线咨询: 点击这里给我发消息

微信号:3007537140

上班时间: 10:30-22:30

关注我们
x

注册

已经有帐号?