数据结构

位置:IT落伍者 >> 数据结构 >> 浏览文章

数据结构之图的概念[1]


发布日期:2019年09月28日
 
数据结构之图的概念[1]

三种数据结构比较

线性表数据元素之间仅有线性关系每个数据元素只有一个直接前驱和一个直接后继

树形结构数据元素之间有着明显的层次关系并且每一层上的数据元素可能和下一层中多个元素相关但只能和上一层中一个元素相关

图形结构结点之间的关系可以是任意的图中任意两个元素之间都可能相关

图的基本术语

图(Graph)图G由两个集合V和E组成记为G=(VE)这里V是顶点的有穷非空集合E是边(或弧)的集合而边(或弧)是V中顶点的偶对

顶点(Vertex)图中的结点又称为顶点

边(Edge)相关顶点的偶对称为边

有向图(Digraph)若图G中的每条边都是有方向的则称G为有向图

弧(Arc)又称为有向边在有向图中一条有向边是由两个顶点组成的有序对有序对通常用尖括号表示

弧尾(Tail)边的始点

弧头(Head)边的终点

无向图(Undigraph)若图G中的每条边都是没有方向的则称G为无向图

无向完全图(Undirected Complete Graph)恰好有n(n)/的无向图

有向完全图(Directed Complete Graph)恰好有n(n)条弧的有向图

邻接点(Adjacent)若(vivj)是一条无向边则称顶点vi和vj互为邻接点

度(Degree)无向图中顶点v的度是关联于该顶点的边的数目记为TD(v)

入度(Indegree)若G为有向图则把以顶点v为终点的边的数目称为v的入度记为ID(v)

出度(Outdegree)若G为有向图则把以顶点v为始点的边的数目称为v的出度记为OD(v)

对于有向图TD(v)=ID(v)+OD(v)

子图(Subgraph)设G=(VE)是一个图若E是E的子集V是V的子集使得E中的边仅与V中顶点相关联则图G=(VE)称为图G的子图

路径(Path)无向图G=(VE)中从顶点v到顶点v的路径是一个顶点序列(v=vivivin=v)其中(vijvij)∈E≤j≤n有向图G=(VE)中从顶点v到顶点v的路径是一个顶点序列(v=vivivin=v)其中〈vijvij〉∈E≤j≤n

简单路径序列中顶点不重复出现的路径

环(Cycle)又称回路第一个顶点和最后一个顶点相同的路径

简单回路又称简单环除了第一个顶点和最后一个顶点外其余顶点不重复的回路

连通在无向图G中如果从顶点v到顶点v有路径则称v和v是连通的

[] []

               

上一篇:数据结构之图的概念[2]

下一篇:数据结构 4.10 链队列中删除元素的特殊情况