21xrx.com
2025-03-16 09:46:09 Sunday
文章检索 我的文章 写文章
C++实现图的邻接表
2023-07-09 08:56:43 深夜i     17     0
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++语言在实现图的邻接表时非常方便。对于要解决需要图数据结构的问题,邻接表是一种非常常用和高效的选择。

  
  

评论区

    相似文章