实验四图的遍历算法设计与实现

一、实验名称：图的遍历算法设计与实现

二、实验目的：

1.掌握图的深度优先遍历的算法。

2.掌握图的广度优先遍历的算法。

3.实验章节：算法设计与分析第四章

三、实验内容。实验问题和程序运行结果

第一部分广度优先遍历算法

完善下列程序，并回答问题。

  1 #include <iostream.h>
  2 #define QSize 30
  3 template<class T>  //队列
  4 class Queue
  5 {
  6 public:
  7     Queue(){data = new T[30]; Qsize = 30;InitQueue();};
  8     Queue(int size){Qsize = size; data = new T[Qsize];InitQueue();};
  9     void InitQueue(){            //初始化队列
 10         front = rear = 0;
 11     };
 12     void Append(T e){            //入队操作
 13         if((rear+1)%Qsize==front) cout<<"队列已满";
 14         else 
 15         {
 16             data[rear]=e;
 17             rear=(rear+1)%Qsize;
 18          }
 19     };
 20     T Front(){        //出对操作
 21         if(IsEmpty())  return -1;
 22         T e =data[front];
 23         front=(front+1)%Qsize;
 24         return e;
 25     };                    
 26     void Serve(){return;};
 27     int IsEmpty(){                //判定是否为空
 28         if(front==rear) return 1;
 29         return 0;
 30     };
 31 private:
 32     T* data;
 33     int front;
 34     int rear;
 35     int Qsize;
 36 };
 37 
 38 enum ColorType{White,Gray,Black};
 39 struct ENode
 40 {
 41     int adjVex;
 42     ENode* nextArc;
 43 };
 44 class Graph
 45 {
 46 public:
 47     Graph(int mSize){
 48         n = mSize;
 49         a = new ENode* [n];
 50         for(int i = 0; i<n;i++) a[i] = NULL;
 51     }
 52     void DFS_Traversal(int* parent);
 53     void BFS_Traversal(int* parent);
 54     void input(int data[][7], int lenth){
 55         ENode *t;
 56         ENode *newNode;
 57         for(int i = 0; i< n; i++){
 58             t = a[i];
 59             for(int j = 0; j<lenth ;j++){
 60                 if(data[i][j] >=0 && data[i][j] <= n-1){
 61                     newNode = new ENode();
 62                     newNode->adjVex = data[i][j];
 63                     newNode->nextArc = NULL;
 64                     if(t == NULL && a[i] == NULL){
 65                         a[i] = newNode;
 66                         t=newNode;
 67                     }else{
 68                         t->nextArc = newNode;
 69                         t=newNode;
 70                     }
 71                 }else{
 72                     break;
 73                 }
 74             }
 75         }
 76     }
 77     void output(){
 78         ENode *t;
 79         for(int i = 0; i < n; i++){
 80             cout<<endl<<"  节点"<<i<<"连接的节点";
 81             t=a[i];
 82             while(t!=NULL){
 83                 cout<<"->"<<t->adjVex;
 84                 t = t->nextArc;
 85             }
 86         }
 87     }
 88 protected:
 89     void DFS(int u, int *parent, ColorType* color);
 90     void BFS(int u, int *parent, ColorType* color);
 91     ENode** a;
 92     int n;
 93 };
 94 
 95 void Graph::BFS_Traversal(int* parent)
 96 {
 97     //学生完成部分
 98 }
 99 
100 void Graph::BFS(int u, int* parent, ColorType* color)
101 { 
102     //学生完成部分
103 }
104 
105 void main(){
106     int data[7][7]={{ 1,-1,-1,-1,-1,-1,-1},
107                     { 6, 3, 2,-1,-1,-1,-1},
108                     { 0,-1,-1,-1,-1,-1,-1},
109                     { 2, 0,-1,-1,-1,-1,-1},
110                     { 6, 5,-1,-1,-1,-1,-1},
111                     { 1,-1,-1,-1,-1,-1,-1},
112                     { 5, 3,-1,-1,-1,-1,-1}};
113     Graph *G = new Graph(7);
114     G->input(data,7);
115     G->output();
116     cout<<endl;
117     int parent[30];
118     G->BFS_Traversal(parent);
119 }

补充后的代码如下：

  1 #include <iostream.h>
  2 #define QSize 30
  3 template<class T>  //队列
  4 class Queue
  5 {
  6 public:
  7     Queue(){data = new T[30]; Qsize = 30;InitQueue();};
  8     Queue(int size){Qsize = size; data = new T[Qsize];InitQueue();};
  9     void InitQueue(){            //初始化队列
 10         front = rear = 0;
 11     };
 12     void Append(T e){            //入队操作
 13         if((rear+1)%Qsize==front) cout<<"队列已满";
 14         else 
 15         {
 16             data[rear]=e;
 17             rear=(rear+1)%Qsize;
 18          }
 19     };
 20     T Front(){        //出对操作
 21         if(IsEmpty())  return -1;
 22         T e =data[front];
 23         front=(front+1)%Qsize;
 24         return e;
 25     };                    
 26     void Serve(){return;};
 27     int IsEmpty(){                //判定是否为空
 28         if(front==rear) return 1;
 29         return 0;
 30     };
 31 private:
 32     T* data;
 33     int front;
 34     int rear;
 35     int Qsize;
 36 };
 37 
 38 enum ColorType{White,Gray,Black};
 39 struct ENode
 40 {
 41     int adjVex;
 42     ENode* nextArc;
 43 };
 44 class Graph
 45 {
 46 public:
 47     Graph(int mSize){
 48         n = mSize;
 49         a = new ENode* [n];
 50         for(int i = 0; i<n;i++) a[i] = NULL;
 51     }
 52     void DFS_Traversal(int* parent);
 53     void BFS_Traversal(int* parent);
 54     void input(int data[][7], int lenth){
 55         ENode *t;
 56         ENode *newNode;
 57         for(int i = 0; i< n; i++){
 58             t = a[i];
 59             for(int j = 0; j<lenth ;j++){
 60                 if(data[i][j] >=0 && data[i][j] <= n-1){
 61                     newNode = new ENode();
 62                     newNode->adjVex = data[i][j];
 63                     newNode->nextArc = NULL;
 64                     if(t == NULL && a[i] == NULL){
 65                         a[i] = newNode;
 66                         t=newNode;
 67                     }else{
 68                         t->nextArc = newNode;
 69                         t=newNode;
 70                     }
 71                 }else{
 72                     break;
 73                 }
 74             }
 75         }
 76     }
 77     void output(){
 78         ENode *t;
 79         for(int i = 0; i < n; i++){
 80             cout<<endl<<"  节点"<<i<<"连接的节点";
 81             t=a[i];
 82             while(t!=NULL){
 83                 cout<<"->"<<t->adjVex;
 84                 t = t->nextArc;
 85             }
 86         }
 87     }
 88 protected:
 89     void DFS(int u, int *parent, ColorType* color);
 90     void BFS(int u, int *parent, ColorType* color);
 91     ENode** a;
 92     int n;
 93 };
 94 
 95 void Graph::BFS_Traversal(int* parent)
 96 {
 97     //学生完成部分
 98     ColorType*color=new ColorType[n];
 99     cout<<endl<<"BFS";
100     for(int u=0;u<n;u++){
101         color[u]=White;
102         parent[u]=-1;
103     }
104     for(int u=0;u<n;u++){
105         if(color[u]==White)
106             BFS(u,parent,color);
107     }
108     delete[]color;
109     cout<<endl;
110 }
111 
112 void Graph::BFS(int u, int* parent, ColorType* color)
113 { 
114 
115     //学生完成部分
116     Queue<int> q(QSize);
117     color[u]=Gray;
118     cout<<" "<<u;
119     q.Append(u);
120     while(!q.IsEmpty()){
121         u=q.Front();
122         q.Serve();
123         for(ENode *w=a[u];w;w=w->nextArc){
124             int v=w->adjVex;
125             if(color[v]==White){
126                 color[v]=Gray;
127                 cout<<" "<<v;
128                 parent[v]=u;
129                 q.Append(v);
130             }
131         }
132         color[u]=Black;
133     }
134 }
135 
136 int main(){
137     int data[7][7]={{ 1,-1,-1,-1,-1,-1,-1},
138                     { 6, 3, 2,-1,-1,-1,-1},
139                     { 0,-1,-1,-1,-1,-1,-1},
140                     { 2, 0,-1,-1,-1,-1,-1},
141                     { 6, 5,-1,-1,-1,-1,-1},
142                     { 1,-1,-1,-1,-1,-1,-1},
143                     { 5, 3,-1,-1,-1,-1,-1}};
144     Graph *G = new Graph(7);
145     G->input(data,7);
146     G->output();
147     cout<<endl;
148     int parent[30];
149     G->BFS_Traversal(parent);
150 }

1. 分析Graph类，画出Graph类初始化以后的Graph对象的数据结构图。

2. 分析BFS函数，画出流程图。

3. 上述程序 int data[7][7]={{ 1,-1,-1,-1,-1,-1,-1},

{ 6, 3, 2,-1,-1,-1,-1},

{ 0,-1,-1,-1,-1,-1,-1},

{ 2, 0,-1,-1,-1,-1,-1},

{ 6, 5,-1,-1,-1,-1,-1},

{ 1,-1,-1,-1,-1,-1,-1},

{ 5, 3,-1,-1,-1,-1,-1}};

是对课本图4-1的输入，从0开始的广度优先的顺序是：

4. 若上图从节点4开始遍历的话，广度优先的顺序应该是什么。

5. 分析当Graph类对象，在输入以下图1的时候，从0开始的广度优先顺序是什么。自己设计data[][]数据进行输入，并给出该种输入情况下的遍历顺序。

6. 改写程序，输出parent数组值，并根据parent画出图1的广度优先深林。

第二部分深度优先遍历算法

分析DFS程序，给出DFS的流程图：
对图4-1的DFS遍历顺序是：
当对图1进行DFS遍历的时候，遍历顺序是什么，根据parent值，推断深度优先深林是什么。
自己设计一个图，并通过程序计算深度遍历和广度遍历顺序。

四、实验小结和心得：

实验四 图的遍历算法设计与实现

实验四图的遍历算法设计与实现