DFS
DFS搜索是按照深度的方向搜索，它类似于树的先根遍历，是树的先根遍历的推广。
1.从图的某个顶点v0出发，首先访问v0，
2.找出刚访问过的顶点的第一个未被访问过的邻接点，然后访问该结点，以该结点为新顶点，重复，直到刚访问过的结点没有未被访问过得邻接点为止。
3.返回前一个访问过得且仍有未被访问的邻接点的顶点，找出该结点的下一个未被访问的邻接点，访问该顶点，执行步骤2
下面是邻接矩阵和邻接表存储时DFS访问的代码
#include <iostream>
#include <queue>
#define INF 0x3f3f
using namespace std;
/***************图用邻接矩阵表示***************/
class Graph_a
{
private:
int num;//顶点个数
int e;//边数
int **array;//储存图的联通信息的邻接矩阵
string *info;//结点的信息
bool *visit;//判断该结点是否访问过，false：没有访问过，true：访问过
public:
Graph_a();
~Graph_a();
void print_gra();
void dfs(int index);//深度遍历算法的实现
void dfs_array(int begin);//深度遍历该图
};
//构造函数
Graph_a::Graph_a()
{
cout<<" 请输入图的顶点的个数:"<<endl;
cin>>num;
cout<<" 请输入图的边数:"<<endl;
cin>>e;
//初始化visit,设置每个结点都未访问过
visit=new bool[num];
;i<num;++i)
visit[i]=false;
//初始换存储结点信息的数组
info=new string[num];//new 析构函数中释放
cout<<" 请输入每个顶点的信息:"<<endl;
;i<num;++i)
cin>>info[i];
cout<<" 请输入每条边的两个顶点的编号:"<<endl;
int **e_info=new int*[e];//临时的数组构造函数结束可释放
;i<e;++i)
{
//cout<<"i:"<<i<<endl;
e_info[i]=];
cin>>e_info[i][]>>e_info[i][];
}
//为邻接矩阵开辟空间并初始化
array=new int*[num];//为邻接矩阵开辟空间,一维数组
;i<num;++i)
{
array[i]=new int[num];//二维数组
;j<num;++j)
array[i][j]=;
}
//根据无向图的边的起始坐标和结束坐标构建邻接矩阵,数组中下标均是从0开始，所以需要减1
;i<e;++i)
array[e_info[i][]-][e_info[i][]-]=;
//释放e_info
;i<e;++i)
delete []e_info[i];
delete []e_info;
}
//析构函数
Graph_a::~Graph_a()
{
//释放邻接矩阵
;i<num;++i)
delete []array[i];
delete []array;
delete []info;//释放存储结点信息的数组
delete []visit;//释放标记数组
}
//打印该图的邻接矩阵
void Graph_a::print_gra()
{
cout<<" 该图的邻接矩阵是:"<<endl;
;i<num;++i)
{
;j<num;++j)
cout<<array[i][j]<<" ";
cout<<endl;
}
cout<<endl;
}
//深度遍历该图
void Graph_a::dfs_array(int begin)
{
dfs(begin);
//如果是非连通图，那么需要把结点再遍历一边，保证全部结点都被访问
;i<num;++i)
if(!visit[i])
dfs(i);
}
//深度遍历算法实现
void Graph_a::dfs(int index)
{
cout<<info[index]<<" ";
//标记该结点为访问过
visit[index]=true;
;i<num;++i)//值为0或无穷大表示两点之间没有连通
||array[index][i]==INF)
continue;
else if(!visit[i])
dfs(i);
}
/***************图用邻接表表示***************/
//邻接表中处头结点外的每个结点
typedef struct Node
{
int index;//该边的另一个顶点在顶点表中的下标
Node *next;//依附该顶点的下一条边信息
}Node;
//邻接表中的头结点
typedef struct Head_node
{
string data;
Node *first;//依附顶点的第一条边的信息
}Head_node;
//封装成邻接表:就是对每个结点建一条链表
class Graph_l
{
private:
int num;//顶点数
int e;//边数
bool *visit;
Head_node *node;
public:
Graph_l();
~Graph_l();
void print_g();
void dfs_l(int begin);
void dfs(int index);
};
//构造函数
Graph_l::Graph_l()
{
cout<<" 请输入图的顶点的个数:"<<endl;
cin>>num;
cout<<" 请输入图的边数:"<<endl;
cin>>e;
//初始化visit,设置每个结点都未访问过
visit=new bool[num];
;i<num;++i)
visit[i]=false;
//为邻接表动态申请存储空间,并初始化
node=new Head_node[num];
cout<<" 请输入每个结点的信息:"<<endl;
;i<num;++i)
{
cin>>node[i].data;
node[i].first=NULL;
}
cout<<" 请输入每条边的两个顶点的编号:"<<endl;
int **e_info=new int*[e];//临时的数组构造函数结束可释放
;i<e;++i)
{
e_info[i]=];
cin>>e_info[i][]>>e_info[i][];//e_info[i][0]存放边的起始点，e_info[i][1]存放边的结束点
}
;i<e;++i)
{
Node *next=new Node;
next->index=e_info[i][]-;
next->next=NULL;
//判断该顶点的边是否有依附
]-].first==NULL)
node[e_info[i][]-].first=next;
else//寻找邻接表的最后一个节点
{
Node *now;
now=node[e_info[i][]-].first;
while(now->next)
now=now->next;
now->next=next;
}
}
//释放e_info
;i<num;++i)
delete []e_info[i];
delete []e_info;
}
//析构函数
Graph_l::~Graph_l()
{
delete []node;
delete []visit;
}
//打印邻接链表的函数
void Graph_l::print_g()
{
cout<<" 该图的邻接表表示为:"<<endl;
;i<num;++i)
{
//输出结点的数据
cout<<node[i].data<<" ";
//依附头节点的第一个结点
Node *now=node[i].first;
while(now)
{
//输出依附该边的结点的另一个坐标
cout<<now->index<<" ";
now=now->next;
}
cout<<endl;
}
cout<<endl;
}
//深度优先搜索邻接表
void Graph_l::dfs_l(int begin)
{
dfs(begin);
;i<num;++i)
if(visit[i]==false)
dfs(i);
}
//深度优先搜索算法实现
void Graph_l::dfs(int index)
{
cout<<node[index].data<<" ";
visit[index]=true;
Node *next=node[index].first;
while(next)
{
if(!visit[next->index])
dfs(next->index);
else
next=next->next;
}
}
int main()
{
//图的邻接矩阵
Graph_a g;
g.print_gra();
g.dfs_array();
//图的邻接表
Graph_l G;
G.print_g();
G.dfs_l();
;
}
BFS
广度优先搜索是指按照广度得方向搜索，类似于树的按层遍历，是树的按层遍历的推广
1.从图中某个顶点v0出发，首先访问v0
2.依次访问v0各个未被访问的邻结点
3.分别从这些邻接点(端点)出发，依次访问他各个问呗访问的邻接点（新的端点），访问时保证：如果vi和vj为当前端结点，且vi在vj前被访问，则vi所有未被访问的邻接点应在vj所有未被访问的邻接点
前访问，重复步骤3，直到所有端结点的邻接点都被访问过。
如果还有其他节点未被访问，选一个未被访问的顶点作为起始点，重复上述过程，直到所有节点都被访问过.
#include <iostream>
#include <queue>
#define INF 0x3f3f
using namespace std;
/***************图用邻接矩阵表示***************/
class Graph_a
{
private:
int num;//顶点个数
int e;//边数
int **array;//储存图的联通信息的邻接矩阵
string *info;//结点的信息
bool *visit;//判断该结点是否访问过，false：没有访问过，true：访问过
public:
Graph_a();
~Graph_a();
void print_gra();
void dfs(int begin);//深度遍历算法的实现
};
//构造函数
Graph_a::Graph_a()
{
cout<<" 请输入图的顶点的个数:"<<endl;
cin>>num;
cout<<" 请输入图的边数:"<<endl;
cin>>e;
//初始化visit,设置每个结点都未访问过
visit=new bool[num];
;i<num;++i)
visit[i]=false;
//初始换存储结点信息的数组
info=new string[num];//new 析构函数中释放
cout<<" 请输入每个顶点的信息:"<<endl;
;i<num;++i)
cin>>info[i];
cout<<" 请输入每条边的两个顶点的编号:"<<endl;
int **e_info=new int*[e];//临时的数组构造函数结束可释放
;i<e;++i)
{
//cout<<"i:"<<i<<endl;
e_info[i]=];
cin>>e_info[i][]>>e_info[i][];
}
//为邻接矩阵开辟空间并初始化
array=new int*[num];//为邻接矩阵开辟空间,一维数组
;i<num;++i)
{
array[i]=new int[num];//二维数组
;j<num;++j)
array[i][j]=;
}
//根据无向图的边的起始坐标和结束坐标构建邻接矩阵,数组中下标均是从0开始，所以需要减1
;i<e;++i)
array[e_info[i][]-][e_info[i][]-]=;
//释放e_info
;i<e;++i)
delete []e_info[i];
delete []e_info;
}
//析构函数
Graph_a::~Graph_a()
{
//释放邻接矩阵
;i<num;++i)
delete []array[i];
delete []array;
delete []info;//释放存储结点信息的数组
delete []visit;//释放标记数组
}
//打印该图的邻接矩阵
void Graph_a::print_gra()
{
cout<<" 该图的邻接矩阵是:"<<endl;
;i<num;++i)
{
;j<num;++j)
cout<<array[i][j]<<" ";
cout<<endl;
}
cout<<endl;
}
//深度遍历算法实现
void Graph_a::dfs(int begin)
{
queue<int> q;//BFS类似于树的按层遍历,所以用queue
//图可能是非联通的，所以要循环遍历每个顶点
;i<num;++i)//不一定是从第一个点开始遍历，所以要对输入(下标+点的个数-1)%点的个数
+i]%num)
{
cout<<info[(begin-+i)%num]<<" ";
visit[(begin-+i)%num]=true;//把该结点标记为访问过,也就是图中的边的起始下标
q.push((begin-+i)%num);//把该点的下标存入对列中
while(!q.empty())
{
int t=q.front();//图中边的起始下标
q.pop();
;j<num;++j)
||array[t][j]==INF)
continue;
else if(!visit[j])
{
cout<<info[j]<<" ";
visit[j]=true;
q.push(j);
}
}
}
}
/***************图用邻接表表示***************/
//邻接表中处头结点外的每个结点
typedef struct Node
{
int index;//该边的另一个顶点在顶点表中的下标
Node *next;//依附该顶点的下一条边信息
}Node;
//邻接表中的头结点
typedef struct Head_node
{
string data;
Node *first;//依附顶点的第一条边的信息
}Head_node;
//封装成邻接表:就是对每个结点建一条链表
class Graph_l
{
private:
int num;//顶点数
int e;//边数
bool *visit;
Head_node *node;
public:
Graph_l();
~Graph_l();
void print_g();
void dfs(int begin);
};
//构造函数
Graph_l::Graph_l()
{
cout<<" 请输入图的顶点的个数:"<<endl;
cin>>num;
cout<<" 请输入图的边数:"<<endl;
cin>>e;
//初始化visit,设置每个结点都未访问过
visit=new bool[num];
;i<num;++i)
visit[i]=false;
//为邻接表动态申请存储空间,并初始化
node=new Head_node[num];
cout<<" 请输入每个结点的信息:"<<endl;
;i<num;++i)
{
cin>>node[i].data;
node[i].first=NULL;
}
cout<<" 请输入每条边的两个顶点的编号:"<<endl;
int **e_info=new int*[e];//临时的数组构造函数结束可释放
;i<e;++i)
{
e_info[i]=];
cin>>e_info[i][]>>e_info[i][];//e_info[i][0]存放边的起始点，e_info[i][1]存放边的结束点
}
;i<e;++i)
{
Node *next=new Node;
next->index=e_info[i][]-;
next->next=NULL;
//判断该顶点的边是否有依附
]-].first==NULL)
node[e_info[i][]-].first=next;
else//寻找邻接表的最后一个节点
{
Node *now;
now=node[e_info[i][]-].first;
while(now->next)
now=now->next;
now->next=next;
}
}
//释放e_info
;i<num;++i)
delete []e_info[i];
delete []e_info;
}
//析构函数
Graph_l::~Graph_l()
{
delete []node;
delete []visit;
}
//打印邻接链表的函数
void Graph_l::print_g()
{
cout<<" 该图的邻接表表示为:"<<endl;
;i<num;++i)
{
//输出结点的数据
cout<<node[i].data<<" ";
//依附头节点的第一个结点
Node *now=node[i].first;
while(now)
{
//输出依附该边的结点的另一个坐标
cout<<now->index<<" ";
now=now->next;
}
cout<<endl;
}
cout<<endl;
}
//深度优先搜索算法实现
void Graph_l::dfs(int begin)
{
queue<int> q;
;i<num;++i)
+i]%num)
{
cout<<node[(begin-+i)%num].data<<" ";
visit[(begin-+i)%num]=true;
q.push((begin-+i)%num);
while(!q.empty())
{
int t=q.front();
q.pop();
Node *next=node[t].first;
while(next)
{
if(!visit[next->index])
{
cout<<node[next->index].data<<" ";
visit[next->index]=true;
q.push(next->index);
}
next=next->next;
}
}
}
}
int main()
{
//图的邻接矩阵
Graph_a g;
g.print_gra();
g.dfs();
//图的邻接表
Graph_l G;
G.print_g();
G.dfs();
;
}
以上都是基于无向图的写法，有向图的写法在创建邻接表或邻接矩阵时，遍历时稍加修改即可