文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 图的应用——深度优先遍历和广度优先遍历
侵权投诉

图的应用——深度优先遍历和广度优先遍历

return i;

}

return -1;

}

int NextAdjVex(MGraph G,int v,int w) {//

for (int i = w + 1 ; i < G.vexnum; i ++) {

if (G.arcs[v][i].adj == 1)

return i;

}

return -1;

}

void VisitFunc(MGraph G,int v) {//访问图G中v位置的元素

printf("%c ",G.vexs[v]);

}

void DFS(MGraph G,int v) {//从第v个顶点出发递归地深度优先遍历图G visited[v] = true;

VisitFunc(G,v);//访问第v个顶点

for (int w = FirstAdjVex(G,v); w >= 0; w = NextAdjVex(G,v,w)) { if (!visited[w])

DFS(G,w);//对v的尚未访问的邻接顶点w递归调用DFS }

}

void DFSTraverse(MGraph G,char firstVex) {//对图G作深度优先遍历 int v = LocateVex(G,firstVex);

DFS(G,v);

}

void BFSTraverse(MGraph G,char firstVex) {//对图G作广度优先遍历 int v = LocateVex(G,firstVex);

char u;

int w;

Queue Q;

for (int i = 0; i < G.vexnum; i ++)

visited[i] = false;

InitQueue(Q);

if (!visited[v]) {//v尚未访问

VisitFunc(G,v);

visited[v] = true;

EnQueue(Q,firstVex);//v入队列

while(!QueueEmpty(Q)) {

DeQueue(Q,u);//出队列

int p = LocateVex(G,u);

for (w = FirstAdjVex(G,p); w >= 0; w = NextAdjVex(G,p,w)) if (!visited[w]) {

visited[w] = true;

VisitFunc(G,w);

上一页第3页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email