图的存储及相互转换数据结构代码
时间: 2024-06-20 09:02:52 浏览: 10
图的存储方式有多种,常见的有邻接矩阵和邻接表两种方式。
邻接矩阵是一种二维数组,其中数组元素a[i][j]表示顶点i和顶点j之间是否有边相连。如果是无向图,则a[i][j] = a[j][i] = 1表示有边相连,否则为0。如果是有向图,则只需要将a[i][j] = 1表示从i到j有一条有向边。
邻接表则是一个数组,其中每个元素对应一个顶点,该元素保存了一个链表,链表中存储该顶点所连的所有边。每个链表节点包含两个元素:邻接点编号和指向下一个链表节点的指针。
下面是邻接矩阵和邻接表转换为相互的代码:
// 邻接矩阵转换为邻接表
void matrixToList(int matrix[][MAXSIZE], int n, vector<vector<int>> &list) {
list.resize(n + 1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (matrix[i][j] == 1) {
list[i].push_back(j);
}
}
}
}
// 邻接表转换为邻接矩阵
void listToMatrix(vector<vector<int>> &list, int n, int matrix[][MAXSIZE]) {
memset(matrix, 0, sizeof(matrix));
for (int i = 1; i <= n; i++) {
for (int j = 0; j < list[i].size(); j++) {
matrix[i][list[i][j]] = 1;
}
}
}
以上代码仅供参考,实际使用时需要根据具体情况进行修改。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)