2 1
4 3 G2
5 6
4
6.1 图的基本概念
本章只讨论简单图,即有两类图形不在本章讨论之列：
5
6.1 图的基本概念
(无向)完全图(Completed graph) : n个顶点的有n(n-1)/2条边的简单无向图. 有向完全图:
n个顶点的有n(n-1)条弧的简单有向图.
稀疏图(sparse graph)： 边或弧很少的图，通常边数e<nlog2n 稠密图(Dense graph): 无向图中，边数接近n(n-1)/2 ； 有向图中，弧数接近n(n-1)
3
6.1 图的基本概念
例1 图G1：
V(G1)={1,2,3,4,5,6,7} E(G1)={(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)}
例2 图G2：
1
5
7
3
2 G1
4
6
V(G2)={1,2,3,4,5,6} E(G2)={<1,2>, <2,1>, <2,3>, <2,4>, <3,5>, <5,6>, <6,3>}
用邻接表表示无向图时，需要 n 个顶点结点，2e 个边结点。
有向图的邻接表和逆邻接表 在有向图的邻接表中，第i个单链表链接的弧 都是顶点Vi发出的。也称做出边表。 在有向图的逆邻接表中，第i个单链表链接的弧 都是进入顶点Vi的。也称做入边表。
v1 v2 0 1 2 3 邻接表(出边表)
V1 V2 ^ V3 V4 2 3 ^ 0 ^ 1 ^
// 得到图G中顶点v的值
// 确定图G中顶点出v的第一个邻接点
