数据结构实验六图.doc

实验六 图的表示与遍历一、实验目的1、掌握图的邻接矩阵和邻接表表示2、掌握图的深度优先和广度优先搜索方法 3、理解图的应用方法二、实验内容和要求1、阅读并运行下面程序，根据输入写出运行结果include#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;ivexnum;i++) /*邻接矩阵初始化*/ for(j=0;jvexnum;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;jvexnum;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;ivexnum;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;jvexnum;j++) if((g->arcs[i][j]==1)&&(!visited[j])) { printf("%c",g->vexs[j]); visited[j]=TRUE; q->data[q->rear]=j; q->rear=(q->rear+1)%N; } }}void tbfs(graph *g) /*广度优先搜索整个图*/{ int i; printf("\n从顶点%C开始广度优先搜索序列：",g->vexs[0]); for(i=0;ivexnum;i++) if(visited[i]!=TRUE) bfs(i,g);}void init_visit() /*初始化访问标识数组*/{ int i; for(i=0;i

include#include#define N 20typedef struct edgenode{ /*图的邻接表：邻接链表结点*/ int adjvex; /*顶点序号*/ struct edgenode *next; /*下一个结点的指针*/}edgenode;typedef struct vnode{ /*图的邻接表：邻接表*/ char data; /*顶点信息*/ int ind; /*顶点入度*/ struct edgenode *link; /*指向邻接链表指针*/}vnode;void createGraph_list(vnode adjlist[],int *p)； /*建立有向图的邻接表*/void topSort(vnode g[],int n)； /*拓扑排序*/void createGraph_list(vnode adjlist[],int *p){ /*建立有向图的邻接表*/ int i,j,n,e; char v; edgenode *s; i=0;n=0;e=0; printf("输入顶点序列(以#结束)：\n"); while((v=getchar())!='#') { adjlist[i].data=v; /*读入顶点信息*/ adjlist[i].link=NULL; adjlist[i].ind=0; i++; } n=i; *p=n; /*建立邻接链表*/ printf("\n请输入弧的信息(i=-1结束)：i,j:\n"); scanf("%d,%d",&i,&j); while(i!=-1){ s=(struct edgenode*)malloc(sizeof(edgenode)); s->adjvex=j; s->next=adjlist[i].link; adjlist[i].link=s; adjlist[j].ind++; /*顶点j的入度加1*/ e++; scanf("%d,%d",&i,&j); } printf("邻接表:"); for(i=0;i%d",s->adjvex); s=s->next; } }}void topSort(vnode g[],int n){ /*拓扑排序*/ }int main(){ vnode adjlist[N]; int n,*p; p=&n; createGraph_list(adjlist,p); return 0;}§ 根据输入，输出有向图的拓扑排序序列。

并画出有向图输入:ABCDEF#0,11,22,34,14,5-1,-1§ 运行结果：3、阅读并运行下面程序include#define N 20#define TRUE 1#define INF 32766 /*邻接矩阵中的无穷大元素*/#define INFIN 32767 /*比无穷大元素大的数*/typedef struct{ /*图的邻接矩阵*/ int vexnum,arcnum; char vexs[N]; int arcs[N][N];}graph;void createGraph_w(graph *g,int flag);。