ToB企服应用市场:ToB评测及商务社交产业平台

标题: 图的基本术语，邻接矩阵、邻接表表示方法 [打印本页]
作者: 种地    时间: 2022-6-25 01:59
标题: 图的基本术语，邻接矩阵、邻接表表示方法
图的定义

图是一种与线性表和树相比更复杂的数据结构，在图形结构中，结构之间的关系可以是任意的，图中任意两个元素之间都可能相关
图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V，E），其中G表示一个图，V是图G中顶点的集合，E是图中边的集合，顶点也就是树中的结点。
图的分类

无向边：若顶点vi到vj之间的边没有方向，则称这条边为无向边，用（vi，vj）表示。最多为n（n-1）/2条边。

有向边：若vi到vj之间有方向，称为有向边，则用表示，最多有n（n-1）条


有向图的权

有些图或弧具有与它相关的数字，这种与图的边或弧相关的树叫做权（Weight）
这些权可以表示从一个顶点到另一个顶点的距离或耗费，这种带权的图通常称为网（Network）

子图 


连通性

在无向图G中如果两个点之间有路径可以到达，则称这两个点是连通的。如果对于图中任意两个顶点都可以到达，则会称G为连通图。
邻接矩阵

图的邻接矩阵储存方法是用两个数组表示
一个一维数组存储图中顶点信息
一个二维数组（邻接矩阵）储存图中的边或者弧的信息

为1表示两个点是连通的 
邻接矩阵


 
 
 邻接矩阵储存的结构

  1. typedef char VertexType;           //定义顶点类型
  2. typedef int EdgeType;              //边上权值类型由用户定义
  3. #define MAXVEX 100                 //最大顶点数
  4. #define INFINITY 65535             //表示两个顶点不连通
  5. typedef srtuct{
  6.     VertexType vexs[MAXVEX];       //顶点表
  7.     EdgeType arc[MAXVEX][MAXVEX];  //边表
  8.     int numVertexes,numEdges;      //图中当前的顶点数和边数
  9. }MGraph;
复制代码
领接表

图中顶点用一个一维数组储存，当然顶点也可以用单链表储存，不过数组可以较容易地读取顶点信息。另外对于顶点数组中，每个数据元素还需要储存指向第一个邻接点地指针，以便于查找该顶点的边信息。

 
 邻接表的存储的结构

  1. typedef char VertexType;   //顶点类型
  2. typedef int EdgeType;      //边的权值
  3. typedef struct EdgeNode{   
  4.     int adjvex;            //存储该顶点对应的下表
  5.     EdgeType weight;       //用于储存权值，对于非网图不需要
  6.     struct EdgeNode *next; //链域，指向下一个邻接点
  7. }EdgeNode;
复制代码
邻接矩阵储存的结构

  1. typedef struct VertexNode{          //顶点表结构，就一个信息和一个尾巴
  2.     VertexType data；               //顶点域，存储顶点信息
  3.     EdgeNode *firstedge;            //边表头指针
  4. }VertexNode,AdjList[MAXVEX];
  8. typedef struct{
  9.     AdjList adjList；             //结构体数组
  10.     int numVertexes,numEdges;       //图中当前顶点数和边数     
  11. }GraphAdjList;
复制代码


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4