图--基本概念与术语

存储结构

邻接矩阵

邻接表

十字链表

遍历

最小生成树

最短路径

$\bullet$ 基本概念或术语

图是边和顶点的集合，表示为G(V,E)或G(V,{E})，其中V是非空顶点集合，E是边集合；图是一种多对多的数据结构

无向边：使用圆括号标识，记作(vi,vj)或(vj,vi)

有向边：使用尖括号标识，记作<vi,vj>，又名弧，其中vi为弧尾

无向图：V均为无向边

有向图：V均为有向边

邻接点：边的两侧顶点，无向边互为邻接点，有向边<vi,vj>称之为vi邻接到vj，vj邻接自vi

顶点的度：

$\alpha$ 无向图：与该点关联的边数，记作TD(v)

$\beta$ 有向图：入度ID+出度OD，记作TD(v)

简单图：不存在顶点到自身且边不重复

无向完全图：任意两个顶点之间都存在边则称为无向完全图。其顶点对应的最大边数为n*(n-1)/2

有向完全图：任意两个顶点存在方向相反的两条弧。其顶点对应的最大边数为n*(n-1)

权：边的意义值，带权的图一般称作网

顶点与边的关系：

$\alpha$ 无向图的边数等于各顶点的度数和，记作e= ${\frac{1}{2} }$ $\sum\nolimits_{i=1}^nTD(vi)$

$\beta$ 有向图的边数等于各顶点的出度或入度和，记作e= $\sum\nolimits_{i=1}^nID$ = $\sum\nolimits_{i=1}^bnOD$

路径长度：路径上边或弧的数目

回路或环：从顶点A出发回到自身，经过的路径唯一

简单路径：顶点不重复出现的路径

连通图：

$\alpha$ 任意两个顶点之间都有路径(可到达)称为连通图

$\beta$ 非连通的无向图中的连通子图称为连通分量

其子图为

（顶点EF在父图中只有一条相关边，故为连通分量）

（缺少父图顶点A的临边AD和C的临边CD，故非连通分量）

$\gamma$ 有向图中，任意两个顶点。从vi到vj和从vj到vi均有路径，则称为强连通图，非连通的有向图的

子图其连通分量称为强连通分量

$\delta$ 对连通图进行遍历，过程中经历的点边组合视为一颗普通树，称为生成树

$\ast$ 包含连通图中的所有顶点

$\ast$ 任意两顶点之间有且仅有一条路径

$\varepsilon$ 有向图中一顶点入度为0其余顶点入度为1的叫有向树

$\epsilon$ 非连通图的遍历过程中经历的点边组合，称为生成森林

最后编辑于：2021.10.25 22:15:38

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

图--基本概念与术语

图--基本概念与术语

相关阅读更多精彩内容

友情链接更多精彩内容