图( Graph)是一种较线性表和树更为复杂的非线性结 构。在线性结构中,结点之间的关系是线性关系,除开 始结点和终端结点外,每个结点只有一个直接前趋和直 接后继。在树形结构中,结点之间的关系实质上是层次 关系,同层上的每个结点可以和下一层的零个或多个结 点(即孩子)相关,但只能和上一层的一个结点(即双 亲)相关(根结点除外)。然而在图结构中,对结点 (图中常称为顶点)的前趋和后继个数都是不加限制的, 即结点之间的关系是任意的。图中任意两个结点之间都 可能相关。由此,图的应用极为广泛,特别是近年来的 迅速发展,已渗透到诸如语言学、逻辑学、物理、化学、 电讯工程、计算机科学以及数学的其它分支中
图 图（Graph）是一种较线性表和树更为复杂的非线性结 构。在线性结构中，结点之间的关系是线性关系，除开 始结点和终端结点外，每个结点只有一个直接前趋和直 接后继。在树形结构中，结点之间的关系实质上是层次 关系，同层上的每个结点可以和下一层的零个或多个结 点（即孩子）相关，但只能和上一层的一个结点（即双 亲）相关（根结点除外）。然而在图结构中，对结点 （图中常称为顶点）的前趋和后继个数都是不加限制的， 即结点之间的关系是任意的。图中任意两个结点之间都 可能相关。由此，图的应用极为广泛，特别是近年来的 迅速发展，已渗透到诸如语言学、逻辑学、物理、化学、 电讯工程、计算机科学以及数学的其它分支中
基本定义和术语 若图G中的每条边都是有方向的,则称G为有向图 ( Digraph)。在有向图中,一条有向边是由两个顶点 组成的有序对,有序对通常用尖括号表示。例如 V>表示一条有向边,v是边的始点(起点),v是边 的终点。因此,和是两条不同的有 向边。有向边也称为弧(Arc),边的始点称为弧尾 (Tai),终点称为弧头(Head) 图G由两个集合V和E组成,记为G=(V,E),其中v是 顶点的有穷非空集合,E是V中顶点偶对(称为边)的 有穷集。通常,也将图G的顶点集和边集分别记为v(G) 和F(G)。E(G)可以是空集,若E(G)为空,则图G只有顶 点而没有边,称为空图
基本定义和术语 • 若图G中的每条边都是有方向的，则称G为有向图 （Digraph）。在有向图中，一条有向边是由两个顶点 组成的有序对，有序对通常用尖括号表示。例如，＜vi， vj＞表示一条有向边，vi是边的始点（起点），vj是边 的终点。因此，＜vi，vj＞和＜vj，vi＞是两条不同的有 向边。有向边也称为弧（Arc），边的始点称为弧尾 （Tail），终点称为弧头（Head）。 • 图G由两个集合V和E组成，记为G＝(V，E)，其中v是 顶点的有穷非空集合，E是V中顶点偶对（称为边）的 有穷集。通常，也将图G的顶点集和边集分别记为V(G) 和E(G)。E(G)可以是空集，若E(G)为空，则图G只有顶 点而没有边，称为空图
若(v;,v)是一条无向边,则称顶点v;和v;互为邻接点 ( Adjacent,或称v和v相邻接;称(v,y)关联( Incident) 于顶点v和v,或称(v;,v,)与顶点v和v相关联。如图7 1中Gn,与顶点V相邻接的顶点是v,V和v,而关联于 顶点v2的边是(v,V2),(V2,V2)和(V2,)。若是一条有向边,则称顶点v邻接到v顶点v邻接于 点v并称边关联于v和V或称与顶 点v和v相关联。如图71中G1,关联于顶点v的边是和< 无向图中顶点v的度( Degree是关联于该顶点的边的数 目,记为D(y)。若G为有向图,则把以顶点v为终点的 边的数目,称为v的人度( Indegree),记为ID();把以 顶点v为始点的边的数目,称为v的出度( outdegree,记 为OD(V);顶点v的度则定义为该顶点的入度和出度之 和,即D()=ID(v)十OD(y)
若(vi，vj )是一条无向边，则称顶点vi和vj互为邻接点 (Adjacent)，或称vi和vj相邻接；称(vi，vj )关联(Incident) 于顶点vi和vj，或称(vi，vj )与顶点vi和vj相关联。如图7- 1中G2，与顶点vl相邻接的顶点是v2，v3和v4，而关联于 顶点v2的边是(vl，v2 )，(v2，v3 )和(v2，v4 )。若＜vi，vj ＞是一条有向边，则称顶点vi邻接到vj ,顶点vj邻接于顶 点vi ,并称边＜vi，vj＞关联于vi和vj或称＜vi，vj＞与顶 点vi和vj相关联。如图7-1中Gl，关联于顶点v2的边是＜ v1，v2＞，＜v2，vl＞和＜v2 ,v3＞。 无向图中顶点v的度(Degree)是关联于该顶点的边的数 目，记为D(v)。若G为有向图，则把以顶点v为终点的 边的数目，称为v的人度(1ndegree)，记为ID(v)；把以 顶点v为始点的边的数目，称为v的出度(outdegree)，记 为OD(v)；顶点v的度则定义为该顶点的入度和出度之 和，即D(v)＝ID(v)十OD(v)
在无向图G中,若存在一个顶点序列 Vp2 vil?v2…,Vm,vq 使得(vpv),(vnY2),…,(vm,v)均属于E(G),则 称顶点vn到v存在一条路径(Path)。若G是有向图,则 路径也是有向的,它由E(G)中的有向边, 1,V2>,…,组成。路径长度定义为该路 径上边的数目。若“条路径上除了v和v可以相同外 其余顶点均不相同,则称此路径为一条简单路径。起 点和终点相同(vn=v)的简单路径称为简单回路或简单 环Cyle)。例如,在图G2中顶点序列vv2,v3,v4是 条从顶点v到顶点v的长度为3的简单路径;顶点序列 V12V2,Va,V,v32是一条从顶点v到顶点v2的长度为4的 路径,但不是简单路径;顶点序列v,v2,v4,v是一 个长度为3的简单环。在有向图G中,顶点序列v,v2, V是一个长度为2的有向简单环
在无向图G中，若存在一个顶点序列vp ,vi1,vi2…，vin，vq， 使得(vp，vil)，(vi1,vi2)，…，(vin，vq )均属于E(G)，则 称顶点vp到vq存在一条路径(Path)。若G是有向图，则 路径也是有向的，它由E(G)中的有向边＜vp，vil＞，＜ vil，vi2＞，…，＜vin，vq＞组成。路径长度定义为该路 径上边的数目。若一条路径上除了vp和vq可以相同外； 其余顶点均不相同，则称此路径为一条简单路径。起 点和终点相同(vp ＝vq )的简单路径称为简单回路或简单 环(Cycle)。例如，在图G2中顶点序列vl ,v2，v3，v4是一 条从顶点vl到顶点v4的长度为3的简单路径；顶点序列 vl ,v2，v4，vl，v3是一条从顶点vl到顶点v3的长度为4的 路径，但不是简单路径；顶点序列vl，v2，v4，vl是一 个长度为3的简单环。在有向图Gl中，顶点序列vl，v2， vl是一个长度为2的有向简单环
在一个有向图中,若存在一个顶点v,从该顶点有路径可以到达图中 其它所有顶点,则称此有向图为有根图,V称作图的根 在无向图G中,若从顶点v到顶点v有路径(当然从v到v也一定有路 径),则称v和v是连通的。若VG中任意两个不同的顶点v和y都 连通即有路径),则称G为连通图 Connected Graph)。例如,图G2 和G3是连通图。 无向图G的极大连通子图称为G的连通分量( connected Component) 显然,任何连通图的连通分量只有一个,即是其自身,而非连通 的无向图有多个连通分量。例如,图7-4中的G是非连通图,它有 两个连通分量H和H2 在有向图G中,若对于v(G中任意两个不同的顶点v和v,都存在 从v到v以及从v到v的路径,则称G是强连通图。有向图G的极大 强连通子图称为G的强连通分量。显然,强连通图只有一个强连 通分量,即是其自身。非强连通的有向图有多个强连通分量。例 如图7-1中的G不是强连通图,因为v3到v2没有路径,但它有两个 强连通分量
在一个有向图中，若存在一个顶点v，从该顶点有路径可以到达图中 其它所有顶点，则称此有向图为有根图，v称作图的根。 在无向图G中，若从顶点vi到顶点vj有路径(当然从vj到vi也一定有路 径)，则称vi和vj是连通的。若V(G)中任意两个不同的顶点vi和vj都 连通(即有路径)，则称G为连通图(Connected Graph)。例如，图G2 和G3是连通图。 无向图G的极大连通子图称为G的连通分量(connected Component)。 显然，任何连通图的连通分量只有一个，即是其自身，而非连通 的无向图有多个连通分量。例如，图7-4中的G4是非连通图，它有 两个连通分量Hl和H2。 在有向图G中，若对于V(G)中任意两个不同的顶点vi和vj，都存在 从vi到vj以及从vj到vi的路径，则称G是强连通图。有向图G的极大 强连通子图称为G的强连通分量。显然，强连通图只有一个强连 通分量，即是其自身。非强连通的有向图有多个强连通分量。例 如图7-1中的Gl不是强连通图，因为v3到v2没有路径，但它有两个 强连通分量
V2 Q V3 V6 Ve V3 若将图的每条边都赋上一个权,则称这种带权图为网 络( Network)。通常权是具有某种意义的数
若将图的每条边都赋上一个权，则称这种带权图为网 络(Network)。通常权是具有某种意义的数
它们可以表示两个顶点∩ 之间的距离,耗费等
它们可以表示两个顶点 之间的距离，耗费等
图的存储结构 邻接矩阵( Adjacency Matrix)是表示顶点之 间相邻关系的矩阵。 设G=(V,E)是具有n 个顶点的图,则G的 ={1若(,)或,>是E(GD中的边 0:若(v,")或不是E(G)中的边 邻接矩阵是具有如下 性质的n阶方阵:
图的存储结构 • 邻接矩阵(Adjacency Matrix)是表示顶点之 间相邻关系的矩阵。 设G＝(V，E)是具有n 个顶点的图，则G的 邻接矩阵是具有如下 性质的n阶方阵： = ：若（ ）或 不是 （ ）中的边 ：若（ ）或 是 （ ）中的边 v v v v E G v v v v E G i j i j i j i j 0 , , 1 , , A i, j
用邻接矩阵表示法表示图,除了存储用于表示顶点间 相邻关系的邻接矩阵外,通常还需要用一个顺序表来 存储顶点信息。其形式说明如下 t define n 6 /*图的顶点数*/ f define e 8 /*图的边(弧)数* typedef char vextype;/*顶点的数据类型*/ typedef float adjtype;/*权值类型*/ typedef struct i vextype vex[n] adjtype arcs]: igraph
• 用邻接矩阵表示法表示图，除了存储用于表示顶点间 相邻关系的邻接矩阵外，通常还需要用一个顺序表来 存储顶点信息。其形式说明如下： • # define n 6 / * 图的顶点数 * / • # define e 8 / * 图的边（弧）数 */ • typedef char vextype； / * 顶点的数据类型 * / • typedef float adjtype； / * 权值类型 * / • typedef struct • {vextype vexs[n]； • adjtype arcs[n][n]； • }graph；
若图中顶点信息是0至n-1的编号,则仅需令权值为1,存储一个邻接矩阵就可以表 示图。若是网络,则 ditype为权的类型。由于无向图或无向网络的邻接矩阵是对 称的,故可采用压缩存储的方法,仅存储下三角阵(不包括对角线上的元素)中的 元素即可。显然,邻接矩阵表示法的空间复杂度S(n)=O(n2)。 CREATGRAPH(ga)/*建立无向网络* Graph Int 1, J, float w for(i=0: ivexs[i]= getchar(;/*读入顶点信息,建立顶点表*/ for(i=0: iarcs[]]=0 /*邻接矩阵初始化*/ for(k=0:karcs[0]=W; ga->arcsIn 3/*CREATGRAPH * 该算法的执行时间是O(n+n2+e),其中O(m2)的时问耗费在邻接矩阵的初始化操作上。 因为e<n2,所以,算法的时间复杂度是Omn2)
• 若图中顶点信息是0至n-1的编号，则仅需令权值为1，存储一个邻接矩阵就可以表 示图。若是网络，则adjtype为权的类型。由于无向图或无向网络的邻接矩阵是对 称的，故可采用压缩存储的方法，仅存储下三角阵(不包括对角线上的元素)中的 元素即可。显然，邻接矩阵表示法的空间复杂度S(n)＝O(n2 )。 • CREATGRAPH(ga) ／* 建立无向网络 * ／ • Graph * ga； • { • int i，j，k； • float w； • for(i＝0；i＜n；i++) • ga ->vexs[i]＝getchar()；／* 读入顶点信息，建立顶点表 *／ • for(i＝0；i＜n；i++) • for(j＝0；j＜n；j++) • ga ->arcs[i][j]＝0； ／* 邻接矩阵初始化*／ • for(k＝0；k＜e；k++) ／* 读入e条边 *／ • (scanf(”％d％d％f”，&I,&j，&w)；／*读入边(vi，vj )上的权w *／ • ga ->arcs[i][j]＝w； • ga - >arcs[j][i]＝w； • } • }／*CREATGRAPH *／ • 该算法的执行时间是O(n+n2+e)，其中O(n2 )的时问耗费在邻接矩阵的初始化操作上。 因为e＜n 2，所以，算法的时间复杂度是O(n2 )