大家好,又见面了,我是你们的朋友全栈君。
图的遍历分为深度优先遍历(Depth_First_Search)和广度优先遍历(Breadth_First_Search),
分别简称为DFS和BFS。
图的遍历是从某一个顶点出发,访问其他顶点,但是不能重复访问(每个顶点只能访问一次)。
深度优先遍历(DFS):
深度优先,就是沿着某一个方向不重复的一直便利下去,若走到尽头,退到上一个顶点,寻找附近有没有顶点,有且不重复的话,接着便利,否则退到上一个顶点。
下面我来讲解下DFS到底是怎么样实现的……
以下面的图为例吧,,
下面是这个图的DFS遍历过程(黑色背景表示已访问过):
上面的遍历过程我来解释下:
我们起始位置时V0,根据箭头的指向,V0->V4,
然后V4周围没有邻接点了,退到V0,V0周围除了V4也没有邻接点(不能重复访问顶点),
接着我们新找一个顶点V1,V1周围有V0和V2,V0已访问过,遍历V2,V1->V2,
V2周围有V0和V3,遍历V3,V1->V2->V3,
V3周围有V2和V4,遍历V4,V1->V2->V3->V4,
V4周围有V0和V3,返回上一个顶点,指到结束。
emmm,下面我用了邻接矩阵的方式,
对了,邻接矩阵其实也可以自己构建,只要把每个顶点与另一个顶点之间的关系写对,就行了
代码如下:
#include <iostream>
using namespace std;
bool visited[5]; //标记顶点是否访问过
//邻接矩阵
int MGraph[5][5] = {
{0, 0, 0, 0, 1},
{1, 0, 1, 0, 0},
{1, 0, 0, 1, 0},
{0, 1, 0, 0, 1},
{0, 0, 0, 0, 0}
};
//DFS
void DFS(int MGraph[][5], int i)
{
visited[i] = true;
cout << i;
for(int j = 0; j < 5; j++)
{
if(MGraph[i][j] && !visited[j])
DFS(MGraph, j);
}
}
void DFSTraverse(int MGraph[][5])
{
for(int i = 0; i < 5; i++)
visited[i] = false; //将顶点初始化为未访问
for(int i = 0; i < 5; i++)
{
if(!visited[i]) //对未访问过的顶点调用DFS,如是连通图,只执行一次(我这个不是连通图)
DFS(MGraph, i);
}
}
int main()
{
DFSTraverse(MGraph);
return 0;
}
时间复杂度:若顶点数是n,因为是邻接矩阵,它是个二维数组遍历完成则需要O(n^2)。
运行结果:
遍历的结果是:04123,与上图对应。
下面是邻接表的代码(DFS是主体,邻接表的代码就不需要看了):
#include <iostream>
using namespace std;
//开始 邻接表请看上一节
#define MAXVERTEX 100
typedef char vertextype;
typedef struct ArcNode
{
int adjvex;
struct ArcNode *next;
}ArcNode;
typedef struct VertexNode
{
vertextype data;
ArcNode *firstarc;
}VertexNode, AdjList[MAXVERTEX];
typedef struct
{
AdjList adjlist;
int numvertex;
int numarc;
}GraphAdjList;
void CreateAdjListGraph(GraphAdjList &G)
{
ArcNode *e;
cin >> G.numvertex;
cin >> G.numarc;
for(int i = 0; i < G.numvertex; i++)
{
cin >> G.adjlist[i].data;
G.adjlist[i].firstarc = NULL;
}
for(int k = 0; k < G.numarc; k++)
{
int i, j;
cin >> i >> j;
e = new ArcNode;
e->adjvex = j;
e->next = G.adjlist[i].firstarc;
G.adjlist[i].firstarc = e;
}
}
//打印邻接表
void PrintfGraphAdjList(GraphAdjList G)
{
for(int i = 0; i < G.numvertex; i++)
{
ArcNode *p = G.adjlist[i].firstarc;
cout << G.adjlist[i].data << '\t';
while(p)
{
cout << p->adjvex << '\t';
p = p->next;
}
cout << endl;
}
}
//邻接表 结束
bool visited[5]; //用于判断顶点是否被访问过
//DFS
void DFS(GraphAdjList G, int i)
{
ArcNode *p;
p = G.adjlist[i].firstarc;
visited[i] = true; //将访问过的顶点置位true
cout << G.adjlist[i].data;
while(p)
{
if(!visited[p->adjvex])
DFS(G, p->adjvex);
p = p->next;
}
}
void DFSTraverse(GraphAdjList G)
{
for(int i = 0; i < G.numvertex; i++)
visited[i] = false; //将顶点初始化为未访问状态
for(int i = 0; i < G.numvertex; i++)
{
if(!visited[i]) //若顶点没被访问过
DFS(G, i);
}
}
int main()
{
GraphAdjList G;
CreateAdjListGraph(G);
PrintfGraphAdjList(G);
DFSTraverse(G);
return 0;
}
时间复杂度:顶点数是n,边数是e,顶点循环是n,加上DFS里面while(p),边循环了e次,所以是O(n + e)。
运行结果:
两个运行结果都是04123,,,
广度优先遍历(BFS):
从一点出发,先寻找离它最近的几个顶点,然后继这几个顶点再次深入,但是每次搜寻的都是同一级别的(根据离顶点的距离)。
下面我画一个图:
深度优先遍历(DFS):
下面是遍历过程(左右上下的顺序):
emmm,解释下这个遍历过程,不过相信大家也能看懂吧(按照离起始点的远近依次访问)
广度搜索,也就是优先广范围搜索,我们从顶点0开始访问,先访问离它最近的顶点,2和6
这样0->2->6
然后再从2开始访问离它最近的顶点3,7和8
这样0->2->6->3->7->8
然后退回去再从离6最近的5和7访问,7访问过
这样0->2->6->3->7->8->5
然后是3周围的4,接着是7周围的1,这样我们就全部遍历了
最后的流程是0->2->6->3->7->8->5->4->1
然后理解了它的思想后就是代码了,下面是邻接矩阵的BFS:
#include <iostream>
#include <queue>
using namespace std;
//邻接矩阵
int mgraph[9][9] = {
{0, 0, 1, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 1, 1, 0, 1, 0},
{1, 0, 0, 1, 0, 0, 0, 1, 1},
{0, 0, 1, 0, 1, 0, 0, 0, 1},
{0, 1, 0, 1, 0, 1, 0, 0, 1},
{0, 1, 0, 0, 1, 0, 1, 0, 0},
{1, 0, 0, 0, 0, 1, 0, 1, 0},
{0, 1, 1, 0, 1, 0, 1, 0, 0},
{0, 0, 1, 1, 1, 0, 0, 0, 0}
};
//定义一个队列
queue <int> q;
// 定义判断顶点是否被访问过的数组
bool visited[9];
//BFS
void BFSTraverse(int mgraph[][9])
{
for(int i = 0; i < 9; i++)
visited[i] = false;
for(int i = 0; i < 9; i++)
{
if(!visited[i])
{
cout << i;
visited[i] = true;
q.push(i);
}
while(!q.empty())
{
i = q.front();
q.pop();
for(int j = 0; j < 9; j++)
{
if(mgraph[i][j] == 1 && !visited[j])
{
visited[j] = true;
cout << j;
q.push(j);
}
}
}
}
}
int main()
{
BFSTraverse(mgraph);
return 0;
}
时间复杂度:与DFS一样还是O(n^2),
运行结果:
对吧,只要邻接矩阵构建的没有问题,运行结构就跟上面所构造的图一样。
接着是邻接表的BFS代码:
#include <iostream>
#include <queue>
using namespace std;
//开始 邻接表请看上一节
#define MAXVERTEX 100
typedef char vertextype;
typedef struct ArcNode
{
int adjvex;
struct ArcNode *next;
}ArcNode;
typedef struct VertexNode
{
vertextype data;
ArcNode *firstarc;
}VertexNode, AdjList[MAXVERTEX];
typedef struct
{
AdjList adjlist;
int numvertex;
int numarc;
}GraphAdjList;
void CreateAdjListGraph(GraphAdjList &G)
{
ArcNode *e;
cin >> G.numvertex;
cin >> G.numarc;
for(int i = 0; i < G.numvertex; i++)
{
cin >> G.adjlist[i].data;
G.adjlist[i].firstarc = NULL;
}
for(int k = 0; k < G.numarc; k++)
{
int i, j;
cin >> i >> j;
e = new ArcNode;
e->adjvex = j;
e->next = G.adjlist[i].firstarc;
G.adjlist[i].firstarc = e;
e = new ArcNode;
e->adjvex = i;
e->next = G.adjlist[j].firstarc;
G.adjlist[j].firstarc = e;
}
}
//打印邻接表
void PrintfGraphAdjList(GraphAdjList G)
{
for(int i = 0; i < G.numvertex; i++)
{
ArcNode *p = G.adjlist[i].firstarc;
cout << G.adjlist[i].data << '\t';
while(p)
{
cout << p->adjvex << '\t';
p = p->next;
}
cout << endl;
}
}
//邻接表 结束
//定义一个队列
queue <int> q;
// 定义判断顶点是否被访问过的数组
bool visited[9];
//BFS
void BFSTraverse(GraphAdjList G)
{
ArcNode *p;
for(int i = 0; i < 9; i++)
visited[i] = false;
for(int i = 0; i < 9; i++)
{
if(!visited[i])
{
cout << i;
visited[i] = true;
q.push(i);
}
while(!q.empty())
{
i = q.front();
q.pop();
p = G.adjlist[i].firstarc;
while(p)
{
if(!visited[p->adjvex])
{
visited[p->adjvex] = true;
cout << p->adjvex;
q.push(p->adjvex);
}
p = p->next;
}
}
}
}
int main()
{
GraphAdjList G;
CreateAdjListGraph(G);
PrintfGraphAdjList(G);
BFSTraverse(G);
return 0;
}
时间复杂度:O(n + e)。
运行结果:
emmm,虽然结果和上面不一样,但是层次都是一样的,按照离起始点的距离
分为4层,第一层是0,第二层是26,第三层是3578,第四层是14,输入的顺序不对,然后排出来的就不对,然是层次肯定是对的。
emmm,就这样吧!
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/132281.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...