1.基本概念
图(Graph)是一种较线性表和树更为复杂的非线性结构。是对结点的前趋和后继个数不加限制的数据结构,用来描述元素之间“多对多”的关系(即结点之间的关系是任意的)。
一个图G = (V,E)由顶点(vertex)集V(G)和边(edge)集E(G)组成。E中的每一条边连接V中两个不同的顶点。
1、有向图(digraph)
如果图中每一条边上两个顶点都是有序的,那么图就叫做是有向图(directed graph)。 可以用带尖括号的有序点对<ν,ω>来表示有向图的一条边,其中ν,ω∈V(G)。 有向图中的边都是有方向的,称之为有向边。对于有向边来说,<ν,ω>和<ω,ν>表示的是两条方向相反的边。 有向图中的边也可称之为弧(arc),ν可称之为弧尾(tail)或初始点(initial node),ω可称之为弧头(head)或终端点(terminal node)。
V(G1)={ν1,ν2,ν3,ν4}
E(G1)={<ν1,ν2>,<ν2,ν1>,<ν3,ν1>,<ν3,ν4>,<ν2,ν4>}
2、无向图(undigraph)
3、邻接点
4. 度、入度和出度
5、完全图、稀疏图与稠密图
6. 路径与回路
7、子图
8、连通图
9、生成树
10、网
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。