数据结构与算法（十二）——图结构初探

拉维

发布于 2022-06-15 11:50:27

6200

发布于 2022-06-15 11:50:27

文章被收录于专栏：iOS小生活iOS小生活

一、图结构的基本介绍

如上图所示，就是一个图结构。

图（Graph），是由顶点的有限非空集合和顶点之间边的集合组成。图中有两个元素：顶点和边。

1，线性表、树结构和图结构的对比

需要注意的是，在线性表中，我们把数据元素称为元素；在树中，我们将数据元素称为节点；在图中，我们将数据元素称为顶点。

在线性表中，如果没有元素，我们称之为空表；如果一个树没有节点，我们称之为空树；但是，在图中，是不允许没有顶点的，没有空图的概念。

在线性表中，相邻的数据之间有一对一的线性关系；树结构中，相邻的两层节点之间有层次关系；在图结构中，任意的两个顶点都可能会存在关系，并不一定需要相邻才能产生关系。

2，各种图的定义

（1）无向图 & 无向边

如上图所示，顶点A与顶点C之间的边没有箭头指示方向，也就是说，可以由顶点A到顶点C，也可以由顶点C到顶点A，这样的边就是无向边。

由无向边连接而成的图称为无向图。

（2）有向图 & 有向边

如上图所示，顶点A与顶点C之间的连接的边是有方向的，只能由顶点C到顶点A，我们称这样的边为有向边。

由有向边连接而成的图称为有向图。

（3）无向完全图

无向完全图中，任意的两个顶点之间都会有一条直接连接的无向边。

（4）有向完全图

在有向完全图中，任意的两个顶点之间都有两条双向的有向边，使两个顶点能够互通。

（5）网

如果在一个图中，顶点与顶点之间的边对应的还有一个代表权值的数字，那么这样的图结构称为网。

二、图的存储——邻接矩阵

上面是一个图结构，诸位可以想一下，如何将这个图结构存储在计算机当中呢？

我们可以设计一个数据结构，第一个元素是顶点数组，该顶点数组是一个一维数组，存储顶点相关信息；第二个元素是边数组（或者称为弧数组，无向称为边，有向称为弧），边数组是一个二维数组，它是一个邻接矩阵。

1，无向图的存储

如上图所示，图中有V0、V1、V2、V3四个顶点，这四个顶点存在一维的顶点数组中；这四个顶点之间的相互连接关系存在4X4的二维邻接矩阵中。

可以看到，在二维邻接矩阵中，对角线上的值都为0，这是因为，主对角线上都是顶点自身去该顶点自身的路径，这是没有意义的，所以都设为0。

值为1代表二者之间有连接关系，比如[V1, V0]和[V1, V2]都为1，而[V1, V3]为0，这说明V1和V0、V2都有连接关系，而V1、V3之间是没有连接关系的。

由于我们这里是无向图，所以这里的邻接矩阵是以主对角线为轴对称的。

另外，还需要说明的一点是，在图结构中也有度的概念。树结构中的度指的是节点的子节点的个数；图结构中的度指的是，顶点连接的其他顶点数。在邻接矩阵中，顶点i的度指的是第i行非零元素的总和。如上图，V1的度是2，因为V1这一行有两个非零元素。

代码设计如下：

#include <stdio.h>


#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#include <stdbool.h>


// 图中可承载的最大顶点数
#define MaxVertexCount 100
//
// 顶点类型
typedef int VertexType;


// 图的类型
typedef struct Graph {
  VertexType vertexes[MaxVertexCount]; // 顶点数组
  int edges[MaxVertexCount][MaxVertexCount]; // 邻接矩阵，即边表
  int numberOfVertexes; // 图中当前的顶点数
  int numberOfEdges; // 图中当前的边数
} Graph;


// 无向图的顺序存储（邻接矩阵）
void createGraph(Graph *graph) {
  // 1，输入顶点数和边数
  printf("请依次输入顶点数和边数，以,隔开\n");
  scanf("%d,%d", &graph->numberOfVertexes, &graph->numberOfEdges);
  printf("有%d个顶点，有%d条边\n", graph->numberOfVertexes, graph->numberOfEdges);

  // 2，输入顶点信息
  printf("请输入%d个顶点信息\n", graph->numberOfVertexes);
  for (int i = 0; i < graph->numberOfVertexes; i++) {
    scanf("%d", &graph->vertexes[i]);
  }

  // 3，初始化邻接矩阵
  for (int i = 0; i < graph->numberOfVertexes; i++) {
    for (int j = 0; j < graph->numberOfVertexes; j++) {
      graph->edges[i][j] = 0;
    }
  }


  // 4，输入边表信息
  printf("请依次输入对应的边表信息，比如第3行第4列上的值是5，则输入3,4,5\n");
  int row, column, weight;
  for (int i = 0; i < graph->numberOfEdges; i++) {
    scanf("%d,%d,%d", &row, &column, &weight);
    graph->edges[row][column] = weight;
    graph->edges[column][row] = graph->edges[row][column]; // 无向边的邻接矩阵是对称的
  }

  // 5，打印生成的图
  printf("最终生成的图的邻接矩阵为：\n");
  for (int i = 0; i < graph->numberOfVertexes; i++) {
    printf("\n");
    for (int j = 0; j < graph->numberOfVertexes; j++) {
      printf("%d ", graph->edges[i][j]);
    }
  }
  printf("\n");
}

int main(int argc, const char * argv[]) {
  // insert code here...
  printf("Hello, World!\n");
  Graph graph;
  createGraph(&graph);
  return 0;
}

最终的打印结果如下：

代码一共五步：

①输入图中的顶点数和边数
②输入顶点表
③初始化邻接矩阵（即边表）
④输入边表
⑤打印图

2，有向图的存储

如上图所示，是一个有向图。

有向图的邻接矩阵不一定是对称的哦~比如，由V1可以到达V0，但是由V0却到达不了V1，因此，[V1, V0]=1，[V0, V1]=0。

3，网的存储

我们知道，边上带有权值的图就是网。

在前面的示例中，我们知道，在一个图的邻接矩阵中，如果两顶点之间没有连接关系，那么可以将其设为0，否则设为1。但是在网的邻接矩阵中，情况有所不同，对角线上仍然是0，这一点是与之前一样的；但是当两顶点之间存在连接关系的时候，需要设置为对应的权值，而不仅仅是只设置为1；在两顶点之间不存在连接关系的时候，不是设置为0，而是设置为无穷大。

三、图的存储——邻接表

我们知道，任何一种逻辑结构最后都是要通过顺序存储或者链式存储的方式来实现的。上面我们讨论的通过邻接矩阵的方式来存储图，实际上就是通过顺序存储的方式来存储图结构的。而通过顺序存储的方式，实际上是有空间的浪费问题存在的。

如上图所示，该图中共有5个顶点，这些顶点中只有一个V1到V0的有向边，因此在5*5的邻接矩阵中，实际上是只存储了一个有效值[V1, V0]，这样就浪费了24个存储空间。可以看到这是极大的空间浪费。实际上，我们可以采用链式存储的方式来避免这种空间的浪费。

1，无向图的存储

如上图所示，是一个无向图，该无向图中有V0、V1、V2、V3四个顶点。接下来我们使用邻接表的形式来进行存储。

邻接表本质上就是一个一维数组，该一维数组中的元素（上图蓝色部分）就是图的顶点信息。图有多少个顶点，邻接表就有多少个元素。

邻接表的每一个顶点元素都包含两个要素：元素值（即顶点的值）、第一条边的地址。

顶点与顶点之间的边的信息是通过一个单链表（上图红色区域）来记载的，邻接表元素中的指针域指向的就是单链表的首元结点。

该单链表中的各个节点元素就是对应的邻接表节点元素的各个边，由于顶点的边是无序的，因此单链表中的节点顺序也是随意的，只要能够将所有的边串起来即可。比如上图中的V0顶点有3条边，在上图中是按123的顺序，其实也可以按132、213、321等顺序，只要能将三条边串起来即可。

还有一点需要注意，顶点的边信息是存储在单链表中的，单链表中的最后一个节点的指针域要置为空。

单链表的节点，我们称之为边表节点，边表节点中的数据域存储的是边的另一端的节点的值，边表节点的指针域指向的是对应顶点的其他的边。

注意哦，边表上的各个节点之间虽然是通过指针域连接起来了，但是一条边表上的各个节点之间是没有关系的，一条边表上的各个节点都是跟对应的顶点关联的。

如果要查看某一个顶点的度，那么就将该顶点指向的边表进行遍历，计算边表的节点数即可。

2，有向图的存储

有向图中的边是有方向的。在上图中，顶点V0和V1、V2看似是有连接的，但是实际上顶点V0对应的边只有[V0, V3]这一条。

有向图的存储结构跟无向图是一样的。

还有一点需要注意的是，如果某一个顶点没有边，那么在邻接表中，该顶点对应的元素的指针域需要置空。

3，网的存储

带权重的图称为网。

网的顶点表与图的顶点表的逻辑一样，是不需要改动的。

网的边表的节点结构需要在图的边表的节点结构基础上再增加一个值域用于存储边的权重值。

4，代码设计

#include <stdio.h>
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#include <stdbool.h>


// 最大顶点数
#define Max_Vertex_Count 100


// 顶点值的类型
typedef int VertexValueType;


// 边表节点类型
typedef struct EdgeTableNode {
  int weight; // 权重值
  int vertexIndex; // 顶点在顶点表中的底标
  struct EdgeTableNode *next; // 边表（单向链表）的指针域，指向下一个边表节点
} EdgeTableNode;


// 顶点类型
typedef struct VertexType {
  VertexValueType vertexValue; // 顶点值
  struct EdgeTableNode *firstEdge; // 指向边表的首元结点
} VertexType;


// 图的结构
typedef struct Graph {
  struct VertexType vertexes[Max_Vertex_Count]; // 顶点表
  int countOfVertexes; // 顶点数
  int countOfEdges; // 边数
  bool isDirected; // 是否为有向图
} Graph;


// 创建一个图
void createGraph(Graph *graph) {
  // 1，输入顶点数、边数和是否有向
  printf("请输入顶点数：\n");
  scanf("%d", &graph->countOfVertexes);
  printf("请输入边数：\n");
  scanf("%d", &graph->countOfEdges);
  printf("请输入是否为有向图：\n");
  int isDirectedInt;
  scanf("%d", &isDirectedInt);
  graph->isDirected = isDirectedInt == 0 ? false : true;

  // 2，输入顶点值信息
  printf("请依次输入%d个顶点值：\n", graph->countOfVertexes);
  for (int i = 0; i < graph->countOfVertexes; i++) {
    scanf("%d", &graph->vertexes[i].vertexValue);
    graph->vertexes[i].firstEdge = NULL; // 默认是没有边的
  }

  // 3，输入边信息
  printf("请依次输入边信息，格式如下\n起点底标,终点底标,权重值\n");
  int startIndex, endIndex;
  for (int i = 0; i < graph->countOfEdges; i++) {
    // 新建一个边表节点
    struct EdgeTableNode *node = malloc(sizeof(EdgeTableNode));
    // 输入边表信息
    scanf("%d, %d, %d", &startIndex, &endIndex, &node->weight);
    node->vertexIndex = endIndex;
    // 将当前边信息插入到对应的边表中（前插法）
    node->next = graph->vertexes[startIndex].firstEdge;
    graph->vertexes[startIndex].firstEdge = node;

    // 如果是无向图
    if (!graph->isDirected) {
      // 新建一个边表节点
      struct EdgeTableNode *node = malloc(sizeof(EdgeTableNode));
      node->vertexIndex = startIndex;
      // 将当前边信息插入到对应的边表中（前插法）
      node->next = graph->vertexes[endIndex].firstEdge;
      graph->vertexes[endIndex].firstEdge = node;
    }
  }

  // 4，打印图
  int i;
  printf("邻接表中存储信息:\n");
  //遍历一遍顶点坐标，每个再进去走一次
  for (i = 0; i < graph->countOfVertexes; i++) {
      EdgeTableNode * p = graph->vertexes[i].firstEdge;
      while (p) {
          printf("%d->%d ", graph->vertexes[i].vertexValue, graph->vertexes[p->vertexIndex].vertexValue);
          p = p->next;
      }
      printf("\n");
  }
}


int main(int argc, const char * argv[]) {
  // insert code here...
  printf("Hello, World!\n");

  Graph graph;
  createGraph(&graph);

  return 0;
}

执行结果如下：

四、图的遍历——深度优先搜索（DFS，Depth First Search）

如上图所示，图的遍历指的就是，从图的某一个顶点开始将图中所有的顶点完全处理一个遍，但是需要保证不重复处理其中的顶点，也就是说，图中的顶点能且只能被处理一次。

但是，由于图是没有层序的，那么我们该如何识别图中的顶点到底有没有被处理过呢？我们可以给每一个顶点都做一个标记来标识该顶点是否有被处理过。我们可以创建一个visitedVertexes数组，数组的大小就是顶点数，从而一对一标识顶点是否有被处理过。

深度遍历，又称为深度优先搜索（Depth First Search，DFS）。

如上图所示，我将左侧的图“化简为繁”，化成右侧的样子。

首先，从顶点A出发，此时有俩选择B和F，按照右手原则，来到B；

顶点B有三个选择，按照右手原则，来到C；

顶点C有俩选择，按照右手原则，来到D；

顶点D有4个选择，按照右手原则，来到E；

顶点E有俩选择，按照右手原则，来到F；

顶点F有俩选择，按照右手原则应该去A，但是A已经处理过了，所以来到G；

顶点G有3个选择，按照右手原则应该先B再D再H，但是B和D都已经处理过了，所以来到H；

顶点H有俩选择，但是D和E都已经处理过了，所以此时结束遍历。

此时我们复盘一下，以上遍历完全了吗？其实没有，我将顶点I给落下了。那么如何来保证所有的顶点都能够被遍历到呢？

如上图所示，在某一个顶点无路可走的时候，他需要返回到它上一个顶点，一直返回到可以找到未处理的顶点为止，如果返回到最一开始处理的那个顶点还是没有找到待处理的顶点，那么就说明所有的连接顶点都已经处理完毕，此时遍历结束。

1，邻接矩阵的DFS

思路如下：

①创建一个邻接矩阵
②创建一个标识顶点是否被处理过的数组visitedVertexes，并将所有元素初始化为false
③开启图的遍历，一定要注意处理非连接图的情况
④进入某一个顶点的递归遍历，处理该节点，并且将该节点标记为已处理
⑤循环遍历第④步中顶点的边表节点，找到没有被遍历到的顶点，继续递归depthFirstSearch

代码如下：

//
//  main.c
//  邻接矩阵的深度优先遍历
//
//  Created by 拉维 on 2022/4/19.
//


#include <stdio.h>
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#include <stdbool.h>


// 最大顶点数量
#define Max_Vertex_Count 20


// 顶点值类型
typedef char vertexValueType;


// 图结构
typedef struct Graph {
  vertexValueType vertexes[Max_Vertex_Count]; // 顶点表
  int edges[Max_Vertex_Count][Max_Vertex_Count]; // 边表
  int countOfVertexes, countOfEdges; // 顶点数和边数
} Graph;


// 1，创建一个图
void createGraph(Graph *graph) {
  // （1）初始化节点数和边数
  graph->countOfVertexes = 9;
  graph->countOfEdges = 15;

  // （2）初始化顶点表
  graph->vertexes[0] = 'A';
  graph->vertexes[1] = 'B';
  graph->vertexes[2] = 'C';
  graph->vertexes[3] = 'D';
  graph->vertexes[4] = 'E';
  graph->vertexes[5] = 'F';
  graph->vertexes[6] = 'G';
  graph->vertexes[7] = 'H';
  graph->vertexes[8] = 'I';

  // （3）初始化边表
  for (int i = 0; i < graph->countOfVertexes; i++) {
    for (int j = 0; j < graph->countOfVertexes; j++) {
      graph->edges[i][j] = 0;
    }
  }

  // （4）输入边表信息
  graph->edges[0][1]=1;
  graph->edges[0][5]=1;

  graph->edges[1][2]=1;
  graph->edges[1][8]=1;
  graph->edges[1][6]=1;

  graph->edges[2][3]=1;
  graph->edges[2][8]=1;

  graph->edges[3][4]=1;
  graph->edges[3][7]=1;
  graph->edges[3][6]=1;
  graph->edges[3][8]=1;

  graph->edges[4][5]=1;
  graph->edges[4][7]=1;

  graph->edges[5][6]=1;

  graph->edges[6][7]=1;

  // （5）如果是无向图
  for (int i = 0; i < graph->countOfVertexes; i++) {
    for (int j = i; j < graph->countOfVertexes; j++) {
      graph->edges[j][i] = graph->edges[i][j];
    }
  }
}


// 2，深度遍历
bool visitedVertexes[Max_Vertex_Count];


void depthFirstSearch(Graph graph, int vertexIndex) {
  // 处理当前顶点
  printf("%c", graph.vertexes[vertexIndex]);

  // 将当前顶点标记为已展示
  visitedVertexes[vertexIndex] = true;

  // 遍历查找该顶点连接的所有的边
  for (int i = 0; i < graph.countOfVertexes; i++) {
    if (graph.edges[vertexIndex][i] == 1 && !visitedVertexes[i]) {
      // 递归处理该顶点的边
      depthFirstSearch(graph, i);
    }
  }
}


void dfsTraverse(Graph graph) {
  // 初始化visitedVertexes数组
  for (int i = 0; i < graph.countOfVertexes; i++) {
    visitedVertexes[i] = false;
  }

  // 循环遍历图的顶点
  /*
   ⚠️⚠️⚠️这个循环能够保证非连通图中的各个顶点都能够被遍历到⚠️⚠️⚠️
   */
  for (int i = 0; i < graph.countOfVertexes; i++) {
    if (!visitedVertexes[i]) {
      depthFirstSearch(graph, i);
    }
  }
}


int main(int argc, const char * argv[]) {
  // insert code here...
  printf("Hello, World!\n");

  Graph graph;
  createGraph(&graph);
  dfsTraverse(graph);
  printf("\n");

  return 0;
}

看到这里，有些同学可能会有这样一个疑问，既然有一个数组来专门承载图的顶点，那么直接遍历该顶点数组不就可以了吗？为啥还要又是深度又是广度的这么麻烦？这句话看起来貌似没什么问题，但实际上是不对的。图里面包含两个要素，一个是顶点表，一个是边表。图的遍历实际上就是将所有的顶点和边都走一遍，而不单单是遍历顶点。

2，邻接表的DFS

上面讲了邻接矩阵的DFS，接下来我们聊聊邻接表的DFS。

首先来看一下图是如何通过邻接表来进行链式存储的，如下图所示：

可以看到，绿色区域是顶点表，红色区域是边表，具体的细节我前面已经讲过了，这里不赘述，现在我们来看一下，在邻接表中深度搜索的顺序是怎么样的。

如上图所示，首先从A顶点开始，处理完A顶点之后，找到顶点A的边表中的第一个顶点F；

顶点F处理完之后，找到G；

顶点G处理完之后，找到H；

顶点H处理完之后，找到E（G已经处理过了）；

顶点E处理完之后，找到D（H和F已经处理过了）;

顶点D处理完之后，找到I；

顶点I处理完之后，找到C（D已经处理过了）；

顶点C处理完之后，找到B（I和D已经处理过了）；

顶点B处理完之后，B的所有边都处理完了；

然后按照递归栈的顺序一级一级往上继续遍历查找，直至重新回到顶点A结束。

代码思路如下：

①创建一个图
②新建一个visitedVertexes数组来记录各个节点是否被处理过，初始化该数组的所有元素为false
③遍历递归顶点表的所有顶点，该遍历的主要目的就是为了兼容不连续图的情况
④处理顶点信息，并将该顶点标记为已处理
⑤循环遍历当前顶点的所有边表信息，找到没有处理的顶点，进入下一层递归

代码如下：

//
//  main.c
//  邻接表的深度遍历
//
//  Created by 拉维 on 2022/4/19.


#include <stdio.h>
#include <stdio.h>
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#include <stdbool.h>


// 最大顶点数量
#define Max_Vertex_Count 20


// 边表节点类型
typedef struct EdgeTableNode {
  int vertexIndex; // 顶点在顶点表中的下标
  int weight; // 边的权重
  struct EdgeTableNode *next; // 连接下一个边表节点
} EdgeTableNode;


// 顶点值的类型
typedef int VertexValue;


// 顶点类型
typedef struct VertexTableNode {
  VertexValue data; // 值域
  struct EdgeTableNode *firstEdgeNode; // 指针域，指向该顶点的第一条边
} VertexTableNode;


// 图结构
typedef struct Graph {
  VertexTableNode vertextTableNodes[Max_Vertex_Count]; // 顶点表
  int countOfVertexes; // 顶点数量
  int countOfEdges; // 边数量
  bool isDirected; // 是否为有向图
} Graph;


// 1，创建一个图
void createGraph(Graph *graph) {
  // （1）初始化顶点数、边数和是否为有向图
  printf("请输入顶点数：\n");
  scanf("%d", &graph->countOfVertexes);
  printf("请输入边数：\n");
  scanf("%d", &graph->countOfEdges);
  printf("是否为有向图：\n");
  int isDirectedInt;
  scanf("%d", &isDirectedInt);
  graph->isDirected = isDirectedInt != 0;

  // （2）初始化顶点表
  printf("请依次输入%d个顶点值:\n", graph->countOfVertexes);
  for (int i = 0; i < graph->countOfVertexes; i++) {
    scanf("%d", &graph->vertextTableNodes[i].data);
    graph->vertextTableNodes[i].firstEdgeNode = NULL;
  }

  // （3）初始化边表
  printf("请依次输入边表信息，格式如下:\n起始顶点下标,结束顶点下标,权重值\n");
  int startIndex, endIndex;
  for (int i = 0; i < graph->countOfEdges; i++) {
    // 新建一个边表节点
    struct EdgeTableNode *edgeNode = malloc(sizeof(EdgeTableNode));
    scanf("%d,%d,%d", &startIndex, &endIndex, &edgeNode->weight);
    edgeNode->vertexIndex = endIndex;

    //将边表节点前插到对应顶点的单向链表中
    edgeNode->next = graph->vertextTableNodes[startIndex].firstEdgeNode;
    graph->vertextTableNodes[startIndex].firstEdgeNode = edgeNode;

    // 如果是无向图
    if (!graph->isDirected) {
      // 新建一个边表节点
      struct EdgeTableNode *edgeNode = malloc(sizeof(EdgeTableNode));
      edgeNode->vertexIndex = startIndex;

      //将边表节点前插到对应顶点的单向链表中
      edgeNode->next = graph->vertextTableNodes[endIndex].firstEdgeNode;
      graph->vertextTableNodes[endIndex].firstEdgeNode = edgeNode;
    }
  }
}


// 2，深度遍历邻接表


bool visitedVertexes[Max_Vertex_Count]; // 标记各个顶点是否有被处理过


void depthFirstSearch(Graph graph, int vertexIndex) {
  // （1）打印当前顶点，并将当前顶点标记为已处理
  visitedVertexes[vertexIndex] = true;
  printf("%d", graph.vertextTableNodes[vertexIndex].data);

  // （2）寻找未处理过的边信息
  struct EdgeTableNode *tempEdgeNode = graph.vertextTableNodes[vertexIndex].firstEdgeNode;
  while (tempEdgeNode) {
    if (!visitedVertexes[tempEdgeNode->vertexIndex]) {
      depthFirstSearch(graph, tempEdgeNode->vertexIndex);
    }
    tempEdgeNode = tempEdgeNode->next;
  }
}


void dfsReverse(Graph graph) {
  // 将visitedVertexes数组元素都初始化为false
  for (int i = 0; i < graph.countOfVertexes; i++) {
    visitedVertexes[i] = false;
  }

  // 依次遍历各个顶点
  /*
   该循环遍历的作用就是兼容非连接图
   */
  for (int i = 0; i < graph.countOfVertexes; i++) {
    if (!visitedVertexes[i]) {
      depthFirstSearch(graph, i);
    }
  }
}


int main(int argc, const char * argv[]) {
  // insert code here...
  printf("Hello, World!\n");

  Graph graph;
  createGraph(&graph);
  dfsReverse(graph);

  return 0;
}

五、图的遍历——广度优先搜索

广度优先遍历的特点：

①将根节点放到队列的末尾（入队）
②每次从队列的头部取出一个元素（出队），查看该元素所以的下一级元素，并把这些下一级元素放到队尾（入队）
③当找到所要找的元素的时候结束程序
④如果遍历整个树都还没有找到，那么就结束程序

①顶点A作为第一个节点入队，此时队列为A
②A出队，A的两个子节点B、F依次入队，此时队列为BF
③B出队，B的三个子节点C、I、G依次入队，此时队列为FCIG
④F出队，F的子节点E入队，此时队列为CIGE
⑤C出队，C的子节点D入队，此时队列为IGED
⑥I出队，I的各个连接节点均已经处理过，因此无节点入队，此时队列为GED
⑦G出队，G的子节点H入队，此时队列为EDH
⑧E出队，E的各个连接节点均已处理过，因此无节点入队，此时队列为DH
⑨D出队，D的各个连接节点均已处理过，因此无节点入队，此时队列为H
⑩H出队，H的各个连接节点均已处理过，因此无节点入队，此时队列为空

1，邻接矩阵的广度优先搜索

代码如下：

//
//  main.c
//  邻接矩阵的广度优先搜索
//
//  Created by 拉维 on 2022/4/20.
//


#include <stdio.h>
#include <stdbool.h>


// 一、队列结构


// 队列最大长度
#define Max_Queue_Size 8


// 队列中元素值的类型
typedef int ElementType;


// 队列结构
typedef struct Queue {
  int front; // 队头
  int rear; // 队尾
  ElementType datas[Max_Queue_Size]; // 数据
} Queue;


// 1，队列初始化
void initQueue(Queue *queue) {
  queue->front = queue->rear = 0;
}


// 2，入队
void enQueue(Queue *queue, ElementType element) {
  // 如果满队，则退出
  if ((queue->rear - queue->front + Max_Queue_Size) % Max_Queue_Size == Max_Queue_Size - 1) {
    return;
  }

  // 如果没有满队，则入队
  queue->datas[queue->rear] = element;
  queue->rear = (queue->rear + 1) % Max_Queue_Size;
}


// 3，出队
void deQueue(Queue *queue, int *front) {
  // 如果队空，则退出
  if (queue->rear == queue->front) {
    return;
  }

  // 如果队非空，则出队
  queue->front = (queue->front + 1) % Max_Queue_Size;

  // 将队头指针传递出去
  *front = queue->front;
}


// 4，判空
bool isQueueEmpty(Queue queue) {
  return queue.rear == queue.front;
}


// 二、邻接矩阵的创建


// 最大顶点数
#define Max_Vertexes_Count 20


// 图的顶点值类型
typedef int VertexValueType;


// 图结构
typedef struct Graph {
  VertexValueType vertexes[Max_Vertexes_Count]; // 顶点表
  int edges[Max_Vertexes_Count][Max_Vertexes_Count]; // 边表
  int countOfVertexes; // 顶点数
  int countOfEdges; // 边数
} Graph;


// 创建图
void createGraph(Graph *graph) {
  // 1，初始化顶点数和边数
  printf("请输入顶点数：\n");
  scanf("%d", &graph->countOfVertexes);

  printf("请输入边数：\n");
  scanf("%d", &graph->countOfEdges);

  // 2，初始化顶点
  printf("请依次输入%d个顶点值：\n", graph->countOfVertexes);
  for (int i = 0; i < graph->countOfVertexes; i++) {
    scanf("%d", &graph->vertexes[i]);
  }

  // 3，初始化边表信息
  for (int i = 0; i < graph->countOfVertexes; i++) {
    for (int j = 0; j < graph->countOfVertexes; j++) {
      graph->edges[i][j] = 0;
    }
  }

  // 4，输入边表信息
  printf("请依次输入%d条边表信息，格式如下:\n起点下标,终点下标\n", graph->countOfEdges);
  int startIndex, endIndex;
  for (int i = 0; i < graph->countOfEdges; i++) {
    scanf("%d,%d", &startIndex, &endIndex);
    graph->edges[startIndex][endIndex] = 1;
  }
}


// 三、邻接矩阵的广度优先遍历


// 1，创建一个全局数组用于记录各个顶点是否被处理过
bool visitedVertexes[Max_Vertexes_Count];


void widthFirstSearch(Graph graph) {
  // 2， 创建队列并初始化
  Queue queue;
  initQueue(&queue);

  // 3，初始化visitedVertexes数组所有元素为false
  for (int i = 0; i < graph.countOfVertexes; i++) {
    visitedVertexes[i] = false;
  }

  // 4，循环遍历各个顶点，依次入队
  /*
   该循环遍历的主要目的就是兼容非连接图的情况
   */
  for (int i = 0; i < graph.countOfVertexes; i++) {
    // 4.1 如果已经处理过该顶点，则略过
    if (visitedVertexes[i]) {
      continue;
    }

    // 4.2 处理当前顶点信息，并将该顶点标记为已处理
    visitedVertexes[i] = true;
    printf("%d ", graph.vertexes[i]);

    // 4.3 入队
    enQueue(&queue, visitedVertexes[i]);

    // 4.4 循环遍历查找各个节点的子节点，并将没有处理过的节点入队，已经处理过的出队
    int currentIndex = i;
    while (!isQueueEmpty(queue)) { // 只要队列非空，就会一直遍历下去
      // 4.4.1 将当前顶点的所有未处理的子节点入队
      for (int j = 0; j < graph.countOfVertexes; j++) {
        if (graph.edges[currentIndex][j] == 1 && !visitedVertexes[j]) {
          // 处理当前顶点信息，并将该顶点标记为已处理
          visitedVertexes[j] = true;
          printf("%d ", graph.vertexes[j]);
          // 入队
          enQueue(&queue, visitedVertexes[j]);
        }
      }

      // 4.4.2 遍历查询边表信息之后需要将当前顶点出队
      /*
       ⚠️⚠️⚠️出队的时候会将队首底标赋值给变量currentIndex，这样才能在while循环中一路遍历下去
       */
      deQueue(&queue, &currentIndex);
    }
  }
}
/*

 */


int main(int argc, const char * argv[]) {
  // insert code here...
  printf("Hello, World!\n");

  Graph graph;
  createGraph(&graph);
  widthFirstSearch(graph);

  return 0;
}

2，邻接表的广度优先搜索

代码如下：

//
//  main.c
//  邻接表的WFS
//
//  Created by 拉维 on 2022/4/21.
//


#include <stdio.h>
#include <stdbool.h>
#include "stdlib.h"


// 一、队列结构


// 队列的最大容量
#define Max_Queue_size 20


// 队列中元素值的类型
typedef int QueueElement;


// 队列结构
typedef struct Queue {
  int front; // 队首
  int rear; // 队尾
  QueueElement datas[Max_Queue_size];
} Queue;


// 初始化队列
void initQueue(Queue *queue) {
  queue->front = queue->rear = 0;
}


// 入队
void enQueue(Queue *queue, QueueElement element) {
  // 判断是否队满
  if ((queue->rear - queue->front + Max_Queue_size) % Max_Queue_size == Max_Queue_size - 1) {
    return;
  }

  // 如果队未满则入队
  queue->datas[queue->rear] = element;
  queue->rear = (queue->rear + 1) % Max_Queue_size;
}


// 出队
void deQueue(Queue *queue, int *front) {
  // 判断是否队空
  if (queue->rear == queue->front) {
    return;
  }

  // 如果队未空，则出队
  queue->front = (queue->front + 1) % Max_Queue_size;
  *front = queue->front; // 将队首底标传递出去
}


// 队的判空
bool isQueueEmpty(Queue queue) {
  return queue.front == queue.rear;
}


// 二、图结构（邻接表）


// 图中可承载的最大顶点数量
#define Max_Vertexes_Count 20


// 顶点值类型
typedef int VertexValueType;


// 边表节点类型
typedef struct EdgeTableNode {
  int vertexIndex; // 顶点底标
  int weight; // 权重值
  struct EdgeTableNode *next; // 指针域
} EdgeTableNode;


// 顶点结构
typedef struct Vertex {
  VertexValueType value; // 顶点值
  struct EdgeTableNode *first; // 指向边表的首元结点
} Vertex;


// 图结构
typedef struct Graph {
  Vertex vertexes[Max_Vertexes_Count]; // 顶点表
  int countOfVertexes; // 顶点数量
  int countOfEdges; // 边的数量
} Graph;


// 创建图
void createGraph(Graph *graph) {
  // 1，初始化图的顶点数和边数
  printf("请输入顶点数：\n");
  scanf("%d", &graph->countOfVertexes);
  printf("请输入边数：\n");
  scanf("%d", &graph->countOfEdges);

  // 2，初始化顶点表信息
  printf("请依次输入%d个顶点数据：\n", graph->countOfVertexes);
  for (int i = 0; i < graph->countOfVertexes; i++) {
    scanf("%d", &graph->vertexes[i].value);
    graph->vertexes[i].first = NULL; // 默认都是没有对应边表信息的
  }

  // 3，输入边表信息
  printf("请依次输入%d条边表信息，格式如下：\n起始顶点底标,结束顶点底标,权重值\n", graph->countOfEdges);
  int startIndex, endIndex;
  for (int i = 0; i < graph->countOfEdges; i++) {
    // 新建一个边表节点
    struct EdgeTableNode *edgeNode = malloc(sizeof(EdgeTableNode));
    scanf("%d,%d,%d", &startIndex, &endIndex, &edgeNode->weight);
    edgeNode->vertexIndex = endIndex;

    // 将边表节点前插到边表的首元结点位置
    edgeNode->next = graph->vertexes[startIndex].first;
    graph->vertexes[startIndex].first = edgeNode;
  }
}


// 三、邻接表的广度优先搜索


// 1，声明一个数组，记录各个节点是否有被处理过
bool visitedVertexes[Max_Vertexes_Count];


void widthFirstSearch(Graph graph) {
  // 2，生成一个队列
  Queue queue;
  initQueue(&queue);

  // 3，初始化visitedVertexes数组
  for (int i = 0; i < graph.countOfVertexes; i++) {
    visitedVertexes[i] = false;
  }

  // 4，循环遍历各个顶点
  /*
   该循环的主要目的是兼容非连接图。
   实际上如果是连通图的话，该循环只会执行一次。
   */
  for (int i = 0; i < graph.countOfVertexes; i++) {
    // 4.1 如果已经处理过了，则略过
    if (visitedVertexes[i]) {
      continue;
    }

    // 4.2 处理当前顶点信息，并标记为已处理
    printf("%d ", graph.vertexes[i].value);
    visitedVertexes[i] = true;

    // 4.3 将当前顶点入队
    enQueue(&queue, i);

    // 4，4 循环遍历队列中的各个顶点元素，并依次将下一级顶点入队，当前顶点出队
    struct EdgeTableNode *edgeNode;
    int frontIndex = i; // 队列头部
    while (!isQueueEmpty(queue)) {
      // 将当前顶点的连接顶点入队
      edgeNode = graph.vertexes[frontIndex].first;
      while (edgeNode) {
        // 处理当前未处理的顶点信息，并标记为已处理，同时入队
        if (!visitedVertexes[edgeNode->vertexIndex]) {
          printf("%d ", graph.vertexes[edgeNode->vertexIndex].value);
          visitedVertexes[edgeNode->vertexIndex] = true;
          enQueue(&queue, edgeNode->vertexIndex);
        }
        edgeNode = edgeNode->next;
      }

      // 将当前顶点出队
      deQueue(&queue, &frontIndex);
    }
  }
}


int main(int argc, const char * argv[]) {
  // insert code here...
  printf("Hello, World!\n");

  Graph graph;
  createGraph(&graph);
  widthFirstSearch(graph);

  return 0;
}

以上。

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2022-04-22，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

存储

本文分享自 iOS小生活微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

存储

登录后参与评论

0 条评论

热度

数据结构与算法（十二）——图结构初探

数据结构与算法（十二）——图结构初探

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐