lisp遍历表中所有顶点_数据结构-图和图遍历(DFS、BFS)

梦里梦外; 2023-01-08 15:27 168阅读 0赞

一、图的定义和相关术语

图是由顶点(Vertex)和边(Edge)

图可以分为有向图和无向图，无向图所有边都是双边的

顶点的度是指该顶点相连的边的条数，特别是对于有向图的边数称为顶点的出度，顶点的入边条数称为该顶点的入度。

顶点和边都可以有一定的属性，量化的属性称为权值，顶点的权值和边的权值分别称为点权和边权。

二、图的存储

一般图来说存储方式有两种：邻接矩阵和邻接表

邻接矩阵，本质上是一个二维数组，里面可以存放权值，但是是开辟了一个二维数组，不能够开辟很大的，一般的结点数不能超过1000。

邻接表， N个顶点就会有N个列表，常常使用vector来实现邻接表。

vector Adj\[N\];

Adj\[1\].push\_back(3);

struct Node\{

int v;

int w;

\};

vector Adj\[N\];

//如果想添加边

Node temp;

temp.v = 3;

temp.w = 4;

Adj\[1\].push\_back(temp);

//更快的方式，用定义结构体Node时构造函数

struct Node\{

int v, w;

Node(int \_v, int \_w) : v(\_v), w(\_w) \{\}

//这样就可以不用定义临时变量

Adj\[1\].push\_back(Node(3, 4));

三、图的遍历

一般有两种深度优先搜索(DFS)和广度优先搜索(BFS)

1. 采用深度优先搜索法遍历图

连通分量，在无向图中，如果图的任意两个点都可以连通，则称图G为连通图；否则称为非连通图，且称其中的极大连通子图为连通分量。

强连通分量，在有向图中，如果两个顶点都可以通过一条有向路径到达另一个顶点，就称为这两个顶点强连通。如果这个图任意两个顶点都是强连通，那么就称这个图是强连通图；否则图就是非强连通图，且其中极大强连通子图为强连通分量。

把连通分量和强连通分量均称为连通块

代码实现

//伪代码

DFS(u)\{//访问顶点u

vis\[u\] = true;

for(从u出发能够达到的所有顶点v)\{

if(vis\[v\] == false) DFS(v);

DFSTrave(G)\{//遍历图

for(G的所有顶点u)\{

if(vis\[u\] == false) DFS(u);

邻接矩阵版本

const int MAXV = 1000;//最大顶点数

const int INF = 1000000000;//设INF为一个很大的数

int n, G\[MAXN\]\[MAXN\];

bool vis\[MAXV\] = \{false\};//用于判断顶点是否被访问

void DFS(int u, int depth)\{

vis\[u\] = true;

//如果需要对u进行一些操作，可以在这里进行

//下面是对所有从u出发能到达的分支顶点进行枚举

for(int v = 0; v < n; v++)\{

if(vis\[v\] == false && G\[u\]\[v\] != INF)\{

DFS(v, depth+1);

void DFSTrace()\{//遍历图

for(int u = 0; u < n; u++)\{//对于每个顶点

if(vis\[u\] == false)\{

DFS(u, 1);//访问u和u所在的连通块，1表示初始为第一层

邻接表

vector Adj\[MAXN\];//图G的邻接表

int n;//n为顶点数，MAXN为最大顶点数

bool vis\[MAXN\] = \{false\};

void DFS(int u, int depth)\{

vis\[u\] = true;

//一些操作也可在此处进行操作

for(int i = 0; i < Adj\[u\].size(); i++)\{

int v = Adj\[u\]\[i\];

if(vis\[v\] == false)\{

DFS(v, depth+1);

void DFSTrace()\{

for(int u = 0; u < n; u++)\{

if(vis\[u\] == false)\{

DFS(u, 1);

2. 采用广度优先搜索法遍历图

具体实现，就是建立一个队列，并且把初始顶点加入队列，此后每次都取出队首顶点进行访问，并且把该顶点可以到达的的未曾到过的结点加入队列(注意不是访问，而是加入)，直到队列为空。

伪代码

BFS(u)\{

queue q;

将u入队列;

inq\[u\] = true;

while(q非空)\{

取出队首元素u进行访问;

for(遍历该顶点可以到的所有结点v)\{

if(inq\[v\] == false)\{

将v入队列;

inq\[v\] = true;

BFSTrace(G)\{

for(G所有结点)\{

if(inq\[u\] == false)\{

BFS(u);

邻接矩阵版

const int maxn;

const int INF;

int n;

vector G\[maxn\]\[maxn\];

bool inq\[maxn\] = \{false\};

void BFS(int u)\{

queue q;

q.push(u);

inq\[u\] = true;

while(!q.empty())\{

int now = q.front();

q.pop();

for(int i = 0; i < n; i++)\{//这里直接数遍历所有结点，而不是这个Adj\[now\].size()

if(inq\[v\] == false && G\[now\]\[v\] != INF)\{

q.push(v);

inq\[v\] = true;

void BFSTrace()\{

for(int u = 0; i < n; u++)\{

if(inq\[u\] == false)\{

BFS(q);

邻接表版

vector Adj\[maxn\];

int n;

bool inq\[maxn\];

BFS(int u)\{

queue q;

q.push(u);

inq\[u\] = true;

while(!q.empty())\{

int u = q.front();

q.pop();

for(int i = 0; i < Adj\[u\].size(); i++)\{

int v = Adj\[u\]\[i\];

if(inq\[v\] == false)\{

q.push(v);

inq\[v\] = true;

void BFSTrace()\{

for(int u = 0; u < n; u++)\{

if(inq\[u\] == false)\{

BFS(u);

如果需要层号邻接表版

struct Node\{

int v;

int layer;

\};

vector Adj\[maxn\];

void BFS(int s)\{

queue q;

Node start;

start.v = s;

start.layer = 0;

q.push(start);

inq\[start.v\] = true;

while(!q.empty())\{

Node topNode = q.front();

q.pop();

int u = topNode.v;

for(int i = 0; i < Adj\[u\].size(); i++)\{

Node next = Adj\[u\]\[i\];

next.layer = topNode.layer + 1;

if(inq\[next.v\] == false)\{

q.push(next);

inq\[next.v\] = true;

lisp遍历表中所有顶点_数据结构-图和图遍历(DFS、BFS)

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关图的深度遍历和广度遍历

相关 lisp遍历表中所有顶点_数据结构-图和图遍历(DFS、BFS)

相关前序遍历、中序遍历、后序遍历、层次遍历

相关 java遍历之数组遍历,list遍历,set遍历,map遍历，stream遍历,Enumeration遍历

相关有向图遍历，十字链表存储，深度遍历，广度遍历。

相关数据结构图的深度遍历和广度遍历源程序

相关 TinkerPop中的遍历：图的遍历策略

相关 TinkerPop中的遍历：图的遍历策略

相关图的遍历（深度优先遍历和广度优先遍历）

相关图的遍历（广度优先遍历、深度优先遍历）