图的定义和术语：有向图、无向图和图的存储结构

有向图“弧”是有方向的-数据结构课件 本资源摘要信息来自一份数据结构课件，主要讲解了有向图的定义、术语和基本概念。下面是从中提取的相关知识点： 1. 图的定义：图是一种数据结构，由一个顶点集V和一个弧集R构成，记为Graph=(V,R)。其中，V是顶点集，R是弧集。 2. 弧的定义：弧是有方向的，从v到w的一条弧记为<v,w>，其中v是弧尾，w是弧头。谓词P(v,w)定义了弧<v,w>的意义或信息。 3. 有向图的定义：有向图是一种图，其中每条弧都有方向。例如，G1=(V1,VR1)，其中V1={A,B,C,D,E}，VR1={<A,B>,<A,E>,<B,C>,<C,D>,<D,B>,<D,A>,<E,C>}。 4. 无向图的定义：无向图是一种图，其中每条边都没有方向。例如，G2=(V2,VR2)，其中V2={A,B,C,D,E,F}，VR2={(A,B)，(A,E)，(B,E)，(C,D)，(D,F)，(B,F)，(C,F)}。 5. 子图的定义：设图G=(V,{VR})和图G’=(V’,{VR’}),若V’⊆V，VR’⊆VR，则称G’为G的子图。 6. 弧或边带权的图：弧或边带权的图分别称作有向网或无向网。 7. 图的分类：图可以分为稀疏图和稠密图。稀疏图是指边或弧的个数e<nlogn的图，而稠密图是指边或弧的个数e≧nlogn的图。 8. 顶点的度：顶点的度是指和顶点v关联的边的数目。出度是指以顶点v为弧尾的弧的数目，入度是指以顶点v为弧头的弧的数目。顶点的度=出度+入度。 9. 邻接点：如果顶点v和顶点w之间存在一条边，则称顶点v和w互为邻接点。 本资源摘要信息对有向图的定义、术语和基本概念进行了详细的讲解，涵盖了图的定义、弧的定义、有向图和无向图的定义、子图、弧或边带权的图、图的分类、顶点的度和邻接点等知识点，为学习和研究数据结构提供了重要的参考价值。