21xrx.com
2024-09-20 01:05:58 Friday
登录
文章检索 我的文章 写文章
C++实现图的基本操作代码
2023-07-04 18:50:41 深夜i     --     --
C++ 图 基本操作 代码

C++是一种面向对象的编程语言，它可以用来实现图的基本操作代码。图是一种非线性数据结构，它由若干个节点和连接这些节点的边组成，并且可以用来描述许多实际问题。在本文中，我们将介绍如何使用C++实现图的基本操作代码，包括创建图、添加节点、添加边、遍历图等。

1. 创建图：

首先，我们需要创建一个图，它可以通过以下代码实现：

class Graph {

  private:

    int numNodes; // 节点数量

    int** adjacencyMatrix; // 用邻接矩阵表示图的连接关系

  public:

    Graph(int numNodes) { // 构造函数

      this->numNodes = numNodes;

      adjacencyMatrix = new int*[numNodes];

      for (int i = 0; i < numNodes; i++) {

        adjacencyMatrix[i] = new int[numNodes];

        for (int j = 0; j < numNodes; j++) {

          adjacencyMatrix[i][j] = 0; // 初始化邻接矩阵

        }

      }

    }

};

以上代码创建了一个Graph类，该类有一个构造函数，用于初始化邻接矩阵。邻接矩阵用来存储节点之间的连接关系，其中0表示两个节点之间没有边，1表示有一条边连接。

2. 添加节点：

图由若干个节点组成，我们需要实现添加节点的功能。可以通过以下代码实现：

class Graph {

  // ...

  public:

    void addNode() { // 添加节点

      numNodes++;

      int** newMatrix = new int*[numNodes];

      for (int i = 0; i < numNodes; i++) {

        newMatrix[i] = new int[numNodes];

        for (int j = 0; j < numNodes; j++) {

          if (i < numNodes - 1 && j < numNodes - 1) {

            newMatrix[i][j] = adjacencyMatrix[i][j];

          } else {

            newMatrix[i][j] = 0;

          }

        }

      }

      adjacencyMatrix = newMatrix;

    }

};

以上代码添加了一个addNode方法，用于向图中添加节点。首先，生成一个新的邻接矩阵，设置新的节点和所有现有节点之间的连接关系为0，然后将新的邻接矩阵赋值给对象中的邻接矩阵。

3. 添加边：

图由节点和连接这些节点的边组成，我们需要实现添加边的功能。可以通过以下代码实现：

class Graph {

  // ...

  public:

    void addEdge(int source, int destination) { // 添加边

      adjacencyMatrix[source][destination] = 1;

      adjacencyMatrix[destination][source] = 1; // 无向图需要双向连接

    }

};

以上代码添加了一个addEdge方法，用于在图中添加边。将邻接矩阵中对应的两个节点之间的值设置为1即可。

4. 遍历图：

遍历图是常见的操作，我们需要实现遍历图的功能。可以通过以下代码实现：

class Graph {

  // ...

  public:

    void DFS(int start, bool* visited) { // 深度优先遍历

      visited[start] = true;

      cout << start << " ";

      for (int i = 0; i < numNodes; i++) {

        if (adjacencyMatrix[start][i] == 1 && visited[i] == false) {

          DFS(i, visited); // 递归遍历邻居节点

        }

      }

    }

    void BFS(int start) { // 广度优先遍历

      bool* visited = new bool[numNodes];

      for (int i = 0; i < numNodes; i++) {

        visited[i] = false;

      }

      queue q;

      visited[start] = true;

      q.push(start);

      while (!q.empty()) {

        int node = q.front();

        cout << node << " ";

        q.pop();

        for (int i = 0; i < numNodes; i++) {

          if (adjacencyMatrix[node][i] == 1 && visited[i] == false) {

            visited[i] = true;

            q.push(i);

          }

        }

      }

    }

};

以上代码添加了两个遍历图的方法，分别为深度优先遍历和广度优先遍历。深度优先遍历使用递归方式遍历每个节点的邻居节点；广度优先遍历借助队列实现按层级遍历。

综上所述，通过以上代码实现，我们可以实现图的基本操作，包括创建图、添加节点、添加边、遍历图等。这些操作可以用于解决许多实际问题。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复