|
|
|
知识路径： > 计算机科学基础 > 数据结构与算法基本概念 > 数据结构与算法 > 图 >
|
|
相关知识点：5个
|
|
|
|
|
图是由一个非空的顶点集合和一个描述顶点之间多对多关系的边（或弧）集合组成的一种数据结构，它可以形式化地表示为：
|
|
|
|
|
|
其中V=｛x|x?某个数据对象集｝，它是顶点的有穷非空集合；E=｛（x，y） |x, y? V｝或E=｛|x，y?V且Path （x, y）｝,它是顶点之间关系的有穷集合，也称为边集合，PathP （x，y）表示从x到y的一条单向通路。
|
|
|
|
通常，也将图G的顶点集和边集分别记为V （G）和E （G）。E （G）可以是空集，若E （G）为空，则图G只有顶点而没有边。
|
|
|
|
若图G中的每条边都是有方向的，则称G为有向图。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。例如，有序对有向边i，vj>表示一条由vi到vj的有向边。有向边又称为弧，也称为边弧，边弧的始点vi称为弧尾（Tail），边弧的终点vj称为弧头（Head）。若图G中的每条边都是没有方向的，则称G为无向图。无向图中的边均是顶点的无序对，无序对通常用圆括号表示。
|
|
|
|
|
|
|
|
| |
|
|
|
