C++ 图的实现代码 |21xrx.com

C++ 图的实现代码

2023-07-12 05:26:22 深夜i -- --

C++ 图实现代码图论

C++是一种非常流行的高级编程语言，它具有强大的面向对象编程能力和高效的计算性能，被广泛应用于许多领域，包括图形学、机器学习、数据分析等。

在编写C++程序时，图是一种非常常见的数据结构。图是由若干个顶点和若干个边组成的抽象数据类型，用来描述各种复杂的关系和网络。对于图的实现，我们通常会使用邻接矩阵和邻接表两种方式。

邻接矩阵是一种二维数组，用来表示图中各个顶点之间的关系。设图有$n$个顶点，$m$条边，那么邻接矩阵就是一个$n\times n$的矩阵，其中矩阵的第$i$行第$j$列表示从顶点$i$到顶点$j$是否有一条边，如果有则为$1$，否则为$0$。下面是一个简单的邻接矩阵实现代码：


const int MAXN = 100;
int G[MAXN][MAXN], n, m;
void add_edge(int u, int v) {
  G[u][v] = G[v][u] = 1;
}
void remove_edge(int u, int v) {
  G[u][v] = G[v][u] = 0;
}
bool has_edge(int u, int v) {
  return G[u][v] == 1;
}

在这个实现代码中，$G$表示邻接矩阵，$G[i][j]$表示从顶点$i$到顶点$j$是否有一条边。$add\_edge(u,v)$函数用来在顶点$u$和顶点$v$之间增加一条边，$remove\_edge(u,v)$函数用来删除顶点$u$和顶点$v$之间的一条边，$has\_edge(u,v)$函数用来判断顶点$u$和顶点$v$之间是否有边相连。

除了邻接矩阵，我们还可以使用邻接表来实现图。邻接表是一种链表结构，用来表示某个顶点的所有相邻点。设图有$n$个顶点，$m$条边，那么邻接表就是一个长度为$n$的链表数组，其中每个链表表示相应顶点的所有邻接点。下面是一个简单的邻接表实现代码：


const int MAXN = 100;
struct Edge next; edge[MAXN<<1];
int head[MAXN], tot = 0;
void add_edge(int u, int v) {
  edge[++tot].to = v;
  edge[tot].next = head[u];
  head[u] = tot;
}
void remove_edge(int u, int v) {
  for (int i = head[u], last = 0; i; last = i, i = edge[i].next) {
    int j = edge[i].to;
    if (j == v) { edge[last].next = edge[i].next; return; }
  }
}
bool has_edge(int u, int v) {
  for (int i = head[u]; i; i = edge[i].next) {
    int j = edge[i].to;
    if (j == v) return true;
  }
  return false;
}

在这个实现代码中，$edge$表示邻接表，$edge[i].to$表示节点$i$连接的顶点，$edge[i].next$表示节点$i$连接的下一个节点。$head$表示链表数组，表示每个节点的第一个相邻节点。$add\_edge(u,v)$函数用来在顶点$u$和顶点$v$之间增加一条边，$remove\_edge(u,v)$函数用来删除顶点$u$和顶点$v$之间的一条边，$has\_edge(u,v)$函数用来判断顶点$u$和顶点$v$之间是否有边相连。

以上是关于C++实现图的邻接矩阵和邻接表两种方式的代码，需要根据实际需求进行选择。但无论是邻接矩阵还是邻接表，都是用来处理图的非常有效的方法，是C++程序员必备的基础技能之一。

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

下一篇: Node.js数组操作指南

评论区

()

相似文章