首页 > 代码库 > 数据结构（八）图
数据结构（八）图
定义
定义解释
下图就是一张典型的图
图术语定义
无向边：若顶点vi到vj之间的边没有方向，则称这条边为无向边，用无序偶对(vi,vj)来表示
无向图：图内任意两个顶点之间的边都没有方向
有向边：顶点vi到vj的边有方向，也称为弧，用有序偶<vi,vj>表示，vi表示弧尾，vj表示弧头
有向图：图内任意两个顶点之间的边都是有向边
无向完全图：在无向图中，任意两个顶点之间都存在边。完全图有Cn2条边
有向完全图：在有向图中，任意两个顶点都存在互为相反的两条弧
子图：假设两个图 G=(V,{E}) 和 G‘=(V‘,{E‘})，如果 V’ 属于 V 并且 E‘ 属于 E，则称 G’ 为 G 的子图
无向图顶点的度：和顶点关联边的数目
有向图 入度：顶点为头的弧的数目
有向图 出度：顶点为尾的弧的数目
注意
连通图术语
定义
连通分量：无向图中的极大连通子图
连通分量特点：
图的存储结构
1.邻接矩阵
带权的图（网）
不适用于边数相对于顶点数较少的图
2.邻接表
数组和链表相结合，数组存放顶点，链表记录顶点之间的边或弧
对于有向图，有时候会采用逆邻接表，为了更直观得到入度信息
十字链表
把邻接表和逆邻接表结合起来
例如
看图可能有点乱，其实边表结构就是存放了[弧头，弧尾，指向下一个弧头，指向下一个弧尾]，结构交叉，故名为十字链表
邻接多重链表
十字链表关注的是有向图，邻接多重链表关注的是无向图，参考十字链表的边表结构
边集数组
边信息数组
例如
图的遍历
定义
从图中某一个顶点出发遍历其余顶点，且每个顶点只被遍历到一次，这一过程就叫做图的遍历
深度优先遍历（DFS depth first search）
类似树的先序遍历方法
广度优先遍历（BFS breadth first search）
类似树的层序遍历
时间复杂度和深度优先遍历是一样的
最小生成树
构造连通网的最小代价生成树称为最小生成树
如何在图中找到最小生成树呢
普里姆算法和克鲁斯卡尔算法
普利姆算法（prim）
时间复杂度为O(n2)
克鲁斯卡尔（kruskal）
时间复杂度为O(eloge)
最短路径
迪杰斯特拉算法（Dijkstra）
时间复杂度O(n三次方)
费罗伊德算法（Flovd）
时间复杂度O(n三次方)
总结
以顺序表和链表两种表为基础，针对有向图和无向图的存储结构
数据结构（八）图
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。