图的深度优先遍历类似于树的先序遍历,可以利用递归不断地访问当前结点的首个未被访问的邻结点,同时需要设置访问数组来标志每个结点的访问情况,防止被多次访问。
void DFSTraverse(Graph g){//深度优先遍历图g
int visited[MAX_VERTEX_NUM];//每个顶点的访问数组
for(int i=0;i<g.vexnum;i++){
visited[i]=0;//初始化访问数组,0代表未被访问
}
for(int i=0;i<g.vexnum;i++){//遍历一遍防止有遗漏结点
if(!visited[i]){
DFS(g,i);
}
}
}
采用递归实现图的深度优先遍历:
void DFS(Graph g,int v){
visit(v);//访问当前结点,更新访问标志位
visited[v]=1;
int w=FirstAdjVertex(g,v);//递归访问当前结点首个未被访问的邻结点
while(w!=-1){
if(!visited[w]){
DFS(g,w);
}
w=NextAdjVertex(g,v,w);//更新邻结点
}
}
如果采用邻接表的方式存储图则思路相同,其表头结点中firstarc存放首个弧结点的地址,弧结点中的adjvex存放该结点在图中的序号,nextarc指向下一个弧结点:
void DFS(Graph g,int v){//采用邻接表存储
visit(v);//访问当前结点,更新访问标志位
visited[v]=1;
ArcNode* p=g.vertex[v].firstarc;//递归访问当前结点首个未被访问的邻结点
while(p!=NULL){
if(!visited[p->adjvex]){
DFS(g,w);
}
p=p->nextarc;//更新邻结点
}
}
递归的思想同栈(LIFO),所以非递归可以借助栈来实现,待访问结点入栈后,循环判断若栈非空则栈顶元素出栈并访问,同时让其所有未被访问的邻结点入栈,利用栈后进先出的特性,每次的栈顶均为出栈元素首个未被访问的邻结点:
void DFS(Graph g,int v){//采用非递归的方式实现图的深度优先遍历
InitStack(&s);//创建并初始化栈s
PUSH(&s,v);//待访问结点入栈
while(!IsEmpty(s)){//栈非空栈顶元素出栈并访问,同时让其所有未被访问的邻结点入栈
POP(&s,&v);
visit(v);
visited[v]=1;
int w=FirstAdjVex(g,v);
while(w!=-1){
if(!visited[w]){
PUSH(&s,w);
}
w=NextAdjVertex(g,v,w);
}
}