数据结构 图的遍历

数据结构 图的遍历图的遍历分为深度优先遍历(Depth_First_Search)和广度优先遍历(Breadth_First_Search),分别简称为DFS和BFS。图的遍历是从某一个顶点出发,访问其他顶点,但是不能重复访问(每个顶点只能访问一次)。深度优先遍历(DFS):深度优先,就是沿着某一个方向不重复的一直便利下去,若走到尽头,退到上一个顶点,寻找附近有没有顶点,有且不重复的话,接着便利,否则退到上一个顶点…

大家好,又见面了,我是你们的朋友全栈君。

图的遍历分为深度优先遍历(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账号...

(0)


相关推荐

  • 测试管理工具列表大全「建议收藏」

    测试管理工具列表大全「建议收藏」测试管理工具列表大全IDNameNotes1TestDirector/QualityCenter业界第一个基于Web的测试管理系统,它可以在您公司组织内进行全球范围内测试的协调。通过在一个整体的应

  • MySQL触发器

    MySQL在5.0.2版本以上开始支持触发器,触发器是有某些带有命令的时间来触发某些操作,这些事件包括insert语句、delete语句、update语句等。触发器可以用于记录对数据库的操作。1、创

    2021年12月25日
  • 栈溢出

    栈溢出Author:Liedrahttps://www.cnblogs.com/LieDra/入门介绍学习自https://zhuanlan.zhihu.com/p/25816426对部分内容进行

  • 压力换算公斤单位换算_压力单位换算表

    压力换算公斤单位换算_压力单位换算表压力单位换算表来源:华强电子网作者:华仔浏览:1163时间:2016-08-1014:18标签:摘要:november6,2002牛顿/米2(帕斯卡)(n/m2)(pa)公斤力/米2(kgf/m2)公斤力/厘米2(kgf/cm2)巴(bar)标准大气压(atm)毫米水柱4oc(mmh2o)毫米水银柱0oc(mmhg)磅/英寸2(lb/in2,psi)牛顿/米2(帕斯卡)(n…

  • python的random()函数用法_Python随机函数random用法示例

    python的random()函数用法_Python随机函数random用法示例这篇文章主要为大家详细介绍了Python随机函数random用法示例,具有一定的参考价值,可以用来参考一下。对python这个高级语言感兴趣的小伙伴,下面一起跟随512笔记的小编两巴掌来看看吧!在python中用于生成随机数的模块是random,在使用前需要import,下面看下它的用法。random.randomrandom.random()用于生成一个0到1的随机符点数:0b,则生成的…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号