数据结构和算法之图

什么是图

定义

包含

• 1. 一组顶点：通常用V(Vertex)表示顶点集合
• 2. 一组边：通常用E(Edge)表示边的集合

1. 1. 1. 1. 边是顶点对：(v,w)属于E，其中v,w属于V
      2. 2. 有向边表示从v指
      3. 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的最小生成树

常见术语

1. 无向图：无所谓方向的
2. 有向图：在图中，若用箭头标明了边是有方向性(单向或者双向)的，则称这样的图为有向图，否则
   称为无向图。
3. 权重：边上显示的数字，可以有各种各样的现实意义
4. 网络：有带权重的图

邻接矩阵表示法

怎么在程序中表示一个图

邻接矩阵——有什么好处？

1. 直观、简单、好理解
2. 方便检查任意一对顶点间是否存在边
3. 方便找任一顶点的所有"邻接点"(有边直接相连的顶点)
4. 方便计算任一顶点的"度"(从该点出发的边数为"出度"，指向该点的边数为"入度")有向图的概念

邻接矩阵——有什么不好?

1. 浪费空间——存稀疏图(点很多而边很少)有大量无效元素
   但对稠密图(特别是完全图)还是很合算的
2. 浪费时间——统计稀疏图中一共有多少条边

无向图

对应行(或列)非0元素的个数

有向图

对应行非0元素的个数是"出度";对应列非0元素的个数是"入度"

邻接表表示法

邻接表：G[N]为指针数组，对应矩阵每行一个的链表，只存非0元素

优点：

1. 方便找任一顶点的所有"邻接点"
2. 节约稀疏图的空间
   需要N个头指针+2E个结点(每个结点至少2个域)
3. 方便计算任一顶点的"度"
   对无向图：是的
   对有向边：只能计算"出度";需要构造"逆邻接表"(存指向自己的边)来方便计算"入度"
4. 方便检查任意一对顶点间是否存在边？NO
   对于网络，结构中要增加权重的域