图的深度优先和广度优先遍历(图以邻接表表示，由C++面向对象实现）

学习了图的深度优先和广度优先遍历，发现不管是教材还是网上，大都为C语言函数式实现，为了加深理解，我以C＋＋面向对象的方式把图的深度优先和广度优先遍历重写了一遍。

废话不多说，直接上代码：

1 #include<iostream>   2    3 using namespace std;   4    5    6 //构造一个循环队列来存放广度优先算法的下标   7    8 #define ADD 5;   9   10 using namespace std;  11   12 class CirQueue  13 {  14 private:  15     int * base;  16     int front,rear,size,length;  17 public:  18     bool InitCirQueue(int size)  19     {  20         this->size=size;  21         base=new int[size];  22         if(!base)  23         {  24             return false;  25         }  26         front=rear=length=0;  27         return true;  28     }  29     bool insertQueue(int num)  30     {  31         if(length==size)  32         {  33             int newsize=size+ADD;  34             int * newbase=new int[newsize];  35             if(!newbase)  36             {  37                 return false;  38             }  39             int i=0;  40             for(i=0;i<length;i++)  41             {  42                 newbase[(front+i)%newsize]=base[(front+i)%size];  43             }  44             rear=(front+i)%newsize;  45             base=newbase;  46             size=newsize;  47         }  48         base[rear]=num;  49         rear=(rear+1)%size;  50         ++length;  51         return true;  52     }  53     int outQueue()  54     {  55         int temp=base[front];  56         front=(front+1)%size;  57         --length;  58         return temp;  59     }  60     void traverseQueue()  61     {  62         for(int i=0;i<length;i++)  63         {  64             cout<<base[(front+i)%size]<<endl;  65         }  66     }  67     int getLength()  68     {  69         return length;  70     }  71     bool isEmpty()  72     {  73         if(0==length)  74         {  75             return true;  76         }  77         else  78         {  79             return false;  80         }  81     }  82     bool isFull()  83     {  84         if(length==size)  85         {  86             return true;  87         }  88         else  89         {  90             return false;  91         }  92     }  93 };  94   95 // void main()  96 // {  97 //     CirQueue cq;  98 //     cq.InitCirQueue(5);  99 //     for(int i=1;i<=100;i++) 100 //     { 101 //         cq.insertQueue(i); 102 //     } 103 //     cq.traverseQueue(); 104 // } 105  106 //构造循环队列结束 107  108 struct Arc 109 { 110     int adjvex; 111     Arc * next; 112 }; 113  114 struct Vertex 115 { 116     char data; 117     Arc * firstarc; 118 }; 119  120 class Map 121 { 122 private: 123     Vertex * vexList; 124     int vexNum; 125     int arcNum; 126     bool * visted; 127 public: 128     Map(int vexNum,int arcNum) 129     { 130         this->vexNum=vexNum; 131         this->arcNum=arcNum; 132         visted=new bool[vexNum]; 133         for(int i=0;i<vexNum;i++) 134         { 135             visted[i]=false; 136         } 137         vexList=new Vertex[vexNum]; 138         for(int i=0;i<vexNum;i++) 139         { 140             cout<<"请输入第"<<i<<"个顶点的数据:"; 141             cin>>vexList[i].data; 142             vexList[i].firstarc=NULL; 143         } 144         for(int i=0;i<arcNum;i++) 145         { 146             int a,b; 147             cout<<"请输入第"<<i+1<<"条边的两顶点"; 148             cin>>a>>b; 149              150             Arc * tempArc=new Arc; 151             tempArc->adjvex=b; 152             tempArc->next=vexList[a].firstarc; 153             vexList[a].firstarc=tempArc; 154              155             //因为是无向图所以是双向的 156             tempArc=new Arc; 157             tempArc->adjvex=a; 158             tempArc->next=vexList[b].firstarc; 159             vexList[b].firstarc=tempArc; 160         } 161     } 162     void DFS(int v) 163     { 164         cout<<vexList[v].data<<endl; 165         visted[v]=true; 166         Arc * p=vexList[v].firstarc; 167         while(p) 168         { 169             int u=p->adjvex; 170             if(!visted[u]) 171             { 172                 DFS(u); 173             } 174             p=p->next; 175         } 176     } 177     void BFS(int v) 178     { 179         CirQueue cq; 180         cq.InitCirQueue(5); 181         cout<<vexList[v].data<<endl; 182         visted[v]=true; 183         cq.insertQueue(v); 184         while(!cq.isEmpty()) 185         { 186             v=cq.outQueue(); 187             Arc * p=vexList[v].firstarc; 188             while(p) 189             { 190                 int j=p->adjvex; 191                 if(!visted[j]) 192                 { 193                     cout<<vexList[j].data<<endl; 194                     visted[j]=true; 195                     cq.insertQueue(j); 196                 } 197                 p=p->next; 198             } 199         } 200     } 201     void ClearVisted() 202     { 203         for(int i=0;i<vexNum;i++) 204         { 205             visted[i]=false; 206         } 207     } 208 }; 209  210 int main() 211 { 212     Map map(3,3); 213     cout<<"--------------深度优先遍历————————————————"<<endl; 214     map.DFS(0); 215     map.ClearVisted(); 216     cout<<"--------------广度优先遍历————————————————"<<endl; 217     map.BFS(0); 218     return 0; 219 }

运行结果为：