数据结构的图的遍历实验报告.docVIP

实 验 报 告 课程名称： 数据结构 实验名称： 图的遍历 姓 名： 专 业： 计算机科学与技术 班 级： 计算机 学 号： 计算机科学与技术学院 实验教学中心 2015 年 11 月 20 日 实验项目名称：图的遍历 一、实验目的 1深入学习图的遍历原理 ； 2用代码的形式将图的广度优先遍历和深度优先遍历实现； 实验内容 设计程序将图的广度优先遍历和深度优先遍历实现； 实验原理 #includecstdio #includecstring #includeiostream #includealgorithm #includecstdlib using namespace std; const int V = 500; const int E = 500; int EdgeCount; struct Arc { int next_arc; int point; }; int node[V]; struct Arc arc[E]; void Addedge(int u,int v) { arc[EdgeCount].next_arc = node[u]; arc[EdgeCount].point = v; node[u] = EdgeCount; EdgeCount++; } int que[V]; int vis[V]; int sta[V]; int k; int front,rear; void bfs() { front = rear = 0; memset(vis,0,sizeof(vis)); que[rear++] = 1; vis[1] = 1; sta[k++] = 1; while(front rear ) { int cur_node = que[front++]; int edge; for(edge = node[cur_node]; edge!=-1; edge = arc[edge].next_arc) { if(!vis[arc[edge].point]) { que[rear++] = arc[edge].point; vis[arc[edge].point] = 1; sta[k++] = arc[edge].point; } } } } void dfs(int v) { vis[v] = 1; printf(%d ,v); int edge; for(edge= node[v]; edge!=-1; edge = arc[edge].next_arc) { if(!vis[arc[edge].point]) { dfs(arc[edge].point); } } } int main() { int n,m; //printf(输入节点数和边数:\n); while(scanf(%d%d,n,m) ==2) { EdgeCount = 0; memset(node,-1,sizeof(node)); for(int i = 0; im; i++) { int u,v; scanf(%d%d,u,v); Addedge(u,v); } k = 0; bfs(); for(int i = 0; ik; i++) printf(%d ,sta[i]); printf(广度优先\n); memset(vis,0,sizeof(vis)); dfs(1); printf(深度优先\n); } return 0; } 图的结构 五、实验结果分析 2 哈尔滨理工大学计算机科学与技术学院实验教学中心 实验报告 哈尔滨