首页  

数据结构图基础     所属分类 DS 浏览量 69
图(graph) 顶点(vertex) 边/弧(edge) 
G=(V,E)

边是否有方向 分为 无向图和有向图
V={A,B,C,D,E,F} 
E={(A,B),(A,C),(B,C),(B,E),(B,F),(C,F), (C,D),(E,F),(C,E)}

(A,B) 无向
< A , B > 有向 A到B的有向边

邻接点
一条边上的两个顶点叫做邻接点

入边 和 出边
顶点的入边  以该顶点为终点的边
顶点的出边  以该顶点为起点的边

入度 出度
路径和回路

路径  
路径长度  路径中边的数量
简单路径  一条路径上顶点不重复出现 
回路     路径的第一个顶点和最后一个顶点相同 
简单回路  第一个顶点和最后一个顶点相同,其它各顶点都不重复的回路 


连通图和连通分量

连通图
对无向图,任意两个顶点之间都存在一条无向路径,则称该无向图为连通图
对有向图,若图中任意两个顶点之间都存在一条有向路径,则称该有向图为强连通图
连通分量  非连通图中的各个连通子图称为该图的连通分量

权  
带权的图

图的存储结构
邻接矩阵
邻接表

通常采用两个数组来实现邻接矩阵
一个一维数组用来保存顶点信息
一个二维数组来用保存边的信息
邻接矩阵比较耗费空间

邻接表是图的一种链式存储表示方法
它是改进后的"邻接矩阵"
缺点是不方便判断两个顶点之间是否有边,但是相对邻接矩阵更省空间

上一篇     下一篇
数据结构之树

算法导论第二版中文目录

《算法图解》笔记

数据结构之树的性质

常用数据结构

概率论词汇