首页 / 软件开发 / 数据结构与算法 / 图的深度优先遍历：邻接表实现

图的深度优先遍历：邻接表实现2014-12-25这里用邻接表实现图的深度优先遍历，采用递归实现。

#include<iostream>using namespace std;#define VERTEXNUM 5//结点数structedgenode{int to;int weight; // 边的权值edgenode *next;};struct vnode{int from;edgenode *first;};void createGraph（vnode *adjilist, int start, int end,int weight）;void displayGraph（vnode *adjilist,int nodeNum）;void DFT（vnode *adjilist,int* vertexStatusArr,int nodeNum）;void DFTcore（vnode *adjilist,int i,int* vertexStatusArr）;/**/int main（void）{//创建图vnode adjilist[VERTEXNUM];int nodeNum=VERTEXNUM;for（int i=0;i<nodeNum;i++）adjilist[i].first=NULL;int vertexStatusArr[VERTEXNUM]={0};cout<<vertexStatusArr[4]<<endl;createGraph（adjilist,0,3,0）;createGraph（adjilist,0,4,0）;createGraph（adjilist,3,1,0）;createGraph（adjilist,3,2,0）;createGraph（adjilist,4,1,0）;printf（"after create:
"）;displayGraph（adjilist,nodeNum）;//深度优先遍历DFT（adjilist,vertexStatusArr,nodeNum）;system（"pause"）;return 0;}//创建图,采取前插法void createGraph（vnode *adjilist, int start, int end,int weight）{adjilist[start].from=start;edgenode *p=new edgenode;p->to=end;p->weight=weight;p->next=adjilist[start].first;adjilist[start].first=p;}//打印存储的图void displayGraph（vnode *adjilist,int nodeNum）{int i,j;edgenode *p;for（i=0;i<nodeNum;i++）{p=adjilist[i].first;while（p）{cout<<"（"<<adjilist[i].from<<","<<p->to<<"）"<<endl;p=p->next;} }}//深度优先遍历void DFT（vnode *adjilist, int* vertexStatusArr,int nodeNum）{printf（"start BFT graph:
"）;int i;for（i=0;i<nodeNum;i++）{DFTcore（adjilist,i,vertexStatusArr）;}printf（"
"）;}void DFTcore（vnode *adjilist,int i,int* vertexStatusArr）{if（vertexStatusArr[i] == 1）return;printf（"%d ",i）;vertexStatusArr[i] = 1;edgenode *p;for（p=adjilist[i].first;p;p=p->next）{DFTcore（adjilist, p->to, vertexStatusArr）;}}

时间复杂度为O（V+E）。

作者：csdn博客 Duplan