湖南城乡建设部网站,移动开发应用,商务网站建设服务商,二季域名做网站有向图#xff1a;图中的每条边都有方向的图叫有向图。此时#xff0c;边的两个顶点有次序关系#xff0c;有向边 u,v成为从顶点u到顶点v的一条弧#xff0c;u成为弧尾#xff08;始点#xff09;#xff0c;v成为弧头#xff08;终点#xff09;#xff0c…有向图图中的每条边都有方向的图叫有向图。此时边的两个顶点有次序关系有向边 u,v成为从顶点u到顶点v的一条弧u成为弧尾始点v成为弧头终点即有向图中弧 u,v和弧 v,u 表示不同的两条边。
无向图图中的每条边没有方向的图。边的两个顶点没有次序关系无向图用边(u,v)表示对称弧 u,v和 v,u。
权图中的边或弧上有附加的数量信息这种可反映边或弧的某种特征的数据成为权。
网图上的边或弧带权则称为网。可分为有向网和无向网。
邻接和关联若边e(u,v)或弧e u,v则称点u和v互为邻接顶点并称边e或弧e关联于顶点u和v。
度在无向图中与顶点v关联的边的条数成为顶点v的度。有向图中则以顶点v为弧尾的弧的条数成为顶点v的出度以顶点v为弧头的弧的条数成为顶点v的入度而顶点v的度出度入度。图中各点度数之和是边或弧的条数的2倍。
圈图中联接同一个顶点的边叫圈。
平行边图中两个顶点之间若有两条或两条以上的边称这些边为平行边。
简单图没有圈也没有平行边的图。
有向完全图有n个顶点n(n-1)条弧的有向图。每两个顶点之间都有两条方向相反的边连接的图。
完全图有n个顶点n(n-1)/2条边的无向图。若一个图的每一对不同顶点恰有一条边相连则称为完全图。完全图是每对顶点之间都恰连有一条边的简单图。
路径长度路径上边或弧的数目。若路径上的各顶点均不相同则称这条路经为简单路经或路除第一个和最后一个顶点相同外其他各顶点均不相同的路径成为回路或环。
连通图在无向图G中对与图中的任意两个顶点u、v都是连通的则称图G为连通图。
强连通图在有向图G中如果对于每一对Vi和Vj 属于顶点集VVi不等于Vj 从Vi到Vj和从Vj到Vi都存在路径则称G是强连通图。
强连通分量有向图中的极大强连通子图称做有向图的强连通分量。
生成树一个连通图的生成树是一个极小的连通子图它含有图中全部的n个顶点但只有足以构成一棵树的n-1条边。
有向树如果一个有向图恰有一个顶点的入度为0其余顶点的入度为1则是一棵有向树。
图的存储结构
图的存储结构常用的是”邻接矩阵”和”邻接表”。
邻接矩阵
邻接矩阵是指用矩阵来表示图。它是采用矩阵来描述图中顶点之间的关系(及弧或边的权)。 假设图中顶点数为n则邻接矩阵定义为 下面通过示意图来进行解释。 图中的G1是无向图和它对应的邻接矩阵。 图中的G2是无向图和它对应的邻接矩阵。
通常采用两个数组来实现邻接矩阵一个一维数组用来保存顶点信息一个二维数组来用保存边的信息。 邻接矩阵的缺点就是比较耗费空间。
邻接表
邻接表是图的一种链式存储表示方法。它是改进后的”邻接矩阵”它的缺点是不方便判断两个顶点之间是否有边但是相对邻接矩阵来说更省空间。 图中的G1是无向图和它对应的邻接矩阵。 图中的G2是无向图和它对应的邻接矩阵。
图的python实现
在Python中图主要是通过列表和词典来构造。
实现的功能
寻找一条路径查找所有的路径查找最短路径 图的表示A -- BA -- CB -- CB -- DC -- DD -- CE -- FF -- C
#找一条路
def find_path(graph,start,end,path[]):path path [start]if start end:return pathif start not in graph.keys():return Nonefor node in graph[start]:if node not in path:newpath find_path(graph,node,end,path)if newpath:return newpathreturn path
if __name__ __main__:graph {A: [B, C],B: [C, D],C: [D],D: [C],E: [F],F: [C]}print(find_path(graph,A,D))
