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

C++邻接矩阵图的实现

2023-07-05 08:50:00 深夜i -- --

C++ 邻接矩阵图实现数据结构

图是由若干个顶点及它们之间的边组成的，其中顶点和边都有各自的特点和属性。在C++中，可以使用邻接矩阵表示图。邻接矩阵是一个二维数组，用于表示图中每个顶点之间的关系。

邻接矩阵的元素有两种值，0和1，其中0表示两个顶点没有直接边相连，1表示两个顶点之间有一条直接边相连。邻接矩阵可以通过一个二维数组来表示，该数组的大小是N×N，其中N为图中顶点的数量。

在C++中，可以使用以下代码来实现邻接矩阵图：


#include<iostream>
#include<cstring>
using namespace std;
const int MAXN = 100;
bool graph[MAXN][MAXN]; //邻接矩阵
int n; //顶点数量
void init(){
  memset(graph, 0, sizeof(graph)); //初始化矩阵
  cin >> n; //输入顶点数量
  int u, v;
  while(cin >> u >> v){ //输入边
    graph[u][v] = graph[v][u] = true;
  }
}
void print_graph(){
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      cout << graph[i][j] << " ";
    }
    cout << endl;
  }
}
int main(){
  init(); //初始化图
  print_graph(); //打印图
  return 0;
}

在上面的代码中，我们定义了一个邻接矩阵和顶点数量。首先，我们输入顶点数量，然后输入边。根据输入的边，我们在邻接矩阵中将相应的元素设为1。最后，我们打印邻接矩阵，以显示图的结构。

使用邻接矩阵实现图的优点在于，可以很方便地判断两个顶点之间是否有直接边相连。只需要访问二维数组中相应的元素即可。但是，邻接矩阵所占用的空间较大，当图非常稠密时，很多空间都是浪费的。此外，在进行图的遍历和搜索时，邻接矩阵的效率比邻接表低。

总之，邻接矩阵是一个简单而有效的表示图的方式，在C++编程中，它可以很容易地实现。但是，需要根据具体的需求来选择适合的数据结构来表示图，以达到更好的效果。

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

下一篇: C++类声明头文件

评论区

()

相似文章