数据结构---图

数据结构---图

Scroll Down

一、图的定义

在这里插入图片描述

① 邻接:

  如果两个顶点被同一条边连接,就称这两个顶点是邻接的,如上图 I 和 G 就是邻接的,而 I 和 F 就不是。有时候也将和某个指定顶点- - 邻接的顶点叫做它的邻居,比如顶点 G 的邻居是 I、H、F。

② 路径:

  路径是边的序列,比如从顶点B到顶点J的路径为 BAEJ,当然还有别的路径 BCDJ,BACDJ等等。

③ 连通图和非连通图:

  如果至少有一条路径可以连接起所有的顶点,那么这个图称作连通的;如果假如存在从某个顶点不能到达另外一个顶点,则称为非联通的。

在这里插入图片描述

④ 有向图和无向图:

  如果图中的边没有方向,可以从任意一边到达另一边,则称为无向图;比如双向高速公路,A城市到B城市可以开车从A驶向B,也可以开车从B城市驶向A城市。但是如果只能从A城市驶向B城市的图,那么则称为有向图。

⑤ 有权图和无权图:

  图中的边被赋予一个权值,权值是一个数字,它能代表两个顶点间的物理距离,或者从一个顶点到另一个顶点的时间,这种图被称为有权图;反之边没有赋值的则称为无权图。

⑥ 完全图:

  如果图中的 每个顶点都有一条边可以直达每个顶点,那么称这样的图为完全图。