邻接表BFS

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 #define MaxSize 20
  5 
  6 typedef struct ArcNode{            //边表结点 
  7     struct ArcNode *next;
  8     int adjvex;
  9 }ArcNode;
 10 
 11 typedef struct VNode{            //主表结点 
 12     int data;
 13     ArcNode *first;
 14 }VNode,AdjList[MaxSize];
 15 
 16 typedef struct{                    //图 
 17     AdjList Ver;
 18     int VerNum,EdgeNum;
 19 }Graph;
 20 
 21 typedef struct{
 22     ArcNode *data[MaxSize];
 23     int front,rear;
 24 }Queue;
 25 
 26 void InitQueue(Queue &Q)
 27 {
 28     Q.front=Q.rear=0;
 29 }
 30 
 31 bool isEmpty(Queue Q)
 32 {
 33     if(Q.rear==Q.front)
 34         return true;
 35     return false;
 36 }
 37 
 38 bool isFull(Queue Q)
 39 {
 40     if((Q.rear+1)%MaxSize==Q.front)
 41         return true;
 42     return false;
 43 }
 44 
 45 bool EnQueue(Queue &Q,ArcNode *arcnode)
 46 {
 47     if(isFull(Q))
 48         return false; 
 49     Q.data[Q.rear]=arcnode;
 50     Q.rear=(Q.rear+1)%MaxSize;
 51     return true;
 52 }
 53 
 54 bool DeQueue(Queue &Q,ArcNode* &arcnode)
 55 {
 56     if(isEmpty(Q))
 57         return false;
 58     arcnode=Q.data[Q.front];
 59     Q.front=(Q.front+1)%MaxSize;
 60     return true;
 61 }
 62 
 63 void CreateGraph(Graph &G)
 64 {
 65     int x,i,j;
 66     printf("请输入顶点元素:\n");
 67     for(i=0;i<MaxSize;i++)
 68     {
 69         scanf("%d",&x);
 70         if(x==-1)
 71             break;
 72         G.Ver[i].data=x;
 73         G.Ver[i].first=NULL;
 74         G.VerNum++;
 75     }
 76     
 77     printf("请输入边表:\n"); 
 78     for(i=0;i<G.VerNum;i++)
 79     {
 80         ArcNode *p=G.Ver[i].first;
 81         for(j=0;j<G.VerNum;j++)        //有向图顶点可以指向自己 
 82         {
 83             scanf("%d",&x);
 84             if(x==-1)
 85                 break;
 86             ArcNode *arcnode=(ArcNode*)malloc(sizeof(ArcNode));
 87             arcnode->adjvex=x;
 88             arcnode->next=G.Ver[i].first;
 89             G.Ver[i].first=arcnode;
 90             G.EdgeNum++; 
 91         }
 92     }
 93 }
 94 
 95 void DisplayGraph(Graph G)
 96 {
 97     int i,j;
 98     printf("顶点元素为:\n");
 99     for(i=0;i<G.VerNum;i++)
100         G.Ver[i].data;
101     
102     printf("边为:\n");
103     for(i=0;i<G.VerNum;i++)
104     {
105         printf("%d->",G.Ver[i].data);
106         ArcNode *arc=G.Ver[i].first;
107         while(arc!=NULL)
108         {
109             printf("%d  ",arc->adjvex);
110             arc=arc->next;
111         }
112         printf("\n");
113     }
114     
115     printf("顶点元素共有%d个\n",G.VerNum);
116     printf("边有%d条\n",G.EdgeNum); 
117 }
118 
119 
120 int ArrNum(Graph G,int ver)
121 {
122     for(int i=0;i<G.VerNum;i++)
123         if(G.Ver[i].data==ver)
124                 return i;
125     return -1;
126 }
127 
128 int FirstNeighbor(Graph G,int ver)
129 {
130     int x=ArrNum(G,ver);
131     if(x!=-1 && G.Ver[x].first!=NULL)
132         return ArrNum(G,G.Ver[x].first->adjvex);
133     return -1;
134 }
135 
136 int NextNeighbor(Graph G,int ver,int w)
137 {
138     int x=ArrNum(G,ver);
139     ArcNode *arcnode=G.Ver[x].first;
140     while(arcnode!=NULL && arcnode->adjvex!=w)
141         arcnode=arcnode->next;
142     if(arcnode->next!=NULL)
143         return ArrNum(G,arcnode->next->adjvex);
144     return -1;
145 }
146 
147 bool visited[MaxSize];
148 void BFS(Graph G,int v)
149 {
150     printf("%d ", G.Ver[v].data);
151     Queue Q;
152     InitQueue(Q);
153     EnQueue(Q, G.Ver[v].first);
154     visited[v] = true;
155     while (!isEmpty(Q))
156     {
157         ArcNode* arcnode;
158         DeQueue(Q, arcnode);
159         while (arcnode != NULL)
160         {
161             int i = ArrNum(G,arcnode->adjvex);
162             if (!visited[i])
163             {
164                 printf("%d ", G.Ver[i].data);
165                 EnQueue(Q, G.Ver[i].first);
166                 visited[i] = true;
167             }
168             arcnode = arcnode->anext;
169         }
170     }
171 }
172 
173 void BFSTraverse(Graph G)
174 {
175     for(int i=0;i<G.VerNum;i++)
176         visited[i]=false;
177     for(int i=0;i<G.VerNum;i++)
178         if(!visited[i])
179             BFS(G,i);
180 }
181 
182 int main()
183 {
184     Graph G;
185     CreateGraph(G);
186     DisplayGraph(G);
187     BFSTraverse(G);
188     
189     return 0;    
190 }