数据结构实验六图

实验六 图的表示与遍历

一、实验目的

1、掌握图的邻接矩阵和邻接表表示

2、掌握图的深度优先和广度优先搜索方法 3、理解图的应用方法

二、实验内容和要求

1、阅读并运行下面程序，根据输入写出运行结果。 #include #define N 20 #define TRUE 1 #define FALSE 0 int 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(\读入边i,j*/

while(i!=-1) /*读入i,j为－1时结束*/ {

g->arcs[i][j]=1; g->arcs[j][i]=1;

scanf(\ } }

void dfs(int i,graph *g) /*从第i个顶点出发深度优先搜索*/ {

int j;

printf(\ 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(\从顶点%C开始深度优先搜索序列：\ 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(\ 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(\ visited[j]=TRUE; q->data[q->rear]=j; q->rear=(q->rear+1)%N; } } }

void tbfs(graph *g) /*广度优先搜索整个图*/ {

int i;

printf(\从顶点%C开始广度优先搜索序列：\ for(i=0;ivexnum;i++) if(visited[i]!=TRUE) bfs(i,g); }

void init_visit() /*初始化访问标识数组*/ {

int i;

for(i=0;i

visited[i]=FALSE; }

int main() {

graph ga; int i,j;

createGraph(&ga);

printf(\无向图的邻接矩阵：\\n\

for(i=0;i

for(j=0;j

printf(\ printf(\ }

init_visit(); tdfs(&ga); init_visit(); tbfs(&ga); return 0; }

? 根据右图的结构验证实验，输入： ABCDEFGH# 0,1

00,2 0,5 1B1,3 1,4

4E3D2,5 2,6

7H3,7

4,7 -1,-1 ? 运行结果：

2、阅读并运行下面程序，补充拓扑排序算法。 #include #include #define N 20

typedef 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)； /*拓扑排序*/

AC52FG6

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(\请输入弧的信息(i=-1结束)：i,j:\\n\ scanf(\ 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(\ }

printf(\邻接表:\

for(i=0;i

printf(\ s=adjlist[i].link; while(s!=NULL){

printf(\ s=s->next; } } }

void topSort(vnode g[],int n){ /*拓扑排序*/