数据结构与算法课件：图结构.ppt

数据结构与算法

图结构

学习目标

§理解图的定义和相关的基本概念

§掌握图的邻接矩阵和邻接表存储结构

§掌握图基本操作的实现

§掌握并实现图的深度优先和广度优先有哪些信誉好的足球投注网站算法，理解图的

连通性及连通分量概念

§理解图的生成树概念，掌握求图最小代价生成树的两个算

法

§理解有向无环图的概念，掌握图的拓扑排序算法，掌握关

键路径算法

§理解最短路径概念，掌握迪杰斯特拉算法和弗洛伊德算法

的求解过程

§了解各算法的时间复杂度

本章主要内容

图的基本概念

15图的生成树

图的存储结构DAG图及其应用

26

图基本操作的实现

37最短路径

4图的遍历

第一节图的基本概念

§图（graph）由顶点和边组成

§一般地，用G=(V,E)来表示，其中V表示顶

点（vertex）集，是一个有穷非空集合；E

表示边（edge）集，E中的每条边都是V中

某一对顶点的连接

§当顶点分别是u和v时，连接这两个顶点的

边可以表示为一个二元组(u,v)，有时也将边

称为顶点的偶对

§图中任意两个不同顶点之间允许有边，但不能

超过一条

基本概念

§图G=(V,E)中，顶点总数记为|V|，边的总数

记为|E|

§如果图中边的数目较少（相对于顶点数来

说），则图称为稀疏图

§边数较多的图称为密集图或是稠密图

§至于边数多到多少是密集图或少到多少是稀疏

图，并没有严格的界定

§当图中边数的数量级不高于顶点数的数量级时

，就可以认为图是稀疏图

基本概念

§当图中的边限定为从一个顶点指向另一个

顶点时，称为有向边，或称为弧（arc）

§不限定方向的边称为无向边

§一条无向边可以看成是两条方向相反的有向边

§组成有向边的偶对看作是有序的

§组成无向边的偶对是无序的

基本概念

§有向边(u,v)表示从顶点u指向顶点v的边，弧的

方向是从u指向v，u称为弧尾（tail），v称为弧

头（head）

§对于有向边，(u,v)与(v,u)不同

§无向边(u,v)既可以表示从顶点u指向顶点v，也

可以表示从顶点v指向顶点u

§对于无向边，(u,v)与(v,u)是等价的

基本概念

§含有向边的图称为有向图（directedgraph或

简写为digraph）

§如果图中的边都是无向边，则图称为无向

图（undirectedgraph或简写为undigraph）

§如果一个图中既含有有向边，又含有无向

边，则可以将其中所有的无向边表示为一

对方向相反的有向边

§提到有向图时，表明其中所含的边全部都是有

向边

基本概念

§若无向图G中含有边(u,v)，则u和v互为邻接

点（adjacent）

§边(u,v)称为与顶点u和v相关联（incident）

，也可以说边(u,v)依附于顶点u和v

§对于有向图中的有向边(u,v)，称顶点v是顶

点u的邻接点

§顶点u邻接到顶点v，或顶点v邻接自顶点u

§可以给边赋予一个非负的数值，这个非负

数值称为边的权（weight），相应的图称为

带权图（weightedgraph）或是加权图

§可以让各顶点带有标号，这样的图称为标

号图（labedledgraph）

§本章讨论的图大多是标号图，标号可以作为顶

点的名称

示例

§图中两个顶点之间的边不能有重复

§无向图中两个顶点之间最多只能有一条边

§有向图中两个顶点之间最多有两条方向相反的

弧

§图中不包含(i,i)形式的边，即没有顶点自身

到自身的边

§在无向图中，与顶点v相关联的边的数目称

为顶点的度（degree）

§在有向图中，顶点的度分为出度和入度

§以某顶点为弧头的弧称为该顶点的入边，

入边的数目称为该顶点的入度

§以某顶点为弧尾的弧称为该顶点的出边，

出边的数目称为该顶点的出度

§一个顶点的出度和入度之和称为该顶点的

度

§有n个顶点的无向图中，其边数最多可达

n(n-1)/2

§有向图中由于边具有方向性，所以可能的

最大边数比无向图多了一倍，含n个顶点的

有向图中最大边数为n(n-1)

§包含了所有可能边的图称为完全图（

com