一、BFS,也称广度优先搜索,和二叉树的层次遍历算法类似
//BFS
bool visited[MaxVertexNum];
void BFSTraverse(Graph G){
for(i=0;i<G.vexnum;i++)
visited[i]=FALSE;
InitQueue(Q);
for(i=0;i<G.vexnum;i++)
if(!visited[i])
BFS(G,i);
}
void BFS(Graph G,int v){
visit(v);
visited[v]=TRUE;
EnQueue(Q,v);
while(!isEmpty(Q)){
DeQueue(Q,v);
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
if(!visited[w]){
visit(w);
visited[w]=TRUE;
EnQueue(Q,w);
}
}
}
二、DFS,也称深度优先搜索,类似于二叉树的先序遍历
//DFS
bool visited[MaxVertexNum];
void DFSTraverse(Graph G){
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE;
for(v=0;v<G.vexnum;v++)
if(!visited[v])
DFS(G,v);
}
void DFS(Graph G,int v){
visit(v);
visited[v]=TRUE;
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
if(!visited[w]){
DFS(G,w);
}
}