第6章图 本章中介绍下列主要内容: ●图的定义 ●图的存储结构 ●图的遍历操作 ●图的几个典型问题 请单赤鼠标左键换页! 退出
第6章 图 本章中介绍下列主要内容： ⚫ 图的定义 ⚫ 图的存储结构 ⚫ 图的遍历操作 ⚫ 图的几个典型问题 退出
6.1图的定义 6.2图的存值结构 6.3图的遍历 6.4最小生成树问题 6.5拓扑序问题 请单赤鼠标左键换页!
6.1 图的定义 6.2 图的存储结构 6.3 图的遍历 6.4 最小生成树问题 6.5 拓扑排序问题
6.1图的定义 6.1.1定义 图是由结点的有穷集合V和边的集合E组成。其中, 为了与树形结构加以区别,在图结构中常常将结点称 为顶点,边是顶点的有序偶对,若两个顶点之间存在 条边,就表示这两个顶点具有相邻关系。 请单鼠标左键换页!
6.1 图的定义 6.1.1 定义 图是由结点的有穷集合V和边的集合E组成。其中， 为了与树形结构加以区别，在图结构中常常将结点称 为顶点，边是顶点的有序偶对，若两个顶点之间存在 一条边，就表示这两个顶点具有相邻关系
v 4-(w> 图6-1 请单鼠标左键换页!
图 6 - 1 (a) (b)
在上面两个图结构中,一个是有向图,即每条 边都有方向,另一个是无向图,即每条边都没有方 向 在有向图中,通常将边称作弧,含箭头的一端 称为弧头,另一端称为弧尾,记作<vv,它表示 从顶点v到顶点v有一条边 若有向图中有n个顶点,则最多有m(n-1)条弧, 我们又将具有n(n-1)条弧的有向图称作有向完全图 以顶点v为弧尾的弧的数目称作顶点v的出度, 以顶点v为弧头的弧的数目称作顶点v的入度 在无向图中,边记作(vy),它蕴涵着存在< y≥和<vpv>两条弧。若无向图中有n个顶点,则 最多有n(n-)2条边,我们又将具有n(n-1)/2条边的 无向图称作无向完全图 请单赤鼠标左键换页!
在上面两个图结构中，一个是有向图，即每条 边都有方向，另一个是无向图，即每条边都没有方 向。 在有向图中，通常将边称作弧，含箭头的一端 称为弧头，另一端称为弧尾，记作<vi ,vj>，它表示 从顶点vi到顶点vj有一条边。 若有向图中有n个顶点，则最多有n(n-1)条弧， 我们又将具有n(n-1)条弧的有向图称作有向完全图。 以顶点v为弧尾的弧的数目称作顶点v的出度， 以顶点v为弧头的弧的数目称作顶点v的入度。 在无向图中，边记作(vi ,vj )，它蕴涵着存在< vi ,vj>和<vj ,vi>两条弧。若无向图中有n个顶点，则 最多有n(n-1)/2条边，我们又将具有n(n-1)/2条边的 无向图称作无向完全图