dfs是邻接表和邻接矩阵通用吗

发布网友发布时间：2023-02-04 01:57

共1个回答

热心网友时间：2024-11-30 14:44

本文将先介绍图的存储方式：邻接矩阵和邻接表，接着介绍图的基本算法：广度优先搜索和深度优先搜索。
图及其存储方式
图是一种非线性的数据结构。在图论中，图是一种数学结构，用来表示一组对象，这些对象之间有一些成对的关系。对象可以包含任意信息，例如单个值、某段代码或公司员工的姓名，具体取决于图的用途。
这里我们尽可能简单地用一个字母标识每个对象，将图中对象称为顶点(vertices)，对象间关系称为边(edges)。使用 G = ( V , E ) G = (V,E) G=(V,E) 描述顶点V 和边E 的集合，顶点V 的个数为 n = ∣ V ∣ n = |V| n=∣V∣，边的个数 m = ∣ E ∣ m = |E| m=∣E∣。

边用于描述顶点的移动，这种移动称为路径，边可以是有方向的，也可以是无方向的。也就是说，通过多个顶点到顶点的边，可能从顶点y到达顶点v。图中y到v的路径可以记为： y ∗ → G v _y \ \underrightarrow{*}_G\ {_v} y ∗G v 。图可以有一个根节点r，表示图的起点，这时候图记为 G = ( V , E , r ) G=(V,E,r) G=(V,E,r)。
度（Degree）：在无向图中，用于表示一个顶点有多少条边。在有向图中，又把度分为入度（In-Degree）和出度（Out-Degree）。
入度：表示有多少条边指向一个顶点
出度：表示有多少条边从这个顶点指向其他顶点。
一般会使用邻接矩阵（Adjacency Matrix）和邻接表（Adjacency List）两种方式存储图。
邻接矩阵：邻接矩阵是一种比较直观的存储方式，使用一个二维数组 Adj[i][j] 。对于无向图，若顶点 i 和 j 之间存在边，则 Adj[i][j] 和 Adj[j][i] 的值为 1；对于有向图，若顶点 i 和 j 之间存在由顶点 i 指向 j 的边，则 Adj[i][j] 的值为 1。若图的边有权值，则数组中存入权值即可。
邻接表：使用链表数组 Adj[N] 来存储，每个顶点使用一个链表，数组大小 N 为顶点个数。Adj[u] 表示所有和顶点 u 相连的节点。
这里直接使用算法导论上的原图。邻接矩阵和连接表的优缺点也非常明显。邻接矩阵的优点是比较直观，两个顶点的关系比较容易计算，缺点是比较浪费存储空间，尤其对于稀疏图。而邻接表的优点是比较节省存储空间，而缺点是两个顶点的关系计算相对比较困难一些。实际应用需要根据场景和需求选择合适的存储方式。

邻接矩阵存储的参考代码：

#define MaxVertexNum 10
typedef char VertexType;
typedef int EdgeType;

typedef struct
{
VertexType vertex[MaxVertexNum];
EdgeType edge[MaxVertexNum][MaxVertexNum];
int vexnum, edgenum;
} AdjMatGraph;
登录后复制

邻接表参考代码：

#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;

typedef struct Edge{
int adjvex; //边指向的顶点的位下标
EdgeType weight; //权值
struct Edge *next;//指向下一个邻接点
}Edge;

typedef struct Vertex{
VertexType value; //顶点信息
Edge *firstedge; //边指针
}Vertex, AdjList[MaxVertexNum];

typedef struct{
AdjList adjList;
int vexnum, edgenum;
}AdjListGraph;
登录后复制

如果你的图没有权值，顶点信息比较简单，也可以直接使用 C++ 的 vector 表示：

std::vector<std::vector<int>> graph;
登录后复制
广度优先搜索
广度优先搜索（BFS：Breadth-first search）是从源节点到达所有节点，并且从已发现节点搜索未发现节点的时候，始终是从已发现节点的广度方向展开，这优点类似树的层次遍历。BFS 算法生成以源节点 s 到达所有节点 v 的一棵广度优先搜索树。

借助队列，BFS 算法流程如上图所示。以邻接表存储为例，给出 BFS 的算法：
bool visited[MaxVertexNum];
void BFS(const AdjListGraph& g) {
for (int i = 0; i < g.vexnum; i++) {
visited[i] = false;
}
queue<int> q;
for (int i = 0; i < g.vexnum; i++) { // 防止存在非联通子图
if (!visited[i]) {
visited[i] = true;
// visit
cout << g.adjList[i].value;
q.push(i);
while (!q.empty()) {
int u = q.front();
q.pop();
for (Edge* edge = g.adjList[u].firstedge; edge != nullptr; edge = edge->next) {
if (!visited[edge->adjvex]) {
// visit
cout << g.adjList[edge->adjvex].value;
visited[edge->adjvex] = true;
q.push(edge->adjvex);
}
}
}
}
}
cout << endl;
}
登录后复制

深度优先搜索
深度优先搜索（DFS：Depth-first search）尽可能深地搜索一个图。首先访问其实一个起始节点 v，然后访问 v 的一个邻接节点 w，接着 w 的邻接节点。重复上述过程，当无法继续访问时，则回退到最近访问的节点，继续上述过程，直到所有节点都被访问过。

DFS 算法的递归方式比较简单：

bool visited[MaxVertexNum];
void dfs(const AdjListGraph& g, int u) {
// visit
cout << g.adjList[u].value;
visited[u] = true;
for (Edge* edge = g.adjList[u].firstedge; edge != nullptr; edge = edge->next) {
if (!visited[edge->adjvex]) {
dfs(g, edge->adjvex);
}

}
}
void DFS(const AdjListGraph& g) {
for (int i = 0; i < g.vexnum; i++) {
visited[i] = false;
}
for (int i = 0; i < g.vexnum; i++) { // 防止存在非联通子图
if (!visited[i]) {
dfs(g, i);
}
}
}
最后，附上本文源码，方便大家验证。

#include<iostream>
#include<queue>
#include<memory>

using namespace std;

#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;

typedef struct Edge{
int adjvex; //边指向的顶点的位下标
// EdgeType weight; //权值
struct Edge *next;//指向下一个邻接点
}Edge;

typedef struct Vertex{
VertexType value; //顶点信息
Edge *firstedge; //边指针
}Vertex, AdjList[MaxVertexNum];

typedef struct{
AdjList adjList;
int vexnum, edgenum;
}AdjListGraph;

// lookup index of vertex u in the graph
int LocateVex(const AdjListGraph& g, VertexType u)
{
int i;
for(i = 0; i < g.vexnum; ++i)
if(u == g.adjList[i].value)
{
return i;
}

return -1;
}

void printGraph(const AdjListGraph& g)
{
for(int i = 0; i < g.vexnum; i++)
{
cout << g.adjList[i].value;
Edge* edge = g.adjList[i].firstedge;
while(edge != nullptr)
{
cout << "->" << g.adjList[edge->adjvex].value;
edge = edge->next;
}
cout << endl;
}
}

void deleteGraph(AdjListGraph& g) {
// TODO
}

void createGraph(AdjListGraph &g) {
cout << "Enter vertex num: ";
cin >> g.vexnum;
cout << "Enter edge num: ";
cin >> g.edgenum;

cout << "Enter " << g.vexnum << " vertex value: ";
for (int i = 0; i < g.vexnum; i++) {
cin >> g.adjList[i].value;
g.adjList[i].firstedge = nullptr;
}

cout << "Enter" << g.edgenum << " edge info:" << endl;
for (int e = 0; e < g.edgenum; e++) {
VertexType v1, v2;
cin >> v1 >> v2;
int i = LocateVex(g, v1);
int j = LocateVex(g, v2);
if (i == -1 || j == -1) {
cout << "Error edge info" << endl;
}

Edge* e1 = new Edge();
e1->adjvex = j;
e1->next = g.adjList[i].firstedge;
g.adjList[i].firstedge = e1;

Edge* e2 = new Edge();
e2->adjvex = i;
e2->next = g.adjList[j].firstedge;
g.adjList[j].firstedge = e2;
}
}

bool visited[MaxVertexNum];
void BFS(const AdjListGraph& g) {
for (int i = 0; i < g.vexnum; i++) {
visited[i] = false;
}
queue<int> q;
for (int i = 0; i < g.vexnum; i++) {
if (!visited[i]) {
visited[i] = true;
// visit
cout << g.adjList[i].value;
q.push(i);
while (!q.empty()) {
int u = q.front();
q.pop();
for (Edge* edge = g.adjList[u].firstedge; edge != nullptr; edge = edge->next) {
if (!visited[edge->adjvex]) {
// visit
cout << g.adjList[edge->adjvex].value;
visited[edge->adjvex] = true;
q.push(edge->adjvex);
}
}
}
}
}
cout << endl;
}

void dfs(const AdjListGraph& g, int u) {
// visit
cout << g.adjList[u].value;
visited[u] = true;
for (Edge* edge = g.adjList[u].firstedge; edge != nullptr; edge = edge->next) {
if (!visited[edge->adjvex]) {
dfs(g, edge->adjvex);
}

}
}

void DFS(const AdjListGraph& g) {
for (int i = 0; i < g.vexnum; i++) {
visited[i] = false;
}
for (int i = 0; i < g.vexnum; i++) {
if (!visited[i]) {
dfs(g, i);
}
}
}

int main () {
AdjListGraph g;
createGraph(g);
printGraph(g);
BFS(g);
DFS(g);
deleteGraph(g);
}
登录后复制

reference:

算法导论
https://blog.51cto.com/u_15346415/3674106
数据结构
算法
深度优先搜索
广度优先搜索
BFS
贵阳【零跑T03】全系直降!
零跑汽车
广告

邻接表或者邻接矩阵为存储结构实现连通无向图的深度优先和广度优先遍历
187下载·1评论
2015年12月6日
图的深度优先遍历DFS和广度优先遍历BFS（邻接矩阵存储）超详细完整代码简单版
3732阅读·0评论·10点赞
2021年4月14日
深度优先搜索（邻接表）
831阅读·0评论·1点赞
2018年11月1日
基于邻接矩阵的有向图的广度优先遍历(BFS)和深度优先遍历(DFS)算法
337阅读·0评论·1点赞
2022年10月19日
数据结构之图:邻接矩阵和邻接表、深度优先遍历和广度优先遍历
2.7W阅读·4评论·34点赞
2020年6月21日
数据结构-图的存储(邻接矩阵,邻接表)及遍历(dfs,bfs)
1259阅读·0评论·1点赞
2021年1月30日
购蔚来告别高油价！蔚来买车不用买电池，终身免费换电，充电无忧

蔚来
广告
广度优先遍历（邻接表，邻接矩阵）
1181阅读·0评论·0点赞
2022年10月21日
广度优先搜索（邻接矩阵、邻接表）
204阅读·0评论·0点赞
2022年9月10日
深度优先遍历
6674阅读·0评论·1点赞
2018年9月5日
图的邻接矩阵和邻接表存储的深度优先遍历（DFS）算法实现
6781阅读·1评论·2点赞
2018年3月7日
利用邻接矩阵进行的深度优先和广度优先遍历（含全部代码+图解）
8708阅读·4评论·26点赞
2022年4月29日
图的邻接表存储，建立，深度优先搜索，广度优先搜索
209阅读·0评论·1点赞
2022年9月26日
【数据结构】DFS深度优先搜索（分别使用邻接矩阵、邻接表）
1683阅读·1评论·8点赞
2017年6月23日
数据结构-图的邻接矩阵创建以及遍历输出（C语言）
2806阅读·1评论·3点赞
2021年12月2日
求图的最短路径（迪杰斯特拉算法）
217阅读·1评论·1点赞
2020年12月4日
连通图的广度优先搜索实现-邻接表表示图
531阅读·0评论·0点赞
2020年6月1日
邻接矩阵存储图的深度优先遍历(dfs)和广度优先遍历(bfs)
863阅读·1评论·5点赞
2022年3月15日
图的存储结构（邻接矩阵）- 数据结构和算法56
369阅读·0评论·0点赞
2013年5月2日
分别用邻接矩阵和邻接表实现图的深度优先遍历和广度优先遍历_图搜索
2024阅读·0评论·3点赞
2020年11月22日
邻接表的深度优先搜索技术
498阅读·0评论·0点赞
2022年1月12日
去首页
看看更多热门内容