文档介绍：第七章. 图(Chapter 7. Graph)
§ 图的定义及基本操作
图型结构是一种非常重要的、比线性和树型结构更复杂的非线性数据结构,可广泛用于描述自然界各种关系。
右图所示即为一图型结构:
A
B
C
E
F
D
Graph = (V,R)
其中:V={ ai | ai∈D0, i=1,2,…,n, n≥0 }
R={ E }
E={ <x,y> | P(x, y)∧(x, y∈V) }
其中 D0 为某一数据对象,
V 为顶点集,E 为边集。
图的一些基本术语:
顶点(vertex)
数据元素所构成的结点通常称为顶点。
弧(arc)
若两个顶点间有关系<x,y> ∈E ,则称<x,y> 为一条弧。
弧头(head--又称终端点 terminal node)
若<x,y> 为一条弧,则顶点 y 称为弧头。
弧尾(tail--又称初始点 initial node)
若<x,y> 为一条弧,则顶点 x 称为弧尾。
有向图(directed graph)
若<x,y> ∈E ,并不总有<y,x> ∈E,则称此图为有向图。
无向图(undirected graph)
若<x,y> ∈E ,总有<y,x> ∈E,则称此图为无向图。
边(edge)
无向图中两条弧<x,y>和<y,x>可用一条边( x,y )来表示。
pleted graph)
具有 n*(n-1)/2 条边的无向图称为完全图。
pleted directed graph)
具有 n*(n-1) 条弧的有向图称为有向完全图。
稀疏图(sparse graph)
边数很少的图称为稀疏图。
权(weight)
有些图的边或弧具有一定的大小,称之为权。
work)
带权值的图又称为网或网络。
子图(subgraph)
由图的部分顶点和边组成的新图称为原图的子图。
生成子图(spanning subgraph)
由图的全部顶点和部分边组成的子图称为原图的生成子图。
稠密图(dense graph)
边数很多的图称为稠密图。
邻接点(adjacent)
若边(vi,vj) ∈E,则 vi 与 vj 互为邻接点。
依附(incident)
若边(vi,vj) ∈E,则称边(vi,vj)依附于顶点 vi 和 vj 。
相关联(correlative)
若边(vi,vj) ∈E,又称边(vi,vj)与顶点 vi 和 vj 相关联。
顶点的度(degree)
与顶点相关联的边数称为该顶点的度,又分为入度和出度。
顶点的入度(indegree)
以顶点为头的弧数称为该顶点的入度。
顶点的出度(outdegree)
以顶点为尾的弧数称为该顶点的出度。
路径(path)
由顶点vi经过一系列边和顶点到达顶点vj所得到的顶点序列。
回路(loop--又称环 cycle)
起点和终点为同一顶点的路径称为回路。
连通(connected)
无向图中顶点vi到vj间有路径存在,则称vi和vj是连通的。
连通图(connected graph)
无向图中任意两顶点间均存在路径,则称该图为连通图。
连通分量(ponent)
无向图中的极大连通子图称为原图的连通分量。
强连通图(strongly connected graph)
有向图中任意两顶点间均存在路径,则称该图为强连通图。
强连通分量(strongly ponent)
有向图中的极大强连通子图称为原图的强连通分量。
生成树(spanning tree)
连通图的极小连通生成子图称为原图的生成树。
有向树(directed tree)
恰有一个顶点入度为0 ,其余顶点入度均为1的有向图。
生成森林(spanning forest)
由多棵有向树构成的有向图的生成子图称为生成森林。
最小代价生成树(minimum cost spanning tree)
连通网中由最小权值的边构成的生成树。
图的基本操作:
Initiate
Getvertex
Firstadj
Nextadj
Insvertex
Traverse
Insarc
Delvertex
Delarc
§ 图的存储结构
顺序存储结构:
A
B
C
E
F
D
1、邻接矩阵(adjacency matrix)
A B C D E F
0 0 0 0 0 1
1 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 1 0 0 0 0
0 0 0 0 1 0
A
B
C
D
E
F
Aij =
{
0 (vi,vj) ∈E
1 (vi