当前位置 博文首页 > ice_elephant的博客：图的深度遍历和广度遍历
故事情节
Jack 自从买车后，交通出行方便了，心自然就野了！身边的各种朋友自然就多了起来！
有一天晚上，一个年轻漂亮的女同事生日，Jack 受邀请准时爽约！Jack 亲睐此女已久，只是介于家里的 LD 不敢越雷池一步，但是，一有机会，Jack 都会和此女接近，经常在一起，所以可以说是就当个哥们吧！Jack 当晚开心的和女同事喝酒、聊天，忘记了家的存在，不知不觉时间一下子指向了 10 点！此时，正沉浸在幻想中的 Jack 被老婆电话惊醒！不用接都知道，老婆的“圣旨”又来了！这下麻烦来了，老婆电话一到，必须半小时内到家，否则，皮都可能被母老虎拔了，但现在自己渴了酒，叫代驾又需要很久的时间，这一想, Jack 觉得自己麻烦来了！
在计算机科学中，一个图就是一些顶点的集合，这些顶点通过一系列边结对（连接）。顶点用圆圈表示，边就
是这些圆圈之间的连线。顶点之间通过边连接。注意：顶点有时也称为节点或者交点，边有时也称为链接。
社交网络，每一个人就是一个顶点，互相认识的人之间通过边联系在一起, 边表示彼此的关系。这种关系可以
是单向的，也可以是双向的！
? 首先以一个未被访问过的顶点作为起始顶点，访问其所有相邻的顶点;
? 然后对每个相邻的顶点，再访问它们相邻的未被访问过的顶点，直到所有顶点都被访问过，遍历结束。
? 首先以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点；
? 当没有未访问过的顶点时，则回到上一个顶点，继续试探别的顶点，直到所有的顶点都被访问过。
使用深度优先搜索来遍历这个图的具体过程是：
#include<stdio.h>
#include<Windows.h>
#include<iostream>
#include<queue>
using namespace std;
#define MAX_SIZE 1024
typedef struct _EdgNode{//定义边
int adjvex; //邻接的顶点
int weight; //权重
_EdgNode *next;//下一条边
}EdgNode;
typedef struct _VertexNode{//顶点节点
char date;//节点名A,B,C
EdgNode *first;//邻接的第一条边
}VerTexNode,AdjList;
typedef struct _AdjListGraph{
AdjList *adjlist;
int vex;//顶点
int edge;//边数
}AdjListGraph;
//全局数组
bool visit[MAX_SIZE];
int Location(AdjListGraph &G,char v);
void DFS(AdjListGraph &G,char c);
//1、图的初始化
void init(AdjListGraph &G){
G.adjlist = new AdjList[MAX_SIZE];//初始化顶点的个数
G.edge = 0;//边
G.vex = 0;//顶点
for(int i=0;i<MAX_SIZE;i++){
visit[i] = false;//初始化都设为未被访问过的下一节点
}
}
//2、图的创建
void CreateDFS(AdjListGraph &G){
//初始化顶点和边
cout<<"请输入创建的顶点个数和边的个数:"<<endl;
cin>>G.vex>>G.edge;
cout<<"请输入相应的顶点:"<<endl;
//先输入具体的顶点名字
for(int i=0;i<G.vex;i++){
cin>>G.adjlist[i].date;
G.adjlist[i].first = NULL;
}
char v1=0,v2=0;
int i1,i2;
cout<<"请输入相关联的相连接的顶点"<<endl;
for(int i=0;i<G.edge;i++){
//输入进v1，输入进v2
cin>>v1>>v2;//我们要找到顶点的具体下标
i1 = Location(G,v1);
i2 = Location(G,v2);
if(v1!=-1&&v2!=-1){
//来进行插入节点
EdgNode *Edg = new EdgNode;
Edg->adjvex = i2;
Edg->next = G.adjlist[i1].first;
G.adjlist[i1].first = Edg;//
}
}
}
//3、图的Location
int Location(AdjListGraph &G,char c){
for(int i=0;i<G.vex;i++){
if(G.adjlist[i].date==c){
return i;//返回相应的下标
}
}
//否则
return -1;
}
//4、图的DFS
//作用是遍历节点
void DFS(AdjListGraph &G,int v){
int next = -1;
if(visit[v]) return;//如果访问过直接返回
cout<<G.adjlist[v].date<<" ";
visit[v] = true;//置为已访问
EdgNode *temp = G.adjlist[v].first;//通过顶点找到它的下一条边,因为边的初始fist是挂载在顶点上面的
while(temp){
next = temp->adjvex;//获取当前顶点的下一个下标位，通过vist来判断该下标是否已经访问过
temp = temp->next;
if(visit[next]==false){
DFS(G,next);
}
}
}
//深度遍历
//5、图的MAIN_DFS
void Main_DFS(AdjListGraph & G){
//遍历所有的顶点
for(int i=0;i<G.vex;i++){
if(visit[i]==false){
DFS(G,i);
}
}
}
void BFS(AdjListGraph &G,int v){
queue<int>q;
int cur;
int next=-1;
q.push(v);
while(!q.empty()){
cur = q.front();
if(visit[cur]==false){
cout<<G.adjlist[cur].date<<" ";
visit[cur] = true;
}
q.pop();
EdgNode *tp = G.adjlist[cur].first;//把所有邻接点都找出来
while(tp){
next = tp->adjvex;
tp = tp->next;
q.push(next);
}
}
}
//广度遍历
void Main_BFS(AdjListGraph &G){
//遍历所有的顶点
for(int i=0;i<G.vex;i++){
if(visit[i]==false){
BFS(G,i);
}
}
}
void main1(){
AdjListGraph G;
init(G);
CreateDFS(G);
//cout<<"深度遍历"<<endl;
//Main_DFS(G);
cout<<"广度遍历"<<endl;
Main_BFS(G);
system("pause");
}
