DFS类似于树的先序遍历，因此可以用递归实现；
BFS类似于树的层次遍历，因此可以用队列实现。
说明：下面代码中图的存储方式是邻接表。关于邻接表和邻接矩阵可看邻接表和邻接矩阵
思想
从图中的某一个顶点 v0 出发，访问此顶点，然后依次从 v0 的没被访问的邻接点出发深度优先遍历图（体现了递归的思想），直至图中所有和 v0 有路径相通的顶点都被访问到；若此时图中仍有结点没有被访问，则另选图中一个未曾访问的顶点作起始点，重复上述过程。
因为要判断某顶点是否被访问过，所以需要一visit[]数组来记录，若访问过则为true，没访问过则为false
例子
遍历结果： V1–> V2 --> V4 -->V8 --> V5 --> V3 --> V6 --> V7
代码
#include <iostream>
#define MAX_VEX_NUM 20
using namespace std;
typedef char NumType;
struct EdgeNode
{
int adjvex;
EdgeNode *nextedge;
};
struct VexNode
{
NumType data;
EdgeNode *firstedgd;
};
struct Graph
{
VexNode Vex[MAX_VEX_NUM];
int VexNum;
int EdgeNum;
};
int Locate(Graph G,NumType v)
{
int i;
for(i=0;i<G.VexNum;i++)
if(G.Vex[i].data==v)return i;
return -1;
}
void CreateGraph(Graph &G)
{
cout<<"请输入结点个数和边的条数：";
cin>>G.VexNum;cin>>G.EdgeNum;
int i,j,k;
cout<<"请输入结点信息：";
for(i=0;i<G.VexNum;i++){cin>>G.Vex[i].data;G.Vex[i].firstedgd=0;}
NumType v1,v2;
for(k=0;k<G.EdgeNum;k++)
{
cin>>v1;cin>>v2;
i=Locate(G,v1);j=Locate(G,v2);
EdgeNode *p=new EdgeNode();
EdgeNode *p0=new EdgeNode();
*p={j,G.Vex[i].firstedgd};
G.Vex[i].firstedgd=p;
//这是无向图才有的
*p0={i,G.Vex[j].firstedgd};
G.Vex[j].firstedgd=p0;
}
}
//上面的代码是用邻接表存储图结构的过程
//只有下面的代码才是DFS
bool Visited[MAX_VEX_NUM]={false};
void DFS(Graph G,int v)//从下标为v的顶点开始
{
Visited[v]=true;
cout<<G.Vex[v].data<<" ";
EdgeNode *p=0;
for(p=G.Vex[v].firstedgd;p!=0;p=p->nextedge)
if(!Visited[p->adjvex])DFS(G,p->adjvex);
}
void DFSTraverse(Graph G)
{
int i;
for(i=0;i<G.VexNum;i++)
if(!Visited[i])DFS(G,i);
}
int main()
{
Graph G;
CreateGraph(G);
DFSTraverse(G);
return 0;
}
思想
从图中的某一个顶点 v0 出发，访问v0之后，依次访问v0 的没被访问的邻接点，然后，再分别从这些邻接点出发，广度优先遍历图，直至所有顶点都被访问；若此时图中仍有结点没有被访问，则另选图中一个未曾访问的顶点作起始点，重复上述过程。
1、可以看出BFS类似于树的层次遍历，所以需要队列来存储顶点；
2、因为要判断某顶点是否被访问过，所以需要一visit[]数组来记录，若访问过则为true，没访问过则为false。
例子
遍历结果： V1–> V2 --> V3 -->V4 --> V5 --> V6 --> V7 --> V8
代码
#include <iostream>
#define MAX_VEX_NUM 20
#include <queue>
using namespace std;
typedef char NumType;
struct EdgeNode
{
int adjvex;
EdgeNode *nextedge;
};
struct VexNode
{
NumType data;
EdgeNode *firstedgd;
};
struct Graph
{
VexNode Vex[MAX_VEX_NUM];
int VexNum;
int EdgeNum;
};
int Locate(Graph G,NumType v)
{
int i;
for(i=0;i<G.VexNum;i++)
if(G.Vex[i].data==v)return i;
return -1;
}
void CreateGraph(Graph &G)
{
cout<<"请输入结点个数和边的条数：";
cin>>G.VexNum;cin>>G.EdgeNum;
int i,j,k;
cout<<"请输入结点信息：";
for(i=0;i<G.VexNum;i++){cin>>G.Vex[i].data;G.Vex[i].firstedgd=0;}
NumType v1,v2;
cout<<"请输入边的信息：";
for(k=0;k<G.EdgeNum;k++)
{
cin>>v1;cin>>v2;
i=Locate(G,v1);j=Locate(G,v2);
EdgeNode *p=new EdgeNode();
EdgeNode *p0=new EdgeNode();
*p={j,G.Vex[i].firstedgd};
G.Vex[i].firstedgd=p;
//这是无向图才有的
*p0={i,G.Vex[j].firstedgd};
G.Vex[j].firstedgd=p0;
}
}
//上面的代码是用邻接表存储图结构的过程
//只有下面的代码才是BFS
bool Visited[MAX_VEX_NUM]={false};
void BFS(Graph G)
{
queue<int> q;
EdgeNode *p=0;
int i;
for(i=0;i<G.VexNum;i++)
{
if(!Visited[i])
{
Visited[i]=true;
q.push(i);
while(!q.empty())
{
int t=q.front();
q.pop();
cout<<G.Vex[t].data<<" ";
for(p=G.Vex[t].firstedgd;p!=0;p=p->nextedge)
{
if(!Visited[p->adjvex])
{
Visited[p->adjvex]=true;
q.push(p->adjvex);
}
}
}
}
}
}
int main()
{
Graph G;
CreateGraph(G);
BFS(G);
return 0;
}