数据科学与编程

一、什么是“图”（Graph）

表示“多对多”的关系
包含
- 一组顶点：通常用 V (Vertex) 表示顶点集合
- 一组边：通常用 E (Edge) 表示边的集合
 - 无向边：(v, w)
 - 有向边：<v, w>
 - 不考虑重边和自回路

二、抽象数据类型定义

类型名称：图（Graph）
数据对象集：G(V,E)由一个非空的有限顶点集合V和一个有限边集合E组成。
操作集：

<span class="code-snippet_outer">Graph <span class="code-snippet__keyword">Create</span>();//建立并返回空图；</span></code><code><span class="code-snippet_outer">Graph InsertVertex(Graph G, Vertex v);//将v插入G；</span></code><code><span class="code-snippet_outer">Graph InsertEdge(Graph G, Edge e);//将e插入G；</span></code><code><span class="code-snippet_outer">void DFS(Graph G, Vertex v);//从顶点v出发深度优先遍历图G；</span></code><code><span class="code-snippet_outer">void BFS(Graph G, Vertex v);//从顶点v出发宽度优先遍历图G；</span></code><code><span class="code-snippet_outer">void ShortestPath(Graph G, Vertex v, int Dist[]);//计算图G中顶点v到任意其他顶点的最短距离；</span></code><code><span class="code-snippet_outer">void MST(Graph G);//计算图G的最小生成树；</span>

Graph Create();//建立并返回空图；</code><code>Graph InsertVertex(Graph G, Vertex v);//将v插入G；</code><code>Graph InsertEdge(Graph G, Edge e);//将e插入G；</code><code>void DFS(Graph G, Vertex v);//从顶点v出发深度优先遍历图G；</code><code>void BFS(Graph G, Vertex v);//从顶点v出发宽度优先遍历图G；</code><code>void ShortestPath(Graph G, Vertex v, int Dist[]);//计算图G中顶点v到任意其他顶点的最短距离；</code><code>void MST(Graph G);//计算图G的最小生成树；

三、邻接矩阵

邻接矩阵G[N][N]——N个顶点从0到N-1编号，若存在边，则 G[i][j] = 1，否则为0。

对于无向图的存储，怎样可以省一半空间？
邻接矩阵
用一个长度为N(N+1)/2的1维数组A存储{G00,G10,G11,……,Gn-1,0,…,Gn-1 n-1}，则Gij在A中对应的下标是：( i*(i+1)/2 + j )对于网络,只要把G[i][j]的值定义为边<vi,vj>的权重即可。

如，若查看是否有v6到v3的边，则查看G[6*7/2 + 3] = G[24]即可。

四、邻接矩阵性质

优点：邻接矩阵 —— 有什么好处？

直观、简单、好理解
方便检查任意一对顶点间是否存在边
方便找任一顶点的所有“邻接点”（有边直接相连的顶点）
方便计算任一顶点的“度”（从该点发出的边数为“出度”，指向该点的边数为“入度”）
- 无向图：对应行（或列）非0元素的个数
- 有向图：对应行非0元素的个数是“出度”；对应列非0元素的个数是“入度”