邻接矩阵实现的广度优先搜索

朴灿烈づ我的快乐病毒、 2022-09-18 11:59 157阅读 0赞

\#include <stdio.h>  
\#include <stdlib.h>  
\#include <string.h>

//循环队列最多  
\#define MAXSIZE 100  
//定义循环队列的数据结构  
typedef struct  
\{  
 int rear;  
 int front;  
 int data\[MAXSIZE\];  
\}Queue;

bool QueueEmpty(Queue \*Q)  
\{  
 if(Q->rear == Q->front)  
  return true;  
 return false;  
\}

void InitQueue(Queue \*Q)  
\{  
 Q->front = 0;  
 Q->rear = 0;  
\}

bool EnQueue(Queue \*Q,int e)  
\{  
 if(Q->front == (Q->rear+1)%MAXSIZE)  
  return false;  
 Q->data\[Q->rear\] = e;  
 Q->rear = (Q->rear+1)%(MAXSIZE);  
 return true;  
\}

bool DeQueue(Queue \*Q,int \*e)  
\{  
 if(Q->front == Q->rear)  
  return false;  
 \*e = Q->data\[Q->front\];  
 Q->front = (Q->front+1)%MAXSIZE;  
 return true;  
\}

typedef char VertexType;   //顶点的数据类型  
typedef int EdgeType;     //边的权值数据类型

\#define MAXVEX 100        //最多的边的数目  
\#define INFINITY 65535

typedef struct  
\{  
 int numVexs,numEdges;  
 EdgeType arc\[MAXVEX\]\[MAXVEX\];  
 VertexType vexs\[MAXVEX\];  
\}MGraph;                 //图的邻接矩阵的数据结构

bool visited\[MAXVEX\];    //指向图的顶点有没有访问过

//创建无向无权图  
bool CreateMGraph(MGraph \*G)  
\{  
 int i,j,k;  
 printf("请输入图的边数目:");  
 scanf("%d",&G->numEdges);  
 putchar('\\n');  
 printf("请输入图的顶点数目:");  
 scanf("%d",&G->numVexs);  
 getchar();  
 putchar('\\n');  
 printf("请输入顶点信息\\n");  
 for(i=0;i<G->numVexs;i++)  
 \{  
  printf("请输入第%d个顶点信息:",i+1);  
  scanf("%c",&G->vexs\[i\]);  
  getchar();  
  putchar('\\n');  
 \}  
 printf("请输入边的信息,例如vi,vj表示vi下标到vj下表的边\\n");  
 for(k=0;k<G->numEdges;k++)  
 \{  
  printf("请输入第%d条边的信息:",k+1);  
  scanf("%d,%d",&i,&j);  
  putchar('\\n');  
  G->arc\[i\]\[j\] = 1;  
  G->arc\[j\]\[i\] = 1;  
 \}  
 return 1;  
\}

//深度优先搜索  
void BFSTraverse(MGraph \*G)  
\{  
 int i,j,temp;  
 Queue Q;  
 //初始化标志有没有访问过的数组  
 for(i=0;i<G->numVexs;i++)  
  visited\[i\] = false;  
 //初始化队列  
 InitQueue(&Q);  
 //逐个进行深度优先搜索  
 for(i=0;i<G->numVexs;i++)  
 \{  
  //如果没有访问过  
  if(!visited\[i\])  
  \{  
   //先标记在访问  
   visited\[i\] = true;  
   printf("%c->",G->vexs\[i\]);  
   //入队  
   EnQueue(&Q,i);  
   while(!QueueEmpty(&Q))  
   \{  
    DeQueue(&Q,&temp);  
    //将和这个顶点相连的所有定点入队  
    for(j=0;j<G->numVexs;j++)  
    \{  
     if(G->arc\[temp\]\[j\] && !visited\[j\])  
     \{  
      visited\[j\] = true;  
      printf("%c",G->vexs\[j\]);  
      EnQueue(&Q,j);  
     \}  
    \}  
   \}  
  \}  
 \}  
\}

int main()  
\{  
 MGraph G;  
 CreateMGraph(&G);  
 BFSTraverse(&G);  
 return 0;  
\}