php免费网站源码,天元建设集团有限公司烟台分公司,wordpress页面模板路径,网站建设书籍推荐一、实验名称#xff1a;图的遍历算法设计与实现 二、实验目的#xff1a; 1.掌握图的深度优先遍历的算法。 2.掌握图的广度优先遍历的算法。 3.实验章节#xff1a;算法设计与分析 第四章 三、实验内容。实验问题和程序运行结果 第一部分 广度优先遍历算法 完善下列程序图的遍历算法设计与实现 二、实验目的 1.掌握图的深度优先遍历的算法。 2.掌握图的广度优先遍历的算法。 3.实验章节算法设计与分析 第四章 三、实验内容。实验问题和程序运行结果 第一部分 广度优先遍历算法 完善下列程序并回答问题。 1 #include iostream.h2 #define QSize 303 templateclass T //队列4 class Queue5 {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((rear1)%Qsizefront) cout队列已满;14 else 15 {16 data[rear]e;17 rear(rear1)%Qsize;18 }19 };20 T Front(){ //出对操作21 if(IsEmpty()) return -1;22 T e data[front];23 front(front1)%Qsize;24 return e;25 }; 26 void Serve(){return;};27 int IsEmpty(){ //判定是否为空28 if(frontrear) 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 ENode40 {41 int adjVex;42 ENode* nextArc;43 };44 class Graph45 {46 public:47 Graph(int mSize){48 n mSize;49 a new ENode* [n];50 for(int i 0; in;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; jlenth ;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 tnewNode;67 }else{68 t-nextArc newNode;69 tnewNode;70 }71 }else{72 break;73 }74 }75 }76 }77 void output(){78 ENode *t;79 for(int i 0; i n; i){80 coutendl 节点i连接的节点;81 ta[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 coutendl;
117 int parent[30];
118 G-BFS_Traversal(parent);
119 } 补充后的代码如下 1 #include iostream.h2 #define QSize 303 templateclass T //队列4 class Queue5 {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((rear1)%Qsizefront) cout队列已满;14 else 15 {16 data[rear]e;17 rear(rear1)%Qsize;18 }19 };20 T Front(){ //出对操作21 if(IsEmpty()) return -1;22 T e data[front];23 front(front1)%Qsize;24 return e;25 }; 26 void Serve(){return;};27 int IsEmpty(){ //判定是否为空28 if(frontrear) 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 ENode40 {41 int adjVex;42 ENode* nextArc;43 };44 class Graph45 {46 public:47 Graph(int mSize){48 n mSize;49 a new ENode* [n];50 for(int i 0; in;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; jlenth ;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 tnewNode;67 }else{68 t-nextArc newNode;69 tnewNode;70 }71 }else{72 break;73 }74 }75 }76 }77 void output(){78 ENode *t;79 for(int i 0; i n; i){80 coutendl 节点i连接的节点;81 ta[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*colornew ColorType[n];99 coutendlBFS;
100 for(int u0;un;u){
101 color[u]White;
102 parent[u]-1;
103 }
104 for(int u0;un;u){
105 if(color[u]White)
106 BFS(u,parent,color);
107 }
108 delete[]color;
109 coutendl;
110 }
111
112 void Graph::BFS(int u, int* parent, ColorType* color)
113 {
114
115 //学生完成部分
116 Queueint q(QSize);
117 color[u]Gray;
118 cout u;
119 q.Append(u);
120 while(!q.IsEmpty()){
121 uq.Front();
122 q.Serve();
123 for(ENode *wa[u];w;ww-nextArc){
124 int vw-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 coutendl;
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值推断深度优先深林是什么。自己设计一个图并通过程序计算深度遍历和广度遍历顺序。 四、实验小结和心得
