数据结构|数据结构学习笔记（第六章图）数据结构|算法|图|大数据

文章图片

概述 【数据结构|数据结构学习笔记（第六章图）】图的定义这里不多加描述了，下面给出几种图的图像。

文章图片

这是有向图，无向图和有向完全图。
简单图：1.不存在重复边2.不存在顶点到自身的边
多重图: 某两个顶点间的边数大于一条，又允许顶点通过一条边与自身关联。
完全图：任意两个顶点间都有边
关于其他基本概念可看下面这个博主写的超级详细
数据结构：图(Graph)【详解】_UniqueUnit的博客-CSDN博客_数据结构图
图的存储及基本操作邻接矩阵法用一个一维数组存储顶点的信息，用一个二维数组存储边的关系（即顶点间的邻接关系），这个二维数组成为邻接矩阵。

文章图片

#define MaxVertexNum 100//顶点数目 typedef char VertexType; //顶点数据类型 typedef int EdgeType; //边上权值数据类型 typedef struct{ VertexType Vex[MaxVertexNum]; //顶点表 EdgeType Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵 int vexnum,arcnum; //图的当前顶点数和弧数 }MGraph;

文章图片

注：无向图的邻接矩阵是对称矩阵，邻接矩阵空间复杂度为o（n2），n为顶点数
性质
1.无向图邻接矩阵为对称矩阵。
2.无向图第i行（或i列），非0（或非无穷）元素的个数正好为顶点i的度。
对于有向图，第i行非0元素个数为顶点i出度，第i列非0个数为入度。
3.稠密图适合使用邻接矩阵的存储表示。
邻接表法图的邻接表法结合了顺序存储和链式存储。给每个顶点建立个单链表，称为边表，边表的头指针和顶点数据信息采用顺序结构，称为顶点表。

文章图片

下面是无向图和有向图的示例图：

文章图片

文章图片

性质：
1.对于稀疏图，采用邻接表将极大节省存储空间。
2.图的邻接表表示不唯一。
3.在邻接表中，给出一顶点，找出他的邻边很容易。
4.无向图空间复杂度是o（v+2e），有向图为o（v+e），v为顶点集，e为边集
十字链表是有向图的一种链式结构，每个弧和顶点都分别对应一个结点。

文章图片

从左往右：前两个指弧尾弧头，三四个指弧头弧尾相同的下一条弧，第五个指向该弧的相关信息。data为顶点相关信息，后面两个指向以该顶点为弧头弧尾的第一个弧结点。

文章图片

不唯一，很容易求出度和入度。一个十字链表确定一个图。
邻接多重表无向图的另一种链式存储，每条边用一个结点表示。

文章图片

下图为示例：

文章图片

图的基本操作

文章图片

图的遍历广度优先搜索（BFS）类似于二叉树的层次遍历算法
无论是用邻接矩阵还是邻接表，我们都需要一个辅助队列，用邻接表时时间复杂度为o（v+e），用邻接矩阵时，时间复杂度为o（v2）。
广度优先搜索算法_幽蓝丶流月的博客-CSDN博客_广度优先搜索
广度优先搜索算法（附C++实现）_cclplus的博客-CSDN博客_c++广度优先搜索
广度优先生成树