数据结构 图的遍历

数据结构 图的遍历图的遍历分为深度优先遍历(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)
blank

相关推荐

  • python官网下载步骤64位-windows下载并安装Python的具体步骤

    python官网下载步骤64位-windows下载并安装Python的具体步骤安装Python下载并安装PythonPython的官网是www.python.org,我们可以直接从官网下载Python。这里介绍在微软Windows和苹果MacOS两种系统中的安装方式。如果Python官网页面之后有所更新,那请大家用自己的思维能力和观察力,大胆地尝试,推测如何下载安装,解决问题。1.5.1Windows系统进入https://www.python.org/页面,选…

  • linux的上传和下载命令_yum安装rz命令

    linux的上传和下载命令_yum安装rz命令要使用rz、sz命令传输文件需要给服务器安装lrzsz:yum-yinstalllrzsz命令sz、rz的使用方法rz中的r意为received(接收),输入rz时,意为服务器接收文件,即将文件从本地上传到服务器。sz中的s意为send(发送),输入sz时,意为服务器要发送文件,既从服务器发送文件到本地,或是说本地从服务器上下载文件。注意:不论是send还是rec…

  • Lytro光场相机上手视频

    Lytro光场相机上手视频这会儿大家都知道光场相机Lytro了,用一个词来形容的话,应该是“新颖”,你在生活中肯定很难想到相机还可以这么玩。相信你第一印象应该是其微小的体积。如果要你坦率地说,毫无疑问你希望得到一个单反。其细小的身躯,精细的做工让我们想到了iPodNano和iSight,而其桌面的软件当前也只支持Mac,Windows版本正在开发中。视频1…

    2022年10月22日
  • R-向量内积外积[通俗易懂]

    R-向量内积外积[通俗易懂]http://f.dataguru.cn/thread-310494-1-1.htmlhttps://blog.csdn.net/paoxungan5156/article/details/83620632

  • 深入Springboot启动流程+自动配置原理

    深入Springboot启动流程+自动配置原理深入Springboot启动流程+自动配置原理?写在前面?相关常见面试题Springboot启动入口@SpringBootConfiguration解读@ComponentScan解读@EnableAutoConfiguration解读(重点)@AutoConfigurationPackage解读@Import({AutoConfigurationImportSelector.class})解读(重点)?写在前面?自从SpringBoot问世以来,开发界可以说是乱了套。我还记得我朋友几年前去参加

  • free技术详解 lock_lock free的理解

    free技术详解 lock_lock free的理解转自:http://www.isnowfy.com/understand-to-lock-free/以前一直不明白lockfree是什么,后来发现原来是完全理解错了概念,lockfree看到大家有的翻译为无锁,有的翻译为锁无关,其实用不用锁和lockfree是不相关的,用了锁也可能是lockfree,而不用锁有可能不是lockfree。一个lockfree的解释是一个“锁无关”的程序能…

发表回复

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

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