C++实现图的邻接表 |21xrx.com

C++实现图的邻接表

2023-07-09 08:56:43 深夜i -- --

C++ Graph Adjacency List

在计算机科学中，图是一种常见的数据结构，它由节点（也称为顶点）和边组成。节点可以表示实际对象，如人、城市或物品，边表示它们之间的关系。图可以用于各种应用，如社交网络、路线规划、知识图谱等。

图可以用不同的方式来表示，其中一种常用的方法是邻接表。邻接表是一个数组，每个元素对应一个节点，每个元素包含一个链表，该链表包含所有与该节点相连的节点。这种表格形式非常适合表示稀疏图，其中只有一小部分节点相互连接。

下面我们将介绍如何使用C++实现图的邻接表。

首先，我们需要定义一个节点结构体，包含节点的数据和与该节点相连的节点指针链表。


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

然后，我们定义一个图类，包含图的大小和邻接表数组。构造函数初始化图的大小和邻接表数组为空。


class Graph{
  int vertices;
  std::vector<Node*> adjacencyList;
public:
  Graph(int v){
    vertices = v;
    adjacencyList.resize(v, NULL);
  }
  void addEdge(int src, int dest){
    Node* newNode = new Node;
    newNode->data = dest;
    newNode->next = adjacencyList[src];
    adjacencyList[src] = newNode;
  }
};

在这个类中，我们使用了一个向量（vector）来存储邻接表数组。addEdge函数用于添加边，它创建一个新节点并将其插入源节点的链表的开头。

现在，我们可以定义一个图并添加其边。


int main() {
  Graph g(5);
  g.addEdge(0, 1);
  g.addEdge(0, 4);
  g.addEdge(1, 2);
  g.addEdge(1, 3);
  g.addEdge(1, 4);
  g.addEdge(2, 3);
  g.addEdge(3, 4);
}

这样，我们就成功地使用C++实现了图的邻接表。在实践中，我们可以使用此表示法来实现各种常见的图算法，如深度优先搜索（DFS）和广度优先搜索（BFS）等。

总之，邻接表是一种非常实用的图表示法，可以有效地存储和访问图数据，C++语言在实现图的邻接表时非常方便。对于要解决需要图数据结构的问题，邻接表是一种非常常用和高效的选择。

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

下一篇: Python和C++有何联系？

评论区

()

相似文章