怎么在别人网站上做锚文本链接,建境模型,广告设计需要学什么软件,路由 拦截 网站开发对于下面的内容#xff0c;大家着重观察和理解图即可#xff0c;可以直接绕过一些文字性的概念#xff0c;对图有一个大概的认识。 图 简单认识图图的定义有向图和无向图完全图无向完全图有向完全图 图的基本存储结构邻接矩阵存储邻接矩阵的优点 网络的邻接矩阵邻接表无向图… 对于下面的内容大家着重观察和理解图即可可以直接绕过一些文字性的概念对图有一个大概的认识。 图 简单认识图图的定义有向图和无向图完全图无向完全图有向完全图 图的基本存储结构邻接矩阵存储邻接矩阵的优点 网络的邻接矩阵邻接表无向图的邻接表有向图的邻接表关于顶点的度、出度与入度 简单认识图
图是一种比树更为复杂的数据结构。树的节点之间是一对多的关系并且存在父与子的层级划分而图的顶点注意这里不叫节点之间是多对多的关系并且所有顶点都是平等的无所谓谁是父谁是子。 图的定义
图 是由一个非空的顶点集合和一个描述顶点之间多对多关系的边或弧集合组成的一种数据结构它可以形式化地表示为 图VE
其中V{x|x∈某个数据对象集}它是顶点的有穷非空集合E{xy|xy∈V}或E{xy|xy∈V且Pxy}它是顶点之间关系的有穷集合也叫做边集合Pxy表示从x到y的一条单向通路。
有向图和无向图
若图G中的每条边都是有方向的则称G为有向图。在有向图中一条有向边是由两个顶点组成的有序对有序对通常用尖括号表示。例如有序对vivj表示一条由vi到vj的有向边。有向边又称为弧弧的始点称为弧尾弧的终点称为弧头。若图G中的每条边都是没有方向的则称G为无向图。无向图中的边均是顶点的无序对无序对通常用圆括号表示。
下面我们举例说明 ①如下图所示顶点集合V(G1){ V 0 , V 1 , V 2 , V 3 , V 4 V_0,V_1,V_2,V_3,V_4 V0,V1,V2,V3,V4} 边集合为E(G1){ ( V 0 , V 1 ) , ( V 0 , V 3 ) , ( V 1 , V 2 ) , ( V 1 , V 4 ) , ( V 2 , V 3 ) , ( V 2 , V 4 ) (V_0,V_1),(V_0,V_3),(V_1,V_2),(V_1,V_4),(V_2,V_3),(V_2,V_4) (V0,V1),(V0,V3),(V1,V2),(V1,V4),(V2,V3),(V2,V4)} ②如下图所示顶点集合V(G2){ V 0 , V 1 , V 2 , V 3 V_0,V_1,V_2,V_3 V0,V1,V2,V3} 边集合为E(G2){ V 0 , V 1 , V 0 , V 2 , V 2 , V 3 , V 3 , V 0 V_0,V_1,V_0,V_2,V_2,V_3,V_3,V_0 V0,V1,V0,V2,V2,V3,V3,V0} 完全图
简单来说完全图具有最多的边数任意一对顶点间均有边相连。
无向完全图
对于具有n个顶点的完全图如果每两个顶点之间都有相连也就是边数为 e ( n − 1 ) ( n − 2 ) . . . 1 (n-1)(n-2)...1 (n−1)(n−2)...1 n ( n − 1 ) 2 \frac{n(n-1)}{2} 2n(n−1)就是完全图否则就是不完全图。 如下图所示即为无向完全图。
有向完全图
对于具有n个顶点的完全图如果每两个顶点之间都有相连也就是边数为n(n-1),那么即为有向完全图。 如下图所示即为有向完全图。
图的基本存储结构
图的存储结构至少要保存两类信息 1)顶点的数据 2)顶点间的关系
邻接矩阵存储
给定图GVE其中VG{v0…vi…vn-1}G的邻接矩阵Adacency Matrix是具有如下性质的n阶方阵 下面我们举例说明 写出如下两个图的邻接矩阵。 所以它的邻接矩阵为 我们可以观察得知无向图的邻接矩阵是对称的有向图的邻接矩阵可能是不对称的。 所以它的邻接矩阵为
邻接矩阵的优点
邻接矩阵的优点在于用邻接矩阵表示图很容易判定任意两个顶点之间是否有边相连并求得各个顶点的度数。 对于无向图顶点vi的度数是邻接矩阵中第i行或第i列值为1的元素个数。 对于有向图邻接矩阵中第i行值为1的元素个数为顶点vi的出度第i列值为1的元素的个数为顶点vi的入度。
网络的邻接矩阵
当GVE是一个网络时G的邻接矩阵是具有如下性质的n阶方阵 其中Wij表示边上的权值∞表示一个计算机允许的、大于所有边上权值的数。 下面我们举例说明 ①对于如下这个无向图求邻接矩阵 它的邻接矩阵为 ②对于如下这个有向图求邻接矩阵 它的邻接矩阵为
邻接表
如上可以知道邻接矩阵可以直观地看出一个顶点和另一个顶点之间的关联关系。 但是邻接矩阵的缺点时什么呢就是占用太多空间了。 举个例子来说如果有100个顶点这100个顶点之间只有10个顶点之间有关联关系那么就需要建立一个100×100的矩阵在这个邻接矩阵中就只有10或20个1其余都是0这样的矩阵也叫做 稀疏矩阵太浪费存储空间了。 所以为了解决邻接矩阵占用空间的问题人们想到了另一中种图的表示方法邻接表。
无向图的邻接表
对于图G中的每个顶点vi该方法把所有邻接于vi的顶点vj链成一个带头结点的单链表这个单链表就称为顶点vi的邻接表。 单链表中的每个结点至少包含两个域一个为邻接点域adjvex它指示与顶点vi邻接的顶点在图中的位序另一个为链域next它指示与顶点vi邻接的下一个结点。
如下图所示 简单理解单链表的组成 其实可以将图的单链表理解成由一个又一个“带头结点的单链表”组成的。 当然严谨来说肯定不是单链表。这是因为它的表头结点结构和边表结点的结构不同。
它的邻接表为
有向图的邻接表
对于有向图来说如果每一顶点vi的邻接表中每个表结点都存储以vi的为始点射出的一条边则称这种表为有向图的出边表有向图的邻接表反之若每一顶点vi的邻接表中每个表结点都对应于以vi为终点的边即射入vi的边则称这种表为有向图的入边表又称逆邻接表。 举例如下图所示 它的出边表
关于顶点的度、出度与入度
在无向图的邻接表中顶点vi的度为第i个链表中结点的个数而在有向图的出边表中第i个链表中的结点个数是顶点vi的出度为了求入度必须对整个邻接表扫描一遍所有链表中其邻接点域的值为i的结点的个数是顶点vi的入度。
若如下图所示已知该图是无向图则可知改图种V0的度为3. 若如下图所示已知改图是有向图则可知 V0的出度为1V0的入度为2。
