数据结构 - 图的基本概念

2019/03/07 20:43
阅读数 113

数据结构 - 图的基本概念

图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个事物间具有这种关系。图论是一种表示 "多对多" 的关系。

比如下面这张图

图的组成

图是由顶点和边组成的:。

图(graph)是由一些点(vertex)和这些点之间的连线(edge)所组成的(可以无边,但至少包含一个顶点);其中,点通常被成为"顶点(vertex)",而点与点之间的连线则被成为"边或弧"(edege)。通常记为,G=(V,E)。

  • 一组顶点:通常用 V(vertex) 表示顶点集合
  • 一组边:通常用 E(edge) 表示边的集合

 

图的分类

有向图和无向图

图可以分为有向图和无向图,在图中:

  • (v, w) 表示无向边,即 v 和 w 是互通的
  • <v, w> 表示有向边,该边始于 v,终于 w

上面的有向图包含了"A,B,C,D,E"共7个顶点,而且包含了"<A,B>,<A,D>,<A,E>,<B,C>,<C,D>,<D,E>"共6条边。

上面的无向图包含了"A,B,C,D,E"共7个顶点,而且包含了"(A,B),(A,D),(A,E),(B,C),(C,D),(D,E)"共6条边。

 

有权图和无权图

图可以分为有权图和无权图:

  • 有权图:每条边具有一定的权重(weight),通常是一个数字
  • 无权图:每条边均没有权重,也可以理解为权为 1

 

连通图和非连通图

图又可以分为连通图和非连通图:

  • 连通图:所有的点都有路径相连
  • 非连通图:存在某两个点没有路径相连

 

图顶点的度

图中的顶点有度的概念:

  • 度(Degree):所有与它连接点的个数之和
  • 入度(Indegree):存在于有向图中,所有接入该点的边数之和
  • 出度(Outdegree):存在于有向图中,所有接出该点的边数之和

 

图的表示

图在程序中的表示一般有两种方式:

1. 邻接矩阵:

  • 在 n 个顶点的图需要有一个 n × n 大小的矩阵
  • 在一个无权图中,矩阵坐标中每个位置值为 1 代表两个点是相连的,0 表示两点是不相连的
  • 在一个有权图中,矩阵坐标中每个位置值代表该两点之间的权重,0 表示该两点不相连
  • 在无向图中,邻接矩阵关于对角线相等

2. 邻接表:

  • 对于每个顶点,存储着一个链表,用来指向所有与该点直接相连的点
  • 对于无向图来说,使用邻接表进行存储也会出现数据冗余,表头结点A所指链表中存在一个指向C的表结点的同时,表头结点C所指链表也会存在一个指向A的表结点

例如在无向无权图中:

在无向有权图中:

可以看出在无向图中,邻接矩阵关于对角线对称,而邻接链表总有两条对称的边

而在有向无权图中:

3. 邻接矩阵和邻接表对比

  1. 邻接矩阵由于没有相连的边也占有空间,因此存在浪费空间的问题,而邻接链表则比较合理地利用空间
  2. 邻接表比较耗时,牺牲很大的时间来查找,因此比较耗时,而邻接矩阵法相比邻接链表法来说,时间复杂度低。

4. 选择存储结构

根据图的 稠密程度 选择存储结构,假设图有 N 个节点 E 条边,若:

E << N^2 则为交叉少的稀疏图

使用邻接表存储只连接的节点,节省存储空间;使用邻接矩阵将要存储大量的 0 值,浪费空间。

E ≈ N^2 则为交叉多的稠密图

使用邻接矩阵将十分方便的查询连通性,较少的浪费存储空间。邻接表将查找麻烦。

 

图的遍历

图的遍历就是要找出图中所有的点,一般有以下两种方法:

1. 深度优先遍历:(Depth First Search, DFS)

基本思路:深度优先遍历图的方法是,从图中某顶点 v 出发

  1. 访问顶点 v
  2. 从 v 的未被访问的邻接点中选取一个顶点 w,从 w 出发进行深度优先遍历
  3. 重复上述两步,直至图中所有和v有路径相通的顶点都被访问到

伪码实现:

//伪码实现,类似于树的先序遍历
public void DFS(Vertex v){
    visited[v] = true;
    for(v 的每个邻接点 W){
	if(!visited[W]){
	    DFS(W);
	}
    }
}

2. 广度优先搜索:(Breadth First Search, BFS)

广度优先搜索,可以被形象地描述为 "浅尝辄止",它也需要一个队列以保持遍历过的顶点顺序,以便按出队的顺序再去访问这些顶点的邻接顶点。

实现思路:

  1. 顶点 v 入队列
  2. 当队列非空时则继续执行,否则算法结束
  3. 出队列取得队头顶点 v;访问顶点 v 并标记顶点 v 已被访问
  4. 查找顶点 v 的第一个邻接顶点 col
  5. 若 v 的邻接顶点 col 未被访问过的,则 col 继续
  6. 查找顶点 v 的另一个新的邻接顶点 col,转到步骤 5 入队列,直到顶点 v 的所有未被访问过的邻接点处理完。转到步骤 2

要理解深度优先和广度优先搜索,首先要理解搜索步,一个完整的搜索步包括两个处理

  1. 获得当前位置上,有几条路可供选择
  2. 根据选择策略,选择其中一条路,并走到下个位置

相当于在漆黑的夜里,你只能看清你站的位置和你前面的路,但你不知道每条路能够通向哪里。搜索的任务就是,给出初始位置和目标位置,要求找到一条到达目标的路径。

  • 深度优先就是,从初始点出发,不断向前走,如果碰到死路了,就往回走一步,尝试另一条路,直到发现了目标位置。这种不撞南墙不回头的方法,即使成功也不一定找到一条好路,但好处是需要记住的位置比较少。
  • 广度优先就是,从初始点出发,把所有可能的路径都走一遍,如果里面没有目标位置,则尝试把所有两步能够到的位置都走一遍,看有没有目标位置;如果还不行,则尝试所有三步可以到的位置。这种方法,一定可以找到一条最短路径,但需要记忆的内容实在很多,要量力而行。

===========END===========

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部