图

7.1 图及其抽象数据类型

7.1.1图的基本概念

1. 图的定义和术语

图是由顶点集合及顶点间的关系集合组成的一种数据结构.顶点之间的关系称为边.一个图G记为$G=(V,E)$,V是顶点$V_{i}$的有限集合,n为顶点数;E是边的有限集合,即

$$V=\left { v_{i}|v_{i}\in 某个数据集合 \right },0 \leq i <n,n\geq0$$

$$E=\left{ (v_{i},v_{j})|v_{i,v_{j} \in V}\right},0 \leq i,j <n,i \neq j$$

2.顶点的度

顶点的度是指与顶点$$V_{i}$$关联的边数,记为$$degree(v_{i})$$.度为0的顶点称为孤立点,度为1的顶点称为悬挂点.

**入度:**以$$v_{i}$$为终点的边数称为$$V_{i}$$的入度,记作$$indegree(V_{i})$$

**出度:**以$$v_{i}$$为起点的边数称为$$V_{i}$$的入度,记作$$outdegree(V_{i})$$

3.子图、真子图

4.路径

5.连通性

7.1.2图抽象数据类型

图的基本操作有:获得顶点数、获得顶点元素、插入顶点或边、删除顶点或边、遍历等

图抽象数据类型声明如下：

ADT Graph<T>{
    int vertexCount()//返回顶点数
    T getVertex(int i)//返回顶点vi元素
    void setVertex(int i,T x)//设置顶点vi元素为x
    int insertVertex(T x)//插入元素值为x的顶点，返回顶点序号
    void removeVertex(int i)//删除顶点v及其关联的边
  	int next(int i,int j)//返回vi在vj后的后继邻接顶点序号
 	void insertEdge(int i,int j,int weight)//插入边<vi,vj>，权值为weight 
 	void removeEdge(int i,int j)//删除边<vi,vj>
    int weight(int i,int j)//返回<vi,vj>边的权值
    void DFSTraverse(int i)//非连通图的一次深度优先搜索遍历，从顶点vi出发
	void BFSTraverse(int i)//非连通图的一次广度优先搜索遍历，从顶点vi出发
    void minSpanTree()//构造带权无向图的最小生成树，Prim算法
    void shortestPath(int i)//求带权图顶点vi的单源最短路径， Dijkstra算法
	void shortestPath()//求带权图没对顶点间的最短路径及长度,Floyd算法
}

7.2 图的表示和实现