什么是图
定义
包含
- 1. 一组顶点：通常用V(Vertex)表示顶点集合
- 2. 一组边：通常用E(Edge)表示边的集合
- 1. 边是顶点对：(v,w)属于E，其中v,w属于V
- 2. 有向边<v,w>表示从v指
- 3.不考虑重边和自回路
抽象数据类型定义
- 1.类型名称：图(Graph)
- 2. 数据对象集：G(V,E)由一个非空的有限顶点集合V和一个有限边集合E组成(可以一条边都没有，但不 能一个顶点都没有)
- 3. 操作集：对于任意图G属于Graph，以及v属于V，e属于E
1. Graph Create()：建立并返回空图
2. Graph InsertVertex(Graph G, Vertex v)：将v插入G
3. Graph InsertEdge(Graph G, Edge e)：将e插入G;
4. void DFS(Graph G,Vertex v)：从顶点v出发深度优先遍历图G;
5. void BFS(Graph G,Vertex v)：从顶点v出发宽度优先遍历图G;
6. void ShortestPath(Graph G,Vertex v,int Dist[])：计算图G中顶点v到任意其他
顶点的最短距离
7. void MST(Graph G)：计算图G的最小生成树
常见术语
- 无向图：无所谓方向的
- 有向图：在图中，若用箭头标明了边是有方向性(单向或者双向)的，则称这样的图为有向图，否则
称为无向图。 - 权重：边上显示的数字，可以有各种各样的现实意义
- 网络：有带权重的图
邻接矩阵表示法
怎么在程序中表示一个图
邻接矩阵——有什么好处？
- 直观、简单、好理解
- 方便检查任意一对顶点间是否存在边
- 方便找任一顶点的所有"邻接点"(有边直接相连的顶点)
- 方便计算任一顶点的"度"(从该点出发的边数为"出度"，指向该点的边数为"入度")有向图的概念
邻接矩阵——有什么不好?
- 浪费空间——存稀疏图(点很多而边很少)有大量无效元素
但对稠密图(特别是完全图)还是很合算的 - 浪费时间——统计稀疏图中一共有多少条边
无向图
对应行(或列)非0元素的个数
有向图
对应行非0元素的个数是"出度";对应列非0元素的个数是"入度"
邻接表表示法
邻接表：G[N]为指针数组，对应矩阵每行一个的链表，只存非0元素
优点：
- 方便找任一顶点的所有"邻接点"
- 节约稀疏图的空间
需要N个头指针+2E个结点(每个结点至少2个域) - 方便计算任一顶点的"度"
对无向图：是的
对有向边：只能计算"出度";需要构造"逆邻接表"(存指向自己的边)来方便计算"入度" - 方便检查任意一对顶点间是否存在边？NO
对于网络，结构中要增加权重的域
