数据结构

2023-06-06 03:01| 来源: 网络整理| 查看: 265

一、引言

二、图的基本概念

三、图的存储方式

1. 邻接矩阵

2. 邻接表

3. 十字链表

4. 邻接多重表

四、邻接表的实现

1. 邻接表的定义

2. 邻接表的构建

3. 邻接表的遍历

五、邻接表的优缺点

六、总结

一、引言

在计算机科学中，图是一种非常重要的数据结构，它是由节点和边组成的一种数据结构，可以用来表示各种实际问题，如社交网络、路线规划等。在图的存储方式中，邻接表是一种常用的方式，它可以有效地表示图的结构，并且具有较高的效率。本文将介绍图的基本概念、存储方式以及邻接表的实现方法，希望能够帮助读者更好地理解和应用图的相关知识。

二、图的基本概念

在图的定义中，有两个基本概念：节点和边。节点也称为顶点，是图中的基本元素，通常用一个圆圈或方框表示。边是节点之间的连接关系，通常用一条线段表示。图可以分为有向图和无向图两种类型，有向图中的边是有方向的，而无向图中的边是无方向的。

图的表示方法有多种，其中最常用的是邻接矩阵和邻接表。邻接矩阵是一个二维数组，其中每个元素表示两个节点之间是否有边相连。如果节点i和节点j之间有边相连，则邻接矩阵中第i行第j列的元素为1，否则为0。邻接矩阵的缺点是空间复杂度较高，当图的节点数较大时，会占用大量的内存空间。

三、图的存储方式 1. 邻接矩阵

邻接矩阵是一种常用的图的存储方式，它可以用一个二维数组表示图的结构。在邻接矩阵中，每个元素表示两个节点之间是否有边相连。如果节点i和节点j之间有边相连，则邻接矩阵中第i行第j列的元素为1，否则为0。

邻接矩阵的优点是可以快速地判断两个节点之间是否有边相连，时间复杂度为O(1)。但是邻接矩阵的缺点是空间复杂度较高，当图的节点数较大时，会占用大量的内存空间。

以下是C++实现邻接矩阵的构造、析构、深度优先遍历、广度优先遍历的代码：

#include #include using namespace std; const int MAXN = 100; // 最大顶点数 const int INF = 0x3f3f3f3f; // 无穷大 class Graph { private: int n; // 顶点数 int e; // 边数 int **matrix; // 邻接矩阵 public: Graph(int n, int e); // 构造函数 ~Graph(); // 析构函数 void addEdge(int u, int v, int w); // 添加边 void dfs(int u, bool visited[]); // 深度优先遍历 void bfs(int u); // 广度优先遍历 }; Graph::Graph(int n, int e) { this->n = n; this->e = e; matrix = new int*[n]; for (int i = 0; i < n; i++) { matrix[i] = new int[n]; for (int j = 0; j < n; j++) { matrix[i][j] = INF; // 初始化为无穷大 } } } Graph::~Graph() { for (int i = 0; i < n; i++) { delete[] matrix[i]; } delete[] matrix; } void Graph::addEdge(int u, int v, int w) { matrix[u][v] = w; matrix[v][u] = w; // 无向图需要反向也加一次 } void Graph::dfs(int u, bool visited[]) { visited[u] = true; cout right; while (p->right != nullptr) { p = p->right; } p->right = node; } // 找到to对应的头结点 head = &headNodes[to]; // 如果头结点的下指针为空，直接将新节点挂在下指针上 if (head->down == nullptr) { head->down = node; } else { // 否则，找到最后一个节点，将新节点挂在其下侧 OLNode* p = head->down; while (p->down != nullptr) { p = p->down; } p->down = node; } } // 打印图 void print() { for (int i = 0; i < headNodes.size(); i++) { HeadNode* head = &headNodes[i]; OLNode* p = head->right; while (p != nullptr) { cout next != nullptr) { cur = cur->next; } cur->next = newNode; } // 由于是无向图，所以还需要将目标节点的邻接表中插入源节点 newNode = new AdjListNode; newNode->dest = src; newNode->next = nullptr; if (adjList[dest] == nullptr) { adjList[dest] = newNode; } else { AdjListNode* cur = adjList[dest]; while (cur->next != nullptr) { cur = cur->next; } cur->next = newNode; } } // 打印邻接表 void printAdjList() { for (int i = 0; i < V; i++) { cout

【本文地址】

公司简介

联系我们