用C++邻接表存储图数据 |21xrx.com

用C++邻接表存储图数据

2023-07-05 03:07:37 深夜i 13 0

C++ 邻接表图数据存储数据结构

在计算机科学中，图是一种非常重要的数据结构，能够帮助我们描述各种各样的问题场景，例如社交网络、交通路线等等。而在实际应用过程中，我们常常需要用程序来处理图数据，C++邻接表就是处理图数据的一种常见方式。

邻接表是一种基于链表的数据结构，表示了一个有向图或无向图中每个顶点的相邻点集合。在邻接表中，图的顶点被存储为一个数组，而每个顶点对应的边则被存储为一个链表。

尽管邻接矩阵也是存储图数据的一种方法，但是邻接矩阵会占用比较大的内存空间，当图的节点数比较大时，可能会出现内存不足的情况。而邻接表则避免了这个问题，因为邻接表中只存储了顶点之间的边关系。

下面是一个使用C++实现邻接表存储图数据的例子：

#include <iostream>
#include <vector>
using namespace std;
// Edge structure
struct Edge {
  int start, end, weight;
  Edge(int s, int e, int w) start = s; end = e; weight = w;
};
// Graph class
class Graph {
public:
  Graph(int n) {nodes.resize(n);}
  
  void addEdge(int s, int e, int w) {
    nodes[s].push_back(Edge(s, e, w));
  }
  
  void printGraph() {
    for (int i = 0; i < nodes.size(); i++) {
      cout << "Node " << i << ": ";
      for (int j = 0; j < nodes[i].size(); j++) {
        Edge e = nodes[i][j];
        cout << "(" << e.end << "," << e.weight << ") ";
      }
      cout << endl;
    }
  }
private:
  vector<vector<Edge>> nodes;
};
int main() {
  // Create a graph with 4 nodes
  Graph g(4);
  // Add edges to the graph
  g.addEdge(0, 1, 5);
  g.addEdge(1, 2, 3);
  g.addEdge(2, 3, 2);
  g.addEdge(0, 3, 1);
  // Print the graph
  g.printGraph();
  return 0;
}

上述代码中，Graph类使用了 STL vector 来存储每个顶点的边关系，addEdge()方法可以向图中添加新的边，printGraph()方法可以将整个图打印在控制台上。

邻接表是一种使图的存储和操作变得非常简便的数据结构。它可以用来解决很多实际问题，如地图路径规划，社交网络分析等。通过C++邻接表，我们可以轻松地对任意规模的图进行存储、遍历及其他操作。

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

下一篇: C++中如何获取字符数组的长度

评论区

相似文章