21xrx.com
2025-03-22 01:27:54 Saturday
文章检索 我的文章 写文章
C++实现邻接表有向图
2023-07-10 00:40:07 深夜i     15     0
C++ 实现 邻接表 有向图

邻接表是一种十分常见的数据结构，用于表示图的连通关系。在有向图中，每个节点可以指向其他节点，而邻接表就是用来存储这种指向关系的一种数据结构。在C++中，通过使用指针和动态内存分配，我们可以方便地实现邻接表有向图。

邻接表是一种链式存储结构，包括两个部分：一个是节点数组，一个是链式存储的边集数组。每个节点在节点数组中保留一个节点信息，以及一个指向其出边集的指针。而边集数组中的每个元素包含了一条边的信息，包括出发节点和目的节点等。对于每个节点，其出边集就是以该节点为起点的所有边的集合。因此，邻接表有待优化的方面就是出边集的遍历。

通过C++中的动态内存分配，我们可以很方便地定义邻接表。首先，我们定义一个节点类，用于存储节点信息和其出边集的指针，如下所示：

class Node {
public:
  int data;    // 节点信息
  Edge* first;  // 指向出边集的指针
};

其中，Edge是边类，包含了边的信息，如下所示：

class Edge {
public:
  int to;     // 目的节点
  int weight;   // 权重
  Edge* next;   // 指向下一条相同起点的边的指针
};

而邻接表就是由Node和Edge组成的一个结构体数组，如下所示：

struct Graph {
  int n;     // 节点数
  Node* nodes;  // 节点数组，包含指向出边集的指针
  Edge* edges;  // 边集数组
};

在初始化邻接表时，我们首先根据节点数n动态分配节点数组和边集数组。然后，将节点数组中每个元素的指针赋值为NULL。最后，我们遍历边集数组，为每个节点的出边集连接它们所指向的边。这个过程可以通过双重循环来实现，如下所示：



void init(Graph& g, int n, Edge* edges, int m) {


  g.n = n;


  g.nodes = new Node[n];


  g.edges = edges;


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


    g.nodes[i].first = NULL;


  }


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


    int from = edges[i].from;


    int to = edges[i].to;


    edges[i].next = g.nodes[from].first;


    g.nodes[from].first = &edges[i];


  }


}

对于邻接表有向图的遍历，我们可以采用深度优先遍历或广度优先遍历两种方式。在深度优先遍历时，我们需要一个标记数组，用于记录每个节点是否被遍历过。我们从某个起始节点开始遍历，依次访问其出边集中的节点，如果该节点未被访问，则对该节点继续进行深度优先遍历。具体实现可以采用递归或栈来实现。

而在广度优先遍历时，我们同样需要一个标记数组，以及一个队列。从某个起始节点开始，遍历其出边集中的所有节点，并将它们加入队列中。然后，遍历队列中的节点，重复以上过程，直到队列为空或者所有节点都被遍历完。

除了遍历操作外，邻接表还支持添加节点和边、删除节点和边等操作。对于添加节点，在节点数组中分配一个新的节点，然后将其指针赋值为NULL。对于添加边，在边集数组中分配一条新的边，然后将其插入起点节点的出边集中。而对于删除节点和边，则需要依次遍历节点和边，找到需要删除的节点和边，然后将它们从邻接表中移除。

综上所述，邻接表是一种十分常用的数据结构，用于表示图的连通关系。在有向图中，每个节点可以指向其他节点，通过使用指针和动态内存分配，我们可以方便地实现邻接表有向图，并进行遍历和其他操作。

  
  

评论区