图的基本术语，邻接矩阵、邻接表表示方法
图的定义图是一种与线性表和树相比更复杂的数据结构，在图形结构中，结构之间的关系可以是任意的，图中任意两个元素之间都可能相关
图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V，E），其中G表示一个图，V是图G中顶点的集合，E是图中边的集合，顶点也就是树中的结点。
图的分类
无向边：若顶点vi到vj之间的边没有方向，则称这条边为无向边，用（vi，vj）表示。最多为n（n-1）/2条边。
https://img-blog.csdnimg.cn/ead40c00fd564ffa9470080527fe7b5c.png
有向边：若vi到vj之间有方向，称为有向边，则用表示，最多有n（n-1）条
https://img-blog.csdnimg.cn/76c8bee918304734b11465a7830deae7.png
有向图的权
有些图或弧具有与它相关的数字，这种与图的边或弧相关的树叫做权（Weight）
这些权可以表示从一个顶点到另一个顶点的距离或耗费，这种带权的图通常称为网（Network）
https://img-blog.csdnimg.cn/872645d9dd0a4b39bbdc09ee50b58e32.png
子图
https://img-blog.csdnimg.cn/f5e24b01b87347b5835dcea96c9967a6.png
连通性
在无向图G中如果两个点之间有路径可以到达，则称这两个点是连通的。如果对于图中任意两个顶点都可以到达，则会称G为连通图。
邻接矩阵
图的邻接矩阵储存方法是用两个数组表示
一个一维数组存储图中顶点信息
一个二维数组（邻接矩阵）储存图中的边或者弧的信息
https://img-blog.csdnimg.cn/0e10841b9b444bc0b5e2409390d24a20.png
为1表示两个点是连通的
邻接矩阵
https://img-blog.csdnimg.cn/2040c0be67f240c4a2fe83e55f6916e9.png
https://img-blog.csdnimg.cn/23dfc7767ffb46dfbfa99adce3adce7b.png
https://img-blog.csdnimg.cn/8226794080a447eb85fbb2d5e3f81fc9.png
邻接矩阵储存的结构
typedef char VertexType; //定义顶点类型
typedef int EdgeType; //边上权值类型由用户定义
#define MAXVEX 100 //最大顶点数
#define INFINITY 65535 //表示两个顶点不连通
typedef srtuct{
VertexType vexs; //顶点表
EdgeType arc;//边表
int numVertexes,numEdges; //图中当前的顶点数和边数
}MGraph; 领接表
图中顶点用一个一维数组储存，当然顶点也可以用单链表储存，不过数组可以较容易地读取顶点信息。另外对于顶点数组中，每个数据元素还需要储存指向第一个邻接点地指针，以便于查找该顶点的边信息。
https://img-blog.csdnimg.cn/a4b177c065124186ac2bd5a612d86486.png
https://img-blog.csdnimg.cn/e140ef98265b4afca94a468b81925e08.png
邻接表的存储的结构
typedef char VertexType; //顶点类型
typedef int EdgeType; //边的权值
typedef struct EdgeNode{
int adjvex; //存储该顶点对应的下表
EdgeType weight; //用于储存权值，对于非网图不需要
struct EdgeNode *next; //链域，指向下一个邻接点
}EdgeNode; 邻接矩阵储存的结构
typedef struct VertexNode{ //顶点表结构，就一个信息和一个尾巴
VertexType data； //顶点域，存储顶点信息
EdgeNode *firstedge; //边表头指针
}VertexNode,AdjList;
typedef struct{
AdjList adjList； //结构体数组
int numVertexes,numEdges; //图中当前顶点数和边数
}GraphAdjList;
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]