实验十二 图的创建和遍历

——0000000000 ***

一、实验目的

（1） 掌握图的含义；

（2） 掌握用邻接矩阵方法描述图的存储结构； （3） 理解并掌握深度优先遍历和广度优先遍历的算法。

二、实验数据

实验随机输入。

三、实验内容与步骤

（1）以邻接矩阵的描述方法创无向联通图；（2）用深度优先遍历实现图的遍历；（3）用广度优先遍历实现图的遍历。（4）思考若图为无向非连通图，程序应该如何修改

创建图

void CREATGRAPH(GRAPH *ga) {

int i,j,k; float w;

printf(\"图的顶点数为%d，边数为%d\\n\\n\",n,e); for(i=0;ifor(i=0;ifor(k=0;kfor(j=0;jga->arcs[i][j]=0; printf(\"请读入定点信息：\"); fflush(stdin);

scanf(\"%c\",&ga->vexs[i]);

}

}

printf(\"请读入第%d边权值信息：\",k); scanf(\"%d%d%f\",&i,&j,&w); ga->arcs[i][j]=w; ga->arcs[j][i]=w;

printf(\"图表创建完毕\\n\");

深度优先遍历

void DFS(GRAPH g,int i) { }

int j;

printf(\"%c\\n\",[i]); visited[i]=1; for(j=0;jif([i][j])==1 && (! visited[j]))

DFS(g,j);

广度优先遍历

void BFS(GRAPH g,int k) {

sequeue sq1,*sq=&sq1; int i,j; SETNULL(sq); printf(\"%c\\n\",[k]); visited[k]=1; ENQUEUE(sq,k); while(!EMPTY(sq)) { } }

i=DEQUEUE(sq); for(j=0;jif([i][j])==1 && (! visited[j])) { }

printf(\"%c\\n\",[j]); visited[j]=1; ENQUEUE(sq,j);

四、结论与讨论

需要注意的问题：

1. fflush(stdin)表示清除清空输入缓冲区，通常是为了确保不影响后面的数据读取（例如在读完一个字符串后紧接着又要读取一个字符，此时应该先执行fflush(stdin);）。

Ga->vexs[i]=getchar();可以获取顶点信息，但是不能输出图的顶点信息。

2. 输入第i边权的信息时，三个数字分别表示边的两个顶点及权值