什么是图
表示“多对多”的关系 包含
一组顶点：通常用V (Vertex) 表示顶点集合一组边：通常用E (Edge) 表示边的集合
边是顶点对：
(
v
,
w
)
∈
E
(v, w) \in\mathbb E
(v,w)∈E，其中
v
,
w
∈
V
v, w \in\mathbb V
v,w∈V有向边< v, w> 表示从v指向w的边（单行线）不考虑重边和自回路
抽象数据类型定义
类型名：图（Graph） 数据对象集：G(V,E)由一个非空的有限顶点集合V和一个有限边集合E组成（顶点不为空，边可以为空）。 操作集：对于任意图
G
∈
G
r
a
p
h
G\in\mathbb Graph
G∈Graph，以及
v
∈
V
v\in\mathbb V
v∈V,
e
∈
E
e\in\mathbb E
e∈E
Graph Create()：建立并返回空图；Graph InsertVertex(Graph G, Vertex v)：将v插入G；Graph InsertEdge(Graph G, Edge e)：将e插入G；void DFS(Graph G, Vertex v)：从顶点v出发深度优先遍历图G；void BFS(Graph G, Vertex v)：从顶点v出发宽度优先遍历图G；void ShortestPath(Graph G, Vertex v, int Dist[])：计算图G中顶点v到任意其他顶点的最短距离；void MST(Graph G)：计算图G的最小生成树；
常用术语
网络：就是边上有权值的图
怎么在程序中表示一个图
1、邻接矩阵
问题：对于无向图的存储，怎样可以省一半空间？ 用一个长度为N(N+1)/2的1维数组A存储{G00,G10,G11,……,G(n-1)0,…,G(n-1)(n-1)}， 则Gij在A中对应的下标是：
( i*(i+1)/2 + j )
对于网络，只要把G[i][j]的值定义为边 <vi,vj>的权重即可。
邻接矩阵优点
直观、简单、好理解 方便检查任意一对顶点间是否存在边 方便找任一顶点的所有“邻接点”（有边直接相连的顶点） 方便计算任一顶点的“度”（从该点发出的边数为“出度”，指向该点的边数为“入度”）
无向图：对应行（或列）非0元素的个数有向图：对应行非0元素的个数是“出度”；对应列非0元素的个数是“入度”
邻接矩阵缺点
浪费空间—— 存稀疏图（点很多而边很少）有大量无效元素
对稠密图（特别是完全图）还是很合算的 浪费时间—— 统计稀疏图中一共有多少条边
2、邻接表
邻接表优缺点
方便找任一顶点的所有“邻接点” 节约稀疏图的空间
需要N个头指针+ 2E个结点（每个结点至少2个域） 方便计算任一顶点的“度”？
对无向图：是的对有向图：只能计算“出度”；需要构造“逆邻接表”（存指向自己的边）来方便计算“入度” 不能检查任意一对顶点间是否存在边
