【免费】DSAinC++10-图1资源-CSDN文库

数据结构

需积分: 0 35 浏览量 2022-08-04 13:47:54 上传评论收藏 975KB PDF 举报

资源详情

资源评论

资源推荐

2022/4/6

第10章图

电子信息学院

王文伟 WangWenwei,Dr.‐Ing.

Tel:189‐71562600

Email:[email protected]

课程QQ群:珞珈EIS数据结构与算法

，

668792335

第10章图

TableofContents

电子信息学院

本

章

位

置

本章介绍具有非线

性关系的图结构，

重点讨论图的基本

概念及图的存储结

构，还将介绍图结

构中的常用算法，

如遍历算法、图的

生成树和最短路径

等。

第1章绪论

第2章 C++编程基础

第3章遍历、迭代与递归

第4章字符串

第5章排序算法

第6章线性表

第7章栈与队列

第8章数组和广义表

第9章树和二叉树

第10章图

第11章查找算法

第10章图

TableofContents

电子信息学院

10.0简介

10.1图的定义与基本术语

10.2图的存储结构

10.3图的遍历

10.4最小代价生成树

10.5最短路径

第10章图

10.0Introduction



图(Graph)是数据元素集合及元素间的关系集合组

成的数据结构，元素之间的关系没有限制，任意

元素之间可以有关系 (相邻)，即每个数据元素可

有多个前驱元素，多个后继元素。图是一种比线

性表和树更复杂的非线性数据结构。



图是表示离散结构的一种有力的工具，可以用来

描述现实世界的众多问题。图论是离散数学的重

要分支。



本章介绍具有非线性关系的图结构，重点讨论图

的概念、存储结构和遍历，并讨论图的生成树、

最短路径等。

第10章图

10.1图的定义与基本术语

10.1.1 图的定义

10.1.2 结点与边的关系

10.1.3 子图与生成子图

10.1.4 路径、回路及连通性

10.1.5 图的基本操作

第10章图

10.1.1 图的定义

图(graph)是由结点集合及结点间的关系集合组成的一种数

据结构，任意两个元素之间都可能有某种关系。图中结点

（node）之间的关系称为边(edge)。一个图记作G=(V, E)。

V = { x | x∈某个数据元素集合}

E = { e(x,y) | x,y∈V} 或 E = { e<x,y> | x, y∈V}

2022/4/6

第10章图

图的术语

undirected edge:用结点的无序偶对e(x,y)代表一

条无向边，相邻关系。undirected graph:无向图



directed edge:

用结点的有序偶对e<x,y>代表一条

有向边 (

弧，arc

) ，<x,y>和<y,x>分别表示两条

不同的有向边。directed graph:有向图



起点和终点是同一个结点的边，即边e(v,v)或e<v,v>，

称为环（loop）。例如，G

中的边<v

,v

>就是环。



无环且无重边的无向图称为简单图

。



第10章图

图的术语(II)

complete graph:完全图。边数达到最大值，n个

结点的完全图记为K

。有n个结点的无向图，其

边的最大数目为n×(n ‐1)/2；有n个结点的有向

图，其弧的最大数目为n×(n‐1)。

sparsegraph和densegraph:有n个结点的图，其

边的数目如果远小于n

，则称为稀疏图。图的边

数如果接近最大数目，则称为稠密图。

weighted graph或network:带权图或网，每条边上

都加注一个称作权（weight）的数值，表示结点

对相关的强度信息，例如：从一个结点到另一

个结点的距离、花费的代价、所需的时间等。

第10章图

图的示例

第10章图

10.1.2结点与边的关系



adjacent node :若e(v

, v

)是无向图中的一条边，则称v

和v

是相邻结点，边e(v

, v

)与结点v

和v

相关联。



Degree:与结点v相关联的边的数目称为结点的度，表

示为TD(v)。度为1的结点称为悬挂点。



在有向图中，以v为终点的弧数称为v的入度ID(v)；

以v为起点的弧数称为v的出度OD(v)。出度为0的结点

称为终端结点。TD(v) = ID(v ) + OD(v)



度与边数的关系:

TD( )





111

ID() OD()

TD() ID() OD() 2

nnn

ii i

iii

vve

vv ve







 





有向图

无向图

第10章图

10.1.3子图与生成子图



subgraph:设图G = (V, E)，G' = (V', E')，

若V'≤V，E'≤E，并且E'中的边所关联的结点

都在V'中，则称图G'是G的子图。如果G' ≠

G，则称G'是G的真子图。



spanning subgraph: 如果G'是G的子图，且

V’=V，称图G'是G的生成子图。=> 生成树

第10章图

10.1.4路径、回路及连通性



路径、路径长度、回路:在图中，若从结点v

出发，沿一些边依次经过结点v

, v

, …,

到达结点v

，则称结点序列(v

, v

, …, v

, v

)是从v

到v

的一条路径。这

条路径上边的数目定义为路径长度。如果在

一条路径中，除起点和终点外，其他结点都

不相同，则称为简单路径。起点和终点相同

且长度大于1的简单路径成为回路。带权图中，

从起点到终点的路径上各条边的权值之和称

为这条路径的（加权）路径长度。

2022/4/6

第10章图

连通图



connected graph:在无向图G中，若从结点v

到v

有一

条路径，则称v

和v

是连通的。若图G中任意两个结

点都连通，则称G为连通图。



connected component:非连通图的极大连通子图称为

该图的连通分量。



一个有向图G中，若存在一个结点v

，从v

有路径可

以到达图G中其他所有结点，则称为有根的图，称

为图G的根。

(a) 无向图的两个连通分量C

和C

(b) 强连通有向图G

第10章图

10.1.5图的基本操作



Initialize：初始化。建立一个图实例。



AddNode /AddNodes：在图中设置、添加结点。



Get/Set：访问。获取或设置图中的指定结点。



Count：求图的结点个数。



AddEdge/AddEdges：在图中设置、添加边，即结点之

间的关联。



Nodes/Edges：获取结点表或边表。



Remove：删除。从图中删除一个元素及相关联的边。



Contains/IndexOf：查找。在图中查找满足某种条件的

数据元素。



Traversal:遍历。按某种次序访问图中的所有结点，并

且每个结点恰好访问一次。



Copy：复制。复制一个图。

第10章图

10.2图的存储结构

图是结点和边的集合，图的存储结构要记录这两

方面的信息。

• 结点的集合可以用一个称之为结点表的线性表来表示；

• 图中一条边表示两个结点的邻接关系，图的边集可以

用邻接矩阵（adjacencymatrix）或邻接表（adjacency

list）表示。邻接矩阵是一种顺序存储结构，而邻接

表是一种链式存储结构。

10.2.1 图结构的邻接矩阵表示法

10.2.2 图结构的邻接表表示法

第10章图

10.2.1图结构的邻接矩阵表示法



图结构的邻接矩阵用来表示边集，即结点间

相邻关系集合。设G=(V, E)是一个具有n个结

点的图，G的邻接矩阵A是具有下列性质的n

阶方阵:

1(,) ,

0(,) ,

ij ij

vv E vv E

















若e 或

若e

或

0111

1010

1101

1010











第10章图

邻接矩阵



无向图的邻接矩阵是对称的，即a

=a

。有向图

的邻接矩阵不一定对称。



用邻接矩阵表示一个有n个结点的图结构，需要

个存储单元。空间复杂度为O(n

)



0100

0010

1001

1000











第10章图

带权图的邻接矩阵

 在带权图中，设w

表示边（v

, v

）或<v

, v

上的权值，该图的邻接矩阵定义如下：



(, ) ,

ij i j i j i j

ij i j ij ij

wvvvvEvvE

avvvvEvvE





 





 









若且或

若

且或

若



0354 0 3 5

309 0 4

5907 0 6

470 2 0





 



 

 



 







 



 





 

剩余12页未读，继续阅读

评论收藏

内容反馈

彥爷

粉丝: 17
资源: 311

DSAinC++10-图1

评论0

最新资源

DSAinC++10-图1

评论0

DSAinC++8-数组与广义表1

DSAinC++9-树与二叉树1

DSAinC++6-线性表1

DSAinC++2-C++编程基础1

DSAinC++11-查找算法1

DSAinC++1-绪论1

DSAinC++5-排序算法1

DSAinC++7-栈与队列1

DSAinC++3-遍历迭代与递归1

win10环境下vscode运行opencv(C++)(解压即用)-1号包

c++入门，核心，提高讲义笔记

仿照Visionmaster，用C++、Qt编写的视觉软件（注意：是发布版，非源码）

C++STL库常用库函数总结

c++小游戏 c++小游戏

mingw-w64-install.exe

C/C++中文帮助文档

我的世界简易版（C++编写，源代码+程序）

cmu 15445 2023spring project0

QT中利用TCP协议实现了一个多线程的文件互传系统

win10环境下vscode运行opencv(C++)(解压即用)-2号包

第十五届蓝桥杯大赛软件赛省赛-C/C++ 研究生组

第十五届蓝桥杯大赛软件赛省赛-C++A组题目

VC++6.0简易安装板

MinGW-w64安装包

一个免费的c++小游戏集合

第十五届蓝桥杯大赛软件赛省赛C++B组题目

VS2019企业版离线安装包（百度网盘）

Delphi 12 - 含工具、安装、控件、文章

华为OD机考-统一考试机试-含ABCD卷-含java、c++、JavaScript、python-题目

最新资源