【教程】如何使用C++创建图并进行遍历 |21xrx.com

【教程】如何使用C++创建图并进行遍历

2023-06-24 00:53:28 深夜i -- --

C++ 图遍历创建教程

作为一种广泛应用于计算机科学领域的编程语言，C++可用于创建各种各样的数据结构，包括图。图是一种由节点和边组成的抽象结构，常用于描述网络、社交关系等场景。本教程将介绍如何使用C++创建图并进行遍历。

一、创建图

在C++中创建图通常需要使用邻接表或者邻接矩阵两种数据结构，其中邻接表比较常见。下面我们就来演示一下如何使用邻接表创建图。

首先需要定义一个表示节点的结构体，包含节点名称和指向下一个节点的指针。代码如下：


struct Node {
  int name;
  Node* next;
};

接下来，在主函数中首先声明一个大小为5的邻接表，用于表示5个节点之间的关系。


const int MAX_NODE = 5;
Node* graph[MAX_NODE];

为了方便起见，我们可以写一个函数来向邻接表中添加节点。该函数的输入参数为两个节点的名称和它们之间的边的权重。代码如下：


void addEdge(int from, int to, int weight) {
  Node* newNode = new Node;
  newNode->name = to;
  newNode->next = graph[from];
  graph[from] = newNode;
}

使用上述函数来创建图的过程如下所示：


for (int i = 0; i < MAX_NODE; i++) {
  graph[i] = nullptr;
}
addEdge(0, 1, 5);
addEdge(0, 4, 3);
addEdge(1, 2, 6);
addEdge(1, 3, 9);
addEdge(2, 3, 7);
addEdge(3, 4, 1);

该代码片段表示了一个由5个节点组成的图，其中每个节点之间都有一条边，每条边均有一个权重值。

二、图的遍历

有了图的邻接表之后，就可以用各种算法对其进行遍历了。常见的遍历算法有深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索是一种先访问子节点再访问兄弟节点的遍历方式。使用递归算法实现深度优先搜索特别方便。下面是一个深度优先搜索的示例代码：


bool visited[MAX_NODE];
void DFS(int node) {
  visited[node] = true;
  cout << node << " ";
  for (Node* p = graph[node]; p != nullptr; p = p->next) {
    int nextNode = p->name;
    if (!visited[nextNode]) {
      DFS(nextNode);
    }
  }
}

该函数的输入参数为起始遍历节点的编号，该函数会将从该节点开始可以到达的所有节点遍历一遍，遍历时会通过 visited 数组记录该节点是否已经被访问过。

广度优先搜索则是先访问同一层节点再访问下一层节点，使用循环实现广度优先搜索相对简单。具体代码实现如下：


void BFS(int node) {
  queue<int> q;
  q.push(node);
  visited[node] = true;
  while (!q.empty()) {
    int curNode = q.front();
    q.pop();
    cout << curNode << " ";
    for (Node* p = graph[curNode]; p != nullptr; p = p->next) {
      int nextNode = p->name;
      if (!visited[nextNode]) {
        q.push(nextNode);
        visited[nextNode] = true;
      }
    }
  }
}

该函数的输入参数同样是起始遍历节点的编号，该函数会将从该节点开始可以到达的所有节点遍历一遍，遍历时同样会通过 visited 数组记录该节点是否已经被访问过，并使用队列来记录下一层所有待遍历的节点。

总结

本文介绍了如何使用C++创建图，并实现了两种常见的遍历算法：深度优先搜索和广度优先搜索。希望本文对于大家了解如何使用C++创建图以及常见的遍历算法等方面有所启发。

上一篇: idea打包java可执行jar包

下一篇: C++在嵌入式开发中的应用

评论区

()

相似文章