实验7图的表示与遍历.docx

实验五图的表示与遍历一、实验目的1、掌握图的邻接矩阵和邻接表表示2、掌握图的深度优先和广度优先有哪些信誉好的足球投注网站方法3、理解图的应用方法二、实验预习说明以下概念1、深度优先有哪些信誉好的足球投注网站遍历：从根开始一个一个有哪些信誉好的足球投注网站2、广度优先有哪些信誉好的足球投注网站遍历：从根的邻接点出发依次访问3、拓扑排序： 一个无指向的点开始排序4、最小生成树：最小权的生成树5、最短路径：路径权数最小三、实验内容和要求1、阅读并运行下面程序，根据输入写出运行结果。#includestdio.h#define N 20#define TRUE 1#define FALSE 0int visited[N];typedef struct /*队列的定义*/{ int data[N]; int front,rear;}queue;typedef struct /*图的邻接矩阵*/{ int vexnum,arcnum;char vexs[N]; int arcs[N][N];}graph;void createGraph(graph *g); /*建立一个无向图的邻接矩阵*/void dfs(int i,graph *g); /*从第i个顶点出发深度优先有哪些信誉好的足球投注网站*/void tdfs(graph *g); /*深度优先有哪些信誉好的足球投注网站整个图*/void bfs(int k,graph *g); /*从第k个顶点广度优先有哪些信誉好的足球投注网站*/void tbfs(graph *g); /*广度优先有哪些信誉好的足球投注网站整个图*/void init_visit(); /*初始化访问标识数组*/void createGraph(graph *g) /*建立一个无向图的邻接矩阵*/{ int i,j; char v;g-vexnum=0; g-arcnum=0; i=0; printf(输入顶点序列(以#结束)：\n); while((v=getchar())!=#) { g-vexs[i]=v; /*读入顶点信息*/ i++; } g-vexnum=i; /*顶点数目*/ for(i=0;ig-vexnum;i++) /*邻接矩阵初始化*/ for(j=0;jg-vexnum;j++) g-arcs[i][j]=0; printf(输入边的信息：\n); scanf(%d,%d,i,j); /*读入边i,j*/ while(i!=-1) /*读入i,j为－1时结束*/ { g-arcs[i][j]=1; g-arcs[j][i]=1; scanf(%d,%d,i,j); }}void dfs(int i,graph *g) /*从第i个顶点出发深度优先有哪些信誉好的足球投注网站*/{ int j; printf(%c,g-vexs[i]);visited[i]=TRUE; for(j=0;jg-vexnum;j++) if((g-arcs[i][j]==1)(!visited[j])) dfs(j,g);}void tdfs(graph *g) /*深度优先有哪些信誉好的足球投注网站整个图*/{ int i; printf(\n从顶点%C开始深度优先有哪些信誉好的足球投注网站序列：,g-vexs[0]); for(i=0;ig-vexnum;i++) if(visited[i]!=TRUE) dfs(i,g);}void bfs(int k,graph *g) /*从第k个顶点广度优先有哪些信誉好的足球投注网站*/{ int i,j; queue qlist,*q; q=qlist; q-rear=0; q-front=0; printf(%c,g-vexs[k]); visited[k]=TRUE; q-data[q-rear]=k;q-rear=(q-rear+1)%N;while(q-rear!=q-front) { i=q-data[q-front]; q-front=(q-front+1)%N; for(j=0;jg-vexnum;j++) if((g-arcs[i][j]==1)(!visited[j])) { printf(%c,g-vexs[j]); vi