尼采般地抒情

公告栏

此网站主题为本人手写主题, 主题待开源···

站点信息

文章总数目: 298
已运行时间: 991
目录
  1. 一、深度优先搜索算法(Depth-First-Search)
    1. 算法说明
    2. 邻接矩阵的DFS代码
    3. 邻接表的DFS代码
  2. 二、广度优先搜索算法(Breadth-First-Search)
    1. 算法说明
    2. 邻接矩阵的 BFS 代码
    3. 邻接表的BFS代码

尼采般地抒情

尼采般地抒情

公告栏

此网站主题为本人手写主题, 主题待开源···

站点信息

文章总数目: 298
已运行时间: 991


前言:用邻接矩阵和邻接表两种图的存储形式实现DFS、BFS算法,并附例子实现。

总的来说,邻接矩阵比较好处理,没有邻接表处理那么复杂,但是数组永远不能规避的一个缺点就是内存的占用较邻接表高。


一、深度优先搜索算法(Depth-First-Search)

算法说明

访问步骤:

  • 访问顶点v;
  • 依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;
  • 若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止。


核心代码就是利用递归,以及标志数组的设定,每次访问数组元素的那一行,对那行链表进行遍历,每遍历一个链表结点,就将“其”所在的那个数组元素“点亮”。如果标志数组里面的所有元素都被访问了,说明遍历完了


深度优先搜索类似于树里面遍历算法当中的先序遍历。

邻接矩阵的DFS代码

以这个无向图为例

#include<bits/stdc++.h>

using namespace std;

#define MVNum 100
#define MaxInt 32767

typedef char VerTexType;
typedef int ArcType;

/\*\*

- 邻接矩阵存储形式
  _/
  typedef struct {
  /_ data \*/
  VerTexType vexs[MVNum]; //顶点表
  ArcType arcs[MVNum][mvnum]; //邻接矩阵
  int vexnum, arcnum; //图的当前顶点和边数
  }AMGraph;

/\*\*

- 确定 v 在 G 中的位置,即顶点数组的下标
  \*/
  int LocateVex(AMGraph &G, char v) {
  for (int i = 0; i < G.vexnum;i++) {
  if (v == G.vexs[i]){
  return i;
  }
  }
  }

/\*\*

- 如果创建无向图  
   \*/
  void CreateUDN(AMGraph &G) {
  // 采用邻接矩阵表示法,创建无向图 G
  cout << "请输入顶点数和边数:" << endl;
  cin >> G.vexnum >> G.arcnum; //输入顶点数和边数
  // 初始化顶点
  for (int i = 0; i < G.vexnum;i++){
  cout << "请输入第" << i << "个顶点值" << endl;
  cin >> G.vexs[i];
  }
  // 初始化邻接矩阵的边的权值为最大值
  for (int i = 0; i < G.vexnum;i++) {
  for (int j = 0; j < G.vexnum;j++) {
  G.arcs[i][j] = 0;
  }
  }
  // 构造邻接矩阵
  for (int k = 0; k < G.arcnum;k++) {
  cout << "请输入每条边所依附的顶点:" << endl;
  char v1, v2;
  int w = 1; //一条边所依附的顶点和权值
  cin >> v1 >> v2;
  int i = LocateVex(G, v1);
  int j = LocateVex(G, v2);
  G.arcs[i][j] = w;
  G.arcs[j][i] = w;
  }
  }

/\*\*

- 打印输出图
  \*/
  void Display(AMGraph &G) {
  for (int i = 0; i < G.vexnum;i++) {
  for (int j = 0; j < G.vexnum;j++) {
  cout << G.arcs[i][j] << " ";
  }
  cout << endl;
  }
  }

//----邻接矩阵的 DFS 遍历----

//访问标志数组,其初值为 false
bool visited[MVNum];

/\*\*

- 图 G 为邻接矩阵类型,从第 v 个顶点出发深度优先搜索遍历图 G
  \*/
  void DFS_AM(AMGraph &G, int v) {
  //访问第 v 个顶点,并置访问标志数组相应分量值为 true
  cout<<v;  
   visited[v] = true;
  //依次检查邻接矩阵 v 所在的行
  for(int w = 0; w < G.vexnum; w++)  
   //G.arcs[v][w] != 0 表示 w 是 v 的邻接点,!visited[w]表示未访问到
  if((G.arcs[v][w] != 0) && (!visited[w]))  
   DFS_AM(G, w); //递归调用 DFS_AM
  }

/\*\*

- 图 G 的储存类型任意,对非连通图 G 做深度优先遍历
  \*/
  void DFSTraverse(AMGraph &G) {
  //访问标志数组初始化
  for(int v = 0; v < G.vexnum; v++)  
   visited[v] = false;
  //循环调用 DFS
  for(int v = 0; v < G.vexnum; v++)  
   if(!visited[v])
  DFS_AM(G, v); //对尚未访问的顶点调用 DFS
  }

int main() {
AMGraph test;
CreateUDN(test);
Display(test);
DFSTraverse(test);
return 0;
}

邻接表的DFS代码

举之前上课的一张PPT例子(元素插入为后插法)

结果

#include <bits/stdc++.h>
using namespace std;

#define MVNum 100
#define MaxInt 32767

typedef char VerTexType;
typedef int OtherInfo;

/\*\*

- 邻接表存储
  \*/

/\*\*

- 存储结构
  */
  typedef struct ArcNode { //边结点  
   int adjvex; //该边所指向的结点的位置
  struct ArcNode *nextarc; //指向下一条边的指针
  OtherInfo info; //和边相关的其他信息
  }ArcNode;

typedef struct VNode { //顶点信息
VerTexType data; //数据域,存放顶点 vi 的名称或其他有关信息
ArcNode \*firstarc; //指向第一条依附该顶点的边的指针
}VNode, AdjList[MVNum]; //AdjList 表示邻接表的类型

typedef struct {
AdjList vertices;
int vexnum, arcnum; //图当前的顶点数和边数
}ALGragh; //邻接表(Adjacency List)

/\*\*

- 找到 v 顶点在图的顶点数组中的位置
  \*/
  int LocateVex(ALGragh &G, char v) {
  for (int i = 0; i < G.vexnum;i++) {
  if (v == G.vertices[i].data) {
  return i;
  }
  }
  }

/\*\*

- 邻接表创建无向图
  */
  void CreateUDG(ALGragh &G) {
  cout << "请输入顶点数和边数:" << endl;
  cin >> G.vexnum >> G.arcnum; // 邻接表的顶点数和边数
  // 初始化顶点数组
  for (int i = 0; i < G.vexnum;i++) {
  cin >> G.vertices[i].data; // 初始化顶点数组里面的结点 data
  G.vertices[i].firstarc = NULL; // 初始化顶点数组里面的结点 next 域
  }
  // 初始化所有的边
  for (int k = 0; k < G.arcnum;k++) {
  char v1, v2;
  cout << "请输入每条边所依附的顶点:" << endl;
  cin >> v1 >> v2;
  int i = LocateVex(G, v1); // 找到 v1 在顶点数组的下标
  int j = LocateVex(G, v2); // 找到 v2 在顶点数组的下标
  // 下面建立 p1 和 p2 是因为无向图,如果是有向图就没必要了只需要 p1
  // 前插
  ArcNode *p1 = new ArcNode;
  p1->adjvex = j;
  p1->nextarc = G.vertices[i].firstarc;
  G.vertices[i].firstarc = p1;
  ArcNode \*p2 = new ArcNode;
  p2->adjvex = i;
  p2->nextarc = G.vertices[j].firstarc;
  G.vertices[j].firstarc = p2;
  }
  }

/\*\*

- 打印输出图
  */
  void Display(ALGragh &G) {
  for (int i = 0; i < G.vexnum;i++) {
  cout << "结点" << i << ":";
  // 复制选中的节点数组中的结点
  VNode p;
  p = G.vertices[i];
  if (p.firstarc != NULL){
  ArcNode *temp;
  temp = G.vertices[i].firstarc;
  while (temp != NULL) {
  cout << temp->adjvex<<" ";
  temp = temp->nextarc;
  }
  cout << "\n";
  }
  }
  }

//----邻接表的 DFS 遍历----
bool visited[MVNum]; //访问标志数组,其初值为 false

void DFS_AL(ALGragh G, int v)  
{//图 G 为邻接表类型,从从第 v 个顶点出发深度优先搜索遍历图 G
cout<<v; //访问第 v 个顶点,并置访问标志数组相应分量值为 true
visited[v] = true;
ArcNode \*p;  
 p = G.vertices[v].firstarc; //p 指向 v 的边链表的第一个边结点
while(p != NULL)
{
int w = p->adjvex; //w 是 v 的邻接点
if(!visited[w]) //如果 w 未访问
DFS_AL(G, w); //递归调用 DFS_AL
p = p->nextarc; //p 指向下一个结点
}
}

void DFSTraverse(ALGragh G)
{//图 G 的储存类型任意,对非连通图 G 做深度优先遍历
for(int v = 0; v < G.vexnum; v++) //访问标志数组初始化
visited[v] = false;
for(int v = 0; v < G.vexnum; v++) //循环调用 DFS
if(!visited[v])
DFS_AL(G, v); //对尚未访问的顶点调用 DFS
}

int main() {
ALGragh test;
CreateUDG(test);
// Display(test);
DFSTraverse(test);
}

二、广度优先搜索算法(Breadth-First-Search)

算法说明

从某个顶点 V0 出发,并在访问此顶点之后依次访问 V0 的所有未被访问过的邻接点,之后按这些顶点被访问的先后次序依次访问它们的邻接点,直至图中所有和 V0 有路径相通的顶点都被访问到。

若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。


在树遍历中类似层次遍历。

邻接矩阵的 BFS 代码

还是这个例子

#include<bits/stdc++.h>
using namespace std;

#define MVNum 100
#define MaxInt 32767

typedef char VerTexType;
typedef int ArcType;

/\*\*

- 邻接矩阵的 bfs 代码
  _/
  typedef struct {
  /_ data \*/
  VerTexType vexs[MVNum]; //顶点表
  ArcType arcs[MVNum][mvnum]; //邻接矩阵
  int vexnum, arcnum; //图的当前顶点和边数
  }AMGraph;

/\*\*

- 确定 v 在 G 中的位置,即顶点数组的下标
  \*/
  int LocateVex(AMGraph &G, char v) {
  for (int i = 0; i < G.vexnum;i++) {
  if (v == G.vexs[i]){
  return i;
  }
  }
  }

/\*\*

- 创建无向网
- 如果创建无向图  
   \*/
  void CreateUDN(AMGraph &G) {
  // 采用邻接矩阵表示法,创建无向图 G
  cout << "请输入顶点数和边数:" << endl;
  cin >> G.vexnum >> G.arcnum; //输入顶点数和边数
  // 初始化顶点
  for (int i = 0; i < G.vexnum;i++){
  cout << "请输入第" << i << "个顶点值" << endl;
  cin >> G.vexs[i];
  }
  // 初始化邻接矩阵的边的权值为最大值
  for (int i = 0; i < G.vexnum;i++) {
  for (int j = 0; j < G.vexnum;j++) {
  G.arcs[i][j] = 0;
  }
  }
  // 构造邻接矩阵
  for (int k = 0; k < G.arcnum;k++) {
  cout << "请输入每条边所依附的顶点:" << endl;
  char v1, v2;
  int w = 1; //一条边所依附的顶点和权值
  cin >> v1 >> v2;
  int i = LocateVex(G, v1);
  int j = LocateVex(G, v2);
  G.arcs[i][j] = w;
  G.arcs[j][i] = w;
  }
  }

/\*\*

- 打印输出图
  \*/
  void Display(AMGraph &G) {
  for (int i = 0; i < G.vexnum;i++) {
  for (int j = 0; j < G.vexnum;j++) {
  cout << G.arcs[i][j] << " ";
  }
  cout << endl;
  }
  }

//----邻接矩阵的 BFS 遍历----

bool visited[MVNum];

void BFS_AM(AMGraph G, int v)
{//按广度优先非递归遍历连通图 G
cout<<v;
visited[v] = true; //访问第 v 个顶点,并置访问标志数组相应分量值为 true
queue<int> Q;
Q.push(v);
while(!Q.empty())
{
int u = Q.front(); //队头元素出队并置为 u
Q.pop();
for(int w = 0; w < G.vexnum; w++)
if((G.arcs[u][w] != 0) && (!visited[w])) //G.arcs[v][w] != 0 表示 w 是 v 的邻接点,!visited[w]表示未访问到 //w 为 u 的尚未访问的邻接顶点
{
cout<<w;
visited[w] = true; //访问 w,并置访问标志数组相应分量值为 true
Q.push(w); //w 进队
}
}
}

void BFSTraverse(AMGraph &G) {
//访问标志数组初始化
for(int v = 0; v < G.vexnum; v++)  
 visited[v] = false;
//循环调用 BFS
for(int v = 0; v < G.vexnum; v++)  
 if(!visited[v])
BFS_AM(G, v); //对尚未访问的顶点调用 BFS
}

int main() {
AMGraph test;
CreateUDN(test);
Display(test);
// DFSTraverse(test);
BFSTraverse(test);
return 0;
}

邻接表的BFS代码

还用和DFS一样的例子



#include <bits/stdc++.h>
using namespace std;

#define MVNum 100
#define MaxInt 32767

typedef char VerTexType;
typedef int OtherInfo;

/\*\*

- 邻接表的 bfs 代码
  \*/

/\*\*

- 存储结构
  */
  typedef struct ArcNode { //边结点  
   int adjvex; //该边所指向的结点的位置
  struct ArcNode *nextarc; //指向下一条边的指针
  OtherInfo info; //和边相关的其他信息
  }ArcNode;

typedef struct VNode { //顶点信息
VerTexType data; //数据域,存放顶点 vi 的名称或其他有关信息
ArcNode \*firstarc; //指向第一条依附该顶点的边的指针
}VNode, AdjList[MVNum]; //AdjList 表示邻接表的类型

typedef struct {
AdjList vertices;
int vexnum, arcnum; //图当前的顶点数和边数
}ALGraph; //邻接表(Adjacency List)

/\*\*

- 找到 v 顶点在图的顶点数组中的位置
  \*/
  int LocateVex(ALGraph &G, char v) {
  for (int i = 0; i < G.vexnum;i++) {
  if (v == G.vertices[i].data) {
  return i;
  }
  }
  }

/\*\*

- 邻接表创建无向图
  */
  void CreateUDG(ALGraph &G) {
  cout << "请输入顶点数和边数:" << endl;
  cin >> G.vexnum >> G.arcnum; // 邻接表的顶点数和边数
  // 初始化顶点数组
  for (int i = 0; i < G.vexnum;i++) {
  cin >> G.vertices[i].data; // 初始化顶点数组里面的结点 data
  G.vertices[i].firstarc = NULL; // 初始化顶点数组里面的结点 next 域
  }
  // 初始化所有的边
  for (int k = 0; k < G.arcnum;k++) {
  char v1, v2;
  cout << "请输入每条边所依附的顶点:" << endl;
  cin >> v1 >> v2;
  int i = LocateVex(G, v1); // 找到 v1 在顶点数组的下标
  int j = LocateVex(G, v2); // 找到 v2 在顶点数组的下标
  // 下面建立 p1 和 p2 是因为无向图,如果是有向图就没必要了只需要 p1
  // 前插
  ArcNode *p1 = new ArcNode;
  p1->adjvex = j;
  p1->nextarc = G.vertices[i].firstarc;
  G.vertices[i].firstarc = p1;
  ArcNode \*p2 = new ArcNode;
  p2->adjvex = i;
  p2->nextarc = G.vertices[j].firstarc;
  G.vertices[j].firstarc = p2;
  }
  }

/\*\*

- 打印输出图
  */
  void Display(ALGraph &G) {
  for (int i = 0; i < G.vexnum;i++) {
  cout << "结点" << i << ":";
  // 复制选中的节点数组中的结点
  VNode p;
  p = G.vertices[i];
  if (p.firstarc != NULL){
  ArcNode *temp;
  temp = G.vertices[i].firstarc;
  while (temp != NULL) {
  cout << temp->adjvex<<" ";
  temp = temp->nextarc;
  }
  cout << "\n";
  }
  }
  }

//----邻接表的 BFS 遍历----

bool visited[MVNum];

int FirstAdjvex(ALGraph& G, int u)
{
int w = G.vertices[u].firstarc->adjvex;
return w;
}
int NextAdjVex(ALGraph& G, int u, int w)
{
ArcNode \*temp = G.vertices[u].firstarc;
while (temp->adjvex != w)
{
temp = temp->nextarc;
}
if (temp->nextarc)
return temp->nextarc->adjvex;
else
return -1;
delete temp;
}
void BFS_AL(ALGraph& G, int v){
cout << v;
visited[v] = true;
queue<int> Q;
Q.push(v);
int u = v;
while (!Q.empty()){
u = Q.front();
Q.pop();
for (int w = FirstAdjvex(G, u); w >= 0; w = NextAdjVex(G, u, w)){
if (!visited[w]){
cout <<w;
visited[w] = true;
Q.push(w);
}
}
}
}

void BFSTraverse(ALGraph &G) {
//访问标志数组初始化
for(int v = 0; v < G.vexnum; v++)  
 visited[v] = false;
//循环调用 BFS
for(int v = 0; v < G.vexnum; v++)  
 if(!visited[v])
BFS_AL(G, v); //对尚未访问的顶点调用 BFS
}

int main() {
ALGraph test;
CreateUDG(test);
Display(test);
BFSTraverse(test);
}

【插眼】为啥我写的一个函数不需要队列也可以???直接将顶点数组的一个元素后面接的链表遍历不就好了,然后再遍历标志数组元素值部位 true 的不就好了。。。为啥要压队列呀?

莫不是哪里有隐藏的 bug,插个眼!!!

【拔眼】这样是一种特殊情况,只适合图的各个结点是按照层次标号的,并且放入标志数组也是按照顺序放入的……


插眼代码如下:

void BFS_AL(ALGraph &G, int v)
{//按广度优先非递归遍历连通图 G
cout<<v;
visited[v] = true; //访问第 v 个顶点,并置访问标志数组相应分量值为 true
ArcNode \*p;
p = G.vertices[v].firstarc;
if (p != NULL) {
while(p != NULL) {
if (!visited[p->adjvex]){
cout << p->adjvex;
}
visited[p->adjvex] = true;
p = p->nextarc;
}
}
}

评论区

Twikoo giscus