图的广度优先遍历和深度优先遍历

图是一种很重要的数据结构，在我们的编程生活中应用极其广泛
  1 #include <iostream>
  2 using namespace std;
  3 #define INFINITY 32767
  4 #define MAX_VEX 20 //最大顶点个数
  5 #define QUEUE_SIZE (MAX_VEX+1) //队列长度
  6 
  7 bool *visited;  //访问标志数组
  8 //图的邻接矩阵存储结构
  9 typedef struct
 10 {
 11     char *vexs; //顶点向量
 12     int arcs[MAX_VEX][MAX_VEX]; //邻接矩阵
 13     int vexnum,arcnum; //图的当前顶点数和弧数
 14 }Graph;
 15 //队列类
 16 class Queue{
 17 public:
 18     void InitQueue()
 19     {
 20         base=(int *)malloc(QUEUE_SIZE*sizeof(int));
 21         front=rear=0;
 22     }
 23     void EnQueue(int e)
 24     {
 25         base[rear]=e;
 26         rear=(rear+1)%QUEUE_SIZE;
 27     }
 28     void DeQueue(int &e)
 29     {
 30         e=base[front];
 31         front=(front+1)%QUEUE_SIZE;
 32     }
 33 public:
 34     int *base;
 35     int front;
 36     int rear;
 37 };
 38 
 39 
 40 //图G中查找元素c的位置
 41 int Locate(Graph G,char c)
 42 {
 43     for(int i=0;i<G.vexnum;i++)
 44         if(G.vexs[i]==c) 
 45             return i;
 46     return -1;
 47 }
 48 
 49 
 50 //创建无向网
 51 void CreateUDN(Graph &G)
 52 {
 53     int i,j,w,s1,s2;
 54     char a,b,temp;
 55     cout<<"输入顶点数和弧数:";
 56     cin>>G.vexnum>>G.arcnum;
 57     G.vexs=(char *)malloc(G.vexnum*sizeof(char)); //分配顶点数目
 58     cout<<"输入"<<G.vexnum<<"个顶点."<<endl;
 59     for(i=0;i<G.vexnum;i++)
 60     { 
 61         //初始化顶点
 62         cout<<"输入顶点"<<i+1<<":";
 63         cin>>G.vexs[i];
 64     }
 65     for(i=0;i<G.vexnum;i++) //初始化邻接矩阵
 66         for(j=0;j<G.vexnum;j++)
 67             G.arcs[i][j]=INFINITY;
 68     cout<<"输入"<<G.arcnum<<"条弧."<<endl;
 69     for(i=0;i<G.arcnum;i++)
 70     { 
 71         //初始化弧
 72         cout<<"输入弧"<<i+1<<":";
 73         cin>>a>>b>>w; //输入一条边依附的顶点和权值
 74         s1=Locate(G,a);
 75         s2=Locate(G,b);
 76         G.arcs[s1][s2]=G.arcs[s2][s1]=w;
 77     }
 78 }
 79 
 80 
 81 //图G中顶点k的第一个邻接顶点
 82 int FirstVex(Graph G,int k)
 83 {
 84     if(k>=0 && k<G.vexnum)
 85     { 
 86         //k合理
 87         for(int i=0;i<G.vexnum;i++)
 88             if(G.arcs[k][i]!=INFINITY) 
 89                 return i;
 90     }
 91     return -1;
 92 }
 93 
 94 
 95 //图G中顶点i的第j个邻接顶点的下一个邻接顶点
 96 int NextVex(Graph G,int i,int j)
 97 {
 98     if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum)
 99     { 
100         //i,j合理
101         for(int k=j+1;k<G.vexnum;k++)
102             if(G.arcs[i][k]!=INFINITY) 
103                 return k;
104     }
105     return -1;
106 }
107 
108 
109 //深度优先遍历
110 void DFS(Graph G,int k)
111 {
112     int i;
113     if(k==-1)
114     { 
115         //第一次执行DFS时,k为-1
116         for(i=0;i<G.vexnum;i++)
117             if(!visited[i]) 
118                 DFS(G,i); //对尚未访问的顶点调用DFS
119     }
120     else
121     {
122         visited[k]=true;
123         cout<<G.vexs[k]; //访问第k个顶点
124         for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))
125             if(!visited[i]) 
126                 DFS(G,i); //对k的尚未访问的邻接顶点i递归调用DFS
127     }
128 }
129 
130 
131 //广度优先遍历
132 void BFS(Graph G){
133     int k;
134     Queue Q; //辅助队列Q
135     Q.InitQueue();
136     for(int i=0;i<G.vexnum;i++)
137         if(!visited[i])
138         { 
139             //i尚未访问
140             visited[i]=true;
141             cout<<G.vexs[i];
142             Q.EnQueue(i); //i入列
143             while(Q.front!=Q.rear)
144             {
145                 Q.DeQueue(k); //队头元素出列并置为k
146                 for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w))
147                     if(!visited[w])
148                     { 
149                         //w为k的尚未访问的邻接顶点
150                         visited[w]=true;
151                         cout<<G.vexs[w];
152                         Q.EnQueue(w);
153                     }
154             }
155         }
156 }
157 
158 
159 //主函数
160 int main()
161 {
162     int i;
163     Graph G;
164     CreateUDN(G);
165     visited=(bool *)malloc(G.vexnum*sizeof(bool));
166     cout<<"深度优先遍历: ";
167     for(i=0;i<G.vexnum;i++)
168         visited[i]=false;
169     DFS(G,-1);
170     cout<<"
广度优先遍历: ";
171     for(i=0;i<G.vexnum;i++)
172         visited[i]=false;
173     BFS(G);
174     system("pause");
175     return 0;
176 }
作者：耑新新，发布于博客园
转载请注明出处，欢迎邮件交流：zhuanxinxin@aliyun.com