牛小飞《数据结构》9.1图的基本概念和存储结构.pptx

图和图的存储结构图的定义和术语图的存储表示小结用java语言描述图的存储结构课堂练习

1.图的定义2.图的名词和术语3.图的基本操作图和图的存储结构

图(graph)是由一个顶点(vertex)集V和一个边(edge|弧arc)集E构成的数据结构。每条边(edge)是一副点对(v,w)，其中v,w∈V。表示从v到w的一条边(弧)，称v为弧尾(tail)，w为弧头(head)。图的定义

图的定义—有向图如果“弧”是有方向的，则称由顶点集和弧集构成的图为有向图(digraph)。EACBD例如:G1=(V1,E1)V1={A,B,C,D,E}E1={A,B,A,E,B,C,C,D,D,B,D,A,E,C}

若v,w?E必有w,v?E,则以无序对(v,w)代替这两个有序对，称(v,w)为顶点v和顶点w之间存在一条边。上述这种由顶点集和边集构成的图称作无向图。图的定义—无向图

图的定义—无向图例如:G2=(V2,E2)BCAFEDV2={A,B,C,D,E,F}E2={(A,B),(A,E),(B,E),(B,F),(C,D),(C,F)(D,F}弧除了有向和无向的含义之外，有时候还具有第三种成分，称为权(weight)或值(cost)。

子图、网01完全图、稀疏图、稠密图02邻接点、度、入度、出度03路径、路径长度、简单路径、简单回路04连通图、强连通图、弱连通图05名词和术语

名词和术语1）子图、网设图G=(V,{E})和图G?=(V?,E?),且V??V,E??E,则称G?为G的子图。EACBDEACBDB

名词和术语弧或边带权的图分别称作有向网或无向网。ABEC子图、网设图中有n个顶点，e条边，则含有e=n(n-1)/2条边的无向图称作完全图;含有e=n(n-1)条弧的有向图称作有向完全图;若边或弧的个数enlogn，则称作稀疏图，否则称作稠密图。名词和术语2）完全图、稀疏图、稠密图

3）邻接点、度、入度、出度邻接点：假若顶点v和顶点w之间存在一条边，则称顶点v和w互为邻接点，度：和顶点v关联的边的数目，记为TD（v）。边(v,w)和顶点v和w相关联。名词和术语ACDFEBTD(B)=3TD(A)=2

名词和术语3）邻接点、度、入度、出度ABECD顶点的出度:以顶点v为弧尾的弧的数目;记为OD（v）对于右图所示的有向图来说，由于弧有方向性，则有入度和出度之分。

3）邻接点、度、入度、出度顶点的入度:以顶点v为弧头的弧的数目，记为ID（v）顶点的度(TD)=出度(OD)+入度(ID)ID(B)=2OD(B)=1TD(B)=3名词和术语ABECDID(A)=1OD(A)=2TD(A)=3

名词和术语3）邻接点、度、入度、出度ABECD在一个图中，所有顶点的度数之和等于所有边数的（）倍。A.1/2B.1C.2D.4ACDFEB思考

名词和术语ABECD4）路径、路径长度、简单路径、简单回路、圈(环)路径：设图G=(V,{E})中的一个顶点序列{u=v1,v2,…,vN=w}中，(vi,vi+1)?E，0≤iN，则称从顶点u到顶点w之间存在一条路径。如:从A到D长度为3的路径{A,B,C,D}路径长度：路径上边的数目。

名词和术语简单路径:指序列中顶点不重复出现的路径。简单回路:指序列中第一个顶点和最后一个顶点相同的路径。圈(cycle):是满足v1=vN且长至少为1的一条路径。如果该路径是简单路径，那么这个圈就是简单圈。一个有向无圈图简称为DAG。ABECD4）路径、路径长度、简单路径、简单回路、圈(环)

名词和术语5）连通图、强连通图、弱连通图连通图：若无向图G中任意两个顶点之间都有路径相通，则称此图为连通图;BACDFE

名词和术语5）连通图、连通分量、强连通图、强连通分量连通分量：若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。BACDFE

名词和术语强连通图：若有向图任意两个顶点之间都存在一条有向路径，则称为强连通图。ABECD若有向图去掉弧的方向后是连通的，则称为弱连通图。5）连通图、强连通图、弱连通图否则，其各个强连通子图称作它的强连通分量。ABECD

对顶点的访问操作结构的建立和销毁遍历插入或删除顶点插入和删除弧对邻接点的操作基本操作

CreatGraph(V,E):01//按定义(V,E)构造图02DestroyGra