当前位置:   article > 正文

数据结构——图(C语言)_c语言图

c语言图

目录

1.图的基本概念

 2.图的相关定义

 3.图的顶点与边之间的关系

 4.连通图

 5.图的存储结构

(1).邻接矩阵(无向图)

 (2).邻接矩阵(有向图)

(3).邻接矩阵(网)

 


1.图的基本概念

(Graph)是由顶点的有穷非空集合和顶点之间的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。

 注意:在图中数据元素叫做“顶点”;任意两个顶点之间都可能有关系,顶点之间的逻辑关系用“边”来表示,边集可以是空的(只有顶点),但是顶点集合一般要求有穷非空。


 

 2.图的相关定义

  • 无向边:若顶点Vi到Vj之间的边没有方向。则称这条边为无向边(Edge),用无序偶(Vi,Vj)来表示。

G1

 如上图G1是一个无向图,G1={V1,E1},其中

—V1={A,B,C,D};

—E1={(A,B),(B,C),(C,D),(D,A),(A,C)}

  • 有向边:若从顶点Vi到Vj的边有方向,则称这条边为有向边,也称为弧(Arc),用有序偶<Vi,Vj>来表示,Vi称为弧尾,Vj称为弧头。
G2

 上图G2是一个有向图,G2={V2,E2},其中

—V2={A,B,C,D},

—E2={<B,A>,<B,C>,<C,A>,<A,D>}

  • 简单图:在图结构中,若不存在顶点到其自身的边,且同一条边不重复出现,则称这样的图为简单图。以下两个则不属于简单图:

  •  无向完全图:在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图。含有n个顶点的无向完全图有n*(n-1)/2条边。如下图:

  •  有向完全图:在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图。含有n个顶点的有向完全图有n*(n-1)条边。如下图:

  •  稀疏图和稠密图:这里的稀疏和稠密是有些模糊的概念,都是相对而言的,通常认为边或弧数小于n*logn(n是顶点个数)的图称为稀疏图,反之称为稠密图。
  • 带权的图:有些图的边或弧带有与它相关的数字,这种与图的边或弧相关的数叫做(Weight),带权的图通常称为网(Network)。 如下图:

  •  子图:假设有两个图G1=(V1,E1)和G2=(V2,E2),如果V2⊆V1,E2⊆E1,则称G2为G1的子图(Subgraph)。

 

 3.图的顶点与边之间的关系

  • 邻接点:对于无向图G=(V,E),如果边(V1,V1)∈E,则称顶点V1和V2互为邻接点(Adjacent),即V1和V2相邻接。边(V1,V2)依附于顶点V1和V2,或者说(V1,V2)与顶点V1和V2相关联。对于有向图G=(V,E),如果有<V1,V2>∈E,则称顶点V1邻接到顶点V2,顶点V2邻接自顶点V1。
  • 度(Degree):顶点V的度是和V相关联的边的数目,记为TD(V),如下图,顶点A与B互为邻接点,边(A,B)依附于顶点A与B上,顶点A的度为3。

  •  入度、出度:以顶点V为头的弧的数目称为V的入度(InDegree),记为ID(V),以V为尾的弧的数目称为V的出度(OutDegree),记为OD(V),因此顶点V的度为:TD(V)=ID(V)+OD(V)。如下图顶点A的入度是2,出度是1,所以顶点A的度是3。

     
  •  路径的长度是路径上的边或弧的数目。
  • 第一个顶点到最后一个顶点相同的路径称为回路或环(Cycle)。
  • 序列中顶点不重复出现的路径称为简单路径,除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路,称为简单回路或简单环。如下图,左侧是简单环,右侧不是简单环。

 


 

 4.连通图

定义:在无向图G中,如果从顶点V1到顶点V2有路径,则称V1和V2是连通的,如果对于图中任意两个顶点Vi和Vj都是连通的,则称G是连通图。如下图,左侧不是连通图,右侧是连通图:

连通分量:无向图中的极大连通子图称为连通分量。

注意:首先要是子图,并且子图是要连通的;连通子图含有极大顶点数;具有极大顶点数的连通子图包含依附于这些顶点的所有边。

 强连通图:在有向图中,如果对于每一对Vi到Vj都存在路径,则称G是强连通图。

强连通分量:有向图中的极大强连通子图称为有向图的强连通分量。下图中右侧是强连通图,左侧不是。并且右侧是左侧的极大强连通子图,也是左侧的强连通分量。


 

 5.图的存储结构

(1).邻接矩阵(无向图)

图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。

顶点数组:V0V1V2V3
V0V1V2V3
V00111
V11010
V21101
V31010

 如上,我们设置了两个数组,顶点数组为vertex[4]={V0,V1,V2,V3},边数组arc[4][4]为对称矩阵(0表示不存在顶点间的边,1表示顶点间存在边)。

上面第二个表是以对角线为对称轴的对称表,由此我们引入了对称矩阵的概念:所谓对称矩阵就是n阶矩阵的元满足a[i][j]=a[j][i](0<=i,j<=n)。即从矩阵的左上角到右下角的主对角线为轴,右上角的元与左下角对应的元全都是相等的。

从这个二维数组组成的对称矩阵我们可以很容易的知道图中的信息:根据0或1来判定任意两个顶点之间是否有边;某个顶点的就是这个顶点Vi在邻接矩阵中第i行(或第i列)的元素之和;求顶点Vi的所有邻接点就是将矩阵中第i行元素扫描一遍,arc[i][j]为1的就是邻接点。

 (2).邻接矩阵(有向图)

无向图的边构成了一个对称矩阵,看起来浪费了一半的空间,那如果我们是存放有向图会怎样呢?

顶点数组:V0V1V2V3
V0V1V2V3
V00001
V11010
V21100
V30000

 可见顶点数组vertex[4]={V0,V1,V2,V3},弧数组arc[4][4]也是一个矩阵,但因为是有向图,所以这个矩阵并不对称,例如由V1到V0有弧,的到arc[1][0]=1,而V0到V1没有弧,因此arc[0][1]=0。

 有向图要考虑入度和出度,顶点V1的入度为1,正好是第V1列的各数之和,顶点V1的出度为2,正好是第V2行的各数之和

(3).邻接矩阵(网)

 在图的定义中我们提到了网这个概念,事实上也就是每条边上都带有权的图叫做网。

顶点数组:V0V1V2V3
V0V1V2V3
V0018
V1802
V240
V30

 这里的“∞”表示一个计算机允许的,大于所有边上权值的值。

 

 征战尚未结束,你我仍需努力!

后续更精彩~~

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/寸_铁/article/detail/814171
推荐阅读
相关标签
  

闽ICP备14008679号