21xrx.com
2024-11-22 06:21:45 Friday
登录
文章检索 我的文章 写文章
用C++邻接表存储图数据
2023-07-05 03:07:37 深夜i     --     --
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++邻接表,我们可以轻松地对任意规模的图进行存储、遍历及其他操作。

  
  

评论区

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