数据结构与算法(C语言) |
您所在的位置:网站首页 › 平凡图的定义和分类方法 › 数据结构与算法(C语言) |
•图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。 •注意的地方: –线性表中我们把数据元素叫元素,树中叫结点,在图中数据元素我们则称之为顶点(Vertex)。 –线性表可以没有数据元素,称为空表,树中可以没有结点,叫做空树,而图结构在咱国内大部分的教材中强调顶点集合V要有穷非空。 –线性表中,相邻的数据元素之间具有线性关系,树结构中,相邻两层的结点具有层次关系,而图结构中,任意两个顶点之间都可能有关系,顶点之间的逻辑关系用边来表示,边集可以是空的。
无向边:若顶点Vi到Vj之间的边没有方向,则称这条边为无向边(Edge),用无序偶(Vi,Vj)来表示 是一个无向图 G1= (V1, E1) V1={ A, B, C, D, E, F } E1={ (A, B), (A, E), (B, E), (B, F), (C, D), (C, F), (D, F) } 有向边:若从顶点Vi到Vj的边有方向,则称这条边为有向边,也成为弧(Arc),用有序偶来表示,Vi称为弧尾,Vj称为弧头。
•上图G2是一个有向图,G2={V2,E2},其中 –V2={A,B,C,D}, –E2={,,,}
简单图:在图结构中,若不存在顶点到其自身的边,且同一条边不重复出现,则称这样的图为简单图。 无向完全图:在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图。含有n个顶点的无向完全图有n*(n-1)/2条边。
有向完全图:在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图。含有n个顶点的有向完全图有n*(n-1)条边。 通常认为边或弧数小于n*logn(n是顶点的个数)的图称为稀疏图,反之称为稠密图。 有些图的边或弧带有与它相关的数字,这种与图的边或弧相关的数叫做权(Weight),带权的图通常称为网(Network)。
图的顶点与边之间的关系 对于无向图G=(V,E),如果边(V1,V2)∈E,则称顶点V1和V2互为邻接点(Adjacent),即V1和V2相邻接。边(V1,V2)依附(incident)于顶点V1和V2,或者说边(V1,V2)与顶点V1和V2相关联。 顶点V的度(Degree)是和V相关联的边的数目,记为TD(V),如下图,顶点A与B互为邻接点,边(A,B)依附于顶点A与B上,顶点A的度为3。
对于有向图G=(V,E),如果有∈E,则称顶点V1邻接到顶点V2,顶点V2邻接自顶点V1。 以顶点V为头的弧的数目称为V的入度(InDegree),记为ID(V),以V为尾的弧的数目称为V的出度(OutDegree),记为OD(V),因此顶点V的度为TD(V)=ID(V)+OD(V)。 下图顶点A的入度是2,出度是1,所以顶点A的度是3。 连通图 在无向图G中,如果从顶点V1到顶点V2有路径,则称V1和V2是连通的,如果对于图中任意两个顶点Vi和Vj都是连通的,则称G是连通图。 下图中左侧不是连通图,右侧是连通图。 无向图中的极大连通子图称为连通分量。 注意以下概念: –首先要是子图,并且子图是要连通的; –连通子图含有极大顶点数; –具有极大顶点数的连通子图包含依附于这些顶点的所有边。
在有向图G中,如果对于每一对Vi到Vj都存在路径,则称G是强连通图。 有向图中的极大强连通子图称为有向图的强连通分量。 下图左侧并不是强连通图,右侧是。并且右侧是左侧的极大强连通子图,也是左侧的强连通分量。
一个连通图的生成树是一个极小的连通子图,它含有图中全部的n个顶点,但只有足以构成一棵树的n-1条边。 如果一个有向图恰有一个顶点入度为0,其余顶点的入度均为1,则是一棵有向树。
图的存储结构 (一)邻接矩阵 ——邻接矩阵(无向图) 图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。
设置两个数组,顶点数组为vertex[4]={V0,V1,V2,V3},边数组arc[4][4]为对称矩阵(0表示不存在顶点间的边,1表示顶点间存在边)。 对称矩阵:所谓对称矩阵就是n阶矩阵的元满足a[i][j]=a[j][i](0 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |