数据结构实验-图的储存与遍历解析.doc

数据结构　课程实验报告　 学号： 姓名： 实验日期： 2016.1.7 实验名称： 图的存贮与遍历 一、实验目的 掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历 DFS 和广度优先遍历 BFS 操作的实现。 二、实验内容与实验步骤 题目1：对以邻接矩阵为存储结构的图进行DFS和BFS遍历 问题描述：以邻接矩阵为图的存储结构，实现图的DFS和BFS遍历。 基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS和BFS序列。 测试数据：如图所示 题目2：对以邻接表为存储结构的图进行DFS和BFS遍历 问题描述：以邻接表为图的存储结构，实现图的DFS和BFS遍历。 基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS和BFS序列。 测试数据：如图所示 V0 V1 V2 V3 V4 三、附录： 在此贴上调试好的程序。 #include #include #include #define M 100 typedef struct node char vex[M][2]; int edge[M ][ M ]; int n,e; Graph; int visited[M]; Graph *Create_Graph Graph *GA; int i,j,k,w; GA Graph* malloc sizeof Graph ; printf 请输入矩阵的顶点数和边数 用逗号隔开 ：\n ; scanf %d,%d,GA- n,GA- e ; printf 请输入矩阵顶点信息：\n ; for i 0;i GA- n;i++ scanf %s, GA- vex[i][0] , GA- vex[i][1] ; for i 0;i GA- n;i++ for j 0;j GA- n;j++ GA- edge[i][j] 0; for k 0;k GA- e;k++ printf 请输入第%d条边的顶点位置 i,j 和权值 用逗号隔开 ：,k+1 ; scanf %d,%d,%d,i,j,w ; GA- edge[i][j] w; return GA ; void dfs Graph *GA, int v int i; printf %c%c\n,GA- vex[v][0],GA- vex[v][1] ; visited[v] 1; for i 0; i GA- n; i++ if GA- edge[v][i] 1 visited[i] 0 dfs GA, i ; void traver Graph *GA int i; for i 0; i GA- n; i++ visited[i] 0; for i 0; i GA- n;i++ if visited[i] 0 dfs GA, i ; void bfs Graph *GA, int v int j,k,front -1,rear -1; int Q[M]; printf %c%c\n,GA- vex[v][0],GA- vex[v][1] ; visited[v] 1; rear rear+1; Q[rear] v; while front! rear front front+1;k Q[front]; for j 0; j GA- n; j++ if GA- edge[k][j] 1 visited[j] 0 printf %c%c\n,GA- vex[j][0],GA- vex[j][1] ; visited[j] 1; rear rear+1; Q[rear] j; void traver1 Graph *GA int i; for i 0; i GA- n;i++ visited[i] 0; for i 0; i GA- n; i++ if visited[i] 0 bfs GA, i ; typedef struct NODE int adjvex; struct NODE *next; ENode; typedef struct NODE1 char vex[2]; ENode *first; VexNode; typedef struct FS1 VexNode GL[M]; int bian,top; FS; FS *CreateGL FS *kk FS * malloc sizeof FS ; int i,j,k; ENode *s; printf 请输入顶点数和边数 用逗号隔开 ：\n ; scanf %d,%d,kk- top,