数据结构“图”
数据结构“图”

数据结构“图”

图是一种非线性数据结构,由「节点(顶点)」和「边」组成,每条边连接一对顶点。根据边的方向有无,图可分为「有向图」和「无向图」。本文 以无向图为例 开展介绍。

如下图所示,此无向图的 顶点 和 边 集合分别为:

顶点集合: vertices = {1, 2, 3, 4, 5}
边集合: edges = {(1, 2), (1, 3), (1, 4), (1, 5), (2, 4), (3, 5), (4, 5)}

表示图的方法通常有两种:

邻接矩阵: 使用数组 vertices 存储顶点,邻接矩阵 edges 存储边; edges[i][j] 代表节点 i + 1 和 节点 j + 1 之间是否有边。

C++实现如下:

int vertices[5] = {1, 2, 3, 4, 5};
int edges[5][5] = {{0, 1, 1, 1, 1},
                   {1, 0, 0, 1, 0},
                   {1, 0, 0, 0, 1},
                   {1, 1, 0, 0, 1},
                   {1, 0, 1, 1, 0}};

邻接表: 使用数组 vertices 存储顶点,邻接表 edges 存储边。 edges 为一个二维容器,第一维 i 代表顶点索引,第二维 edges[i] 存储此顶点对应的边集和;例如 edges[0] = [1, 2, 3, 4] 代表 vertices[0] 的边集合为 [1, 2, 3, 4]

C++实现如下:

int vertices[5] = {1, 2, 3, 4, 5};
vector<vector<int>> edges;

vector<int> edge_1 = {1, 2, 3, 4};
vector<int> edge_2 = {0, 3};
vector<int> edge_3 = {0, 4};
vector<int> edge_4 = {0, 1, 4};
vector<int> edge_5 = {0, 2, 3};
edges.push_back(edge_1);
edges.push_back(edge_2);
edges.push_back(edge_3);
edges.push_back(edge_4);
edges.push_back(edge_5);

邻接矩阵 VS 邻接表 :

邻接矩阵的大小只与节点数量有关,即 N^2,其中 N 为节点数量。因此,当边数量明显少于节点数量时,使用邻接矩阵存储图会造成较大的内存浪费。
因此,邻接表适合存储稀疏图(顶点较多、边较少); 邻接矩阵适合存储稠密图(顶点较少、边较多)。

0 0 投票数
打个分吧!
guest
0 评论
内联反馈
查看所有评论
0
希望看到您的想法,请您发表评论x
()
x