数据结构与C++ 知识量:9 - 32 - 91
邻接矩阵是表示图的一种方法,尤其适用于表示有限图。邻接矩阵中的每个元素表示相应顶点之间的连接关系。
对于无向图,邻接矩阵是一个对称矩阵,即矩阵的左上角和右下角是对称的。对于有向图,邻接矩阵不一定对称。
邻接矩阵的优点是易于计算图的任意两个顶点之间是否有边,以及任意顶点的度(包括入度和出度)。此外,邻接矩阵还可以直观地看出任意顶点的邻接点。
然而,邻接矩阵的空间复杂度较高,特别是对于稀疏图(边较少的图),邻接矩阵会占用大量空间。在这种情况下,使用邻接表或其他数据结构可能更为有效。
以下是一个简单的C++代码示例,用于表示有向图的邻接矩阵:
#include <iostream> #include <vector> using namespace std; const int MAX_SIZE = 100; // 最大顶点数 int n, m; // n为顶点数,m为边数 vector<vector<int>> adjMatrix; // 邻接矩阵 void initGraph() { adjMatrix.resize(n, vector<int>(n, 0)); // 初始化邻接矩阵 } void addEdge(int u, int v) { adjMatrix[u][v] = 1; // 添加从u到v的边 } void removeEdge(int u, int v) { adjMatrix[u][v] = 0; // 删除从u到v的边 } bool isEdge(int u, int v) { return adjMatrix[u][v] == 1; // 判断是否存在从u到v的边 } int main() { cin >> n >> m; // 输入顶点数和边数 initGraph(); // 初始化邻接矩阵 for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; // 输入边的起点和终点 addEdge(u, v); // 添加边 } // 在此处可以添加其他操作,例如遍历邻接矩阵、查找特定顶点的邻接点等 return 0; }
这个示例代码中,使用一个二维向量adjMatrix来表示邻接矩阵。通过initGraph()函数初始化邻接矩阵,然后使用addEdge()函数添加边,使用removeEdge()函数删除边,使用isEdge()函数判断是否存在边。在主函数中,首先输入顶点数和边数,然后输入每条边的起点和终点,并使用addEdge()函数添加边。
邻接表是另一种表示图的方法,特别适用于稀疏图(边较少的图)。邻接表通过链式存储法,将与每个顶点相邻的顶点存储在一个链表中,从而节省空间。
对于无向图,邻接表中的每个表结点都对应于以该顶点为起点的边。因此,对于n个顶点的无向图,邻接表中有n个表结点,每个表结点都指向一个单向链表,链表中存储的是与该顶点相邻的顶点。
对于有向图,邻接表中的每个表结点都对应于以该顶点为起点的出边。因此,对于n个顶点的有向图,邻接表中有n个表结点,每个表结点都指向一个单向链表,链表中存储的是以该顶点为起点的出边所指向的顶点。
邻接表的优点是空间利用率高,特别是对于稀疏图,可以大大减少空间的使用。此外,邻接表在进行某些图的操作时(如广度优先搜索或深度优先搜索)也更加方便。
然而,邻接表在处理边的连接关系时不如邻接矩阵直观。此外,邻接表需要额外的指针来存储链表,增加了实现难度。
以下是一个简单的C++代码示例,用于表示有向图的邻接表:
#include <iostream> #include <vector> using namespace std; const int MAX_SIZE = 100; // 最大顶点数 int n; // 顶点数 vector<int> adjList[MAX_SIZE]; // 邻接表 void initGraph() { for (int i = 0; i < n; i++) { adjList[i].clear(); // 清空邻接表 } } void addEdge(int u, int v) { adjList[u].push_back(v); // 将v添加到u的邻接表中 } void removeEdge(int u, int v) { for (int i = 0; i < adjList[u].size(); i++) { if (adjList[u][i] == v) { adjList[u].erase(adjList[u].begin() + i); // 从u的邻接表中删除v break; } } } bool isAdjacent(int u, int v) { for (int i = 0; i < adjList[u].size(); i++) { if (adjList[u][i] == v) { return true; // v是u的邻接点 } } return false; // v不是u的邻接点 } int main() { cin >> n; // 输入顶点数 initGraph(); // 初始化邻接表 for (int i = 0; i < n-1; i++) { int u, v; cin >> u >> v; // 输入边的起点和终点 addEdge(u, v); // 添加边 } // 在此处可以添加其他操作,例如遍历邻接表、查找特定顶点的邻接点等 return 0; }
这个示例代码中,使用一个一维数组adjList来表示邻接表。通过initGraph()函数初始化邻接表,然后使用addEdge()函数添加边,使用removeEdge()函数删除边,使用isAdjacent()函数判断是否存在边。在主函数中,首先输入顶点数,然后输入每条边的起点和终点,并使用addEdge()函数添加边。
十字链表(Orthogonal List)是有向图的另一种链式存储结构。该结构可以看成是将有向图的邻接表和逆邻接表结合起来得到的。用十字链表来存储有向图,可以达到高效的存取效果。同时,代码的可读性也会得到提升。
在十字链表中,对应于有向图中每一条弧都有一个结点,对应于每个定顶点也有一个结点。十字链表之于有向图,类似于邻接表之于无向图。也可以理解为将行的单链表和列的单链表结合起来存储稀疏矩阵称为十字链表,每个节点表示一个非零元素。
构成:用链表模拟矩阵的行(或者列,这可以根据个人喜好来定),然后,再构造代表列(或者是行)的链表,将每一行中的元素节点插入到对应的列中去。
十字链表的逻辑结构就像是一个围棋盘,而非零元就好像是在棋盘上放的棋子,总共占的空间就是,确定那些线的表头节点和那些棋子代表的非零元节点。
以下是一个使用C++表示十字链表的示例代码:
#include <iostream> #include <vector> using namespace std; const int MAX_SIZE = 100; // 最大顶点数 // 定义十字链表结点结构体 struct Node { int row, col, data; // 行索引、列索引、数据值 Node* prev; // 指向上一个结点的指针 Node* next; // 指向下一个结点的指针 }; int n; // 顶点数 vector<Node*> rowHead[MAX_SIZE]; // 行头指针数组,用于存储第i行的第一个结点 vector<Node*> colHead[MAX_SIZE]; // 列头指针数组,用于存储第j列的第一个结点 // 初始化十字链表 void initList() { for (int i = 0; i < n; i++) { rowHead[i] = nullptr; } for (int j = 0; j < n; j++) { colHead[j] = nullptr; } } // 在第i行添加一个结点 void addNode(int i, int j, int data) { Node* newNode = new Node(); newNode->row = i; newNode->col = j; newNode->data = data; newNode->prev = nullptr; newNode->next = rowHead[i]; if (rowHead[i] != nullptr) { rowHead[i]->prev = newNode; } else { colHead[j] = newNode; // 第i行只有一个结点时,将其加入到第j列的头指针中 } rowHead[i] = newNode; // 将新结点添加到第i行的头指针中 } // 在第j列删除一个结点,并调整相关指针 void removeNode(int j, int data) { Node* p = colHead[j]; // 从第j列的第一个结点开始遍历 while (p != nullptr && p->data != data) { // 找到要删除的结点的前驱结点 p = p->next; } if (p == nullptr) { // 没有找到要删除的结点 return; } if (p->prev != nullptr) { // 前驱结点不为空,调整前驱结点的后继指针 p->prev->next = p->next; } else { // 第j列的第一个结点就是要删除的结点,调整第j列的头指针 colHead[j] = p->next; } if (p->next != nullptr) { // 后继结点不为空,调整后继结点的前驱指针 p->next->prev = p->prev; } // 第i行的最后一个结点就是要删除的结点,调整第i行的尾指针为nullptr(在removeNode函数中没有处理这个特殊情况) delete p; // 删除结点p }
Copyright © 2017-Now pnotes.cn. All Rights Reserved.
编程学习笔记 保留所有权利
MARK:3.0.0.20240214.P35
From 2017.2.6