顶点与边（弧）之间数量的关系 设n为顶点数，e为边或弧的条数 对无向图有：0<=e<=n(n-1)/2 有向图有：0<=e<=n(n-1)
完全图：
边达到最大的图
? 无向完全图：边数为n(n-1)/2的无向图 ? 有向完全图：弧数为n(n-1)的有向图
权：与图的边或弧相关的数 网：边或弧上带有权值的图
顶点的度
无向图：为依附于顶点V的边数
有向图：等于以顶点V为弧头的弧数（称为V的 入度，记 为ID（V））与以顶点V为弧尾的弧数（称为V 的出度，记为OD（V））之和。即： TD（V）=ID（V）+OD（V）
路径：
无向图：顶点v到v’的路径是一个顶点序列（ v=vi0, vi1, … , vim=v’ ） 其中，（vij-1,vij ）∈E, 1<=j<=m
有向图： 顶点v 到v’的路径是有向的顶点序列（v=vi0, vi1, … , vim=v’） 其中，
路径长度：路径上边或弧的数目
回路或环：首尾顶点相同的路径，称为回路或环。即： （v=vi0, vi1, … , vim=v） 简单路径：路径中不含相同顶点的路径
简单回路：除首尾顶点外，路径中不含相同顶点的回路
顶点连通：若顶点v到顶点v’有路径，则称顶点v与v’是连通的 连通图：包括无向连通图和有向连通图
无向图：若图中任意两个顶点vi,vj都是连通的，则称该图是连通图(vi<>vj) 有向图：若图中任意两个顶点vi,vj，都存在从vi到vj和从 vj到vi的路径，则称该有向图为强连通图(vi<>vj) 连通分量：
无向图：无向图中极大连通子图，称为连通分量
有向图：有向图中极大强连通子图，称为强连通分量
子图是图的一部分，它本身也是一 个图。如果有图G=(V，E)和G′=(V′,E′)， 且V′是V的子集，E′是E的子集，则称G′ 是G的子图。
邻接顶点 在无向图中，若两个顶点之间有边连接，则这两个顶点互为邻接顶点
图的邻接矩阵和邻接表的存储表示
设图G=（V，{E}）有n个顶点，则G的邻接矩阵定义为n阶方阵A。 其中：
??1 若(vi,vj)或?vi,vj?是图G的边A[i,j]????0 若(vi,vj)或?vi,vj?不是图的边
特点：判定两个顶点Vi与Vj是否关联,只需判A[i,j]是否为1 顶点的度容易求得:
? 无向图中：TD(Vi)=∑A[i,j]=∑A[j,i] j=1 j=1 即顶点Vi的度等于邻接矩阵中第i行（或第i列）的元素之和（非0元素个数之和）。
? 有向图中： TD(Vi)=OD(Vi)+ID(Vi) n n
= ∑A[i,j]+∑A[j,i] j=1 j=1
即顶点Vi的出度为邻接矩阵中第i行元素之和 顶点Vi的入度为邻接矩阵中第i列元素之和
如果G是带权的图，wij是边（vi,vj）或
?Wij 若（vi,vj）或?vi,vj?是图G的边(i?j) ?A[i,j]??? 若（vi,vj）或?vi,vj?不是图G的边(i?j) ??0 所有对角线元素?i?j? V1
579V20 5 ∞ 7 ∞ ∞4V338∞ 0 4 ∞ ∞ ∞8 ∞ 0 ∞ ∞ 9∞ ∞ 5 0 ∞ 6V61V565∞ ∞ ∞ 5 0 ∞3 ∞ ∞ ∞ 1 05V4（a) 网图4.9 网及其邻接矩阵(b) 邻接矩阵
邻接表（adjacency list） 无向图邻接表
无向图的邻接表
有向图的邻接表
与无向图的邻接表结构一样。只是在第i条链表上的结点是以Vi为 弧尾的各个弧头顶点
图的深度优先和广度优先遍历
深度优先遍历：