7.2图的抽象数据类型
ADT图(Graph) Data 顶点的有穷非空集合和边的集合。 Operation CreateGraph (*G,V,VR) :按照顶点集V和边弧集VR的定义构造图G。 DestroyGraph(*G) :图G存在则销毁。 LocateVex(G,u) :若图G中存在顶点u，则返回图中的位置。 GetVex (G,v) :返回图G中顶点v的值。 PutVex (G,v,value) :将图G中顶点v赋值value。 FirstAdjVex (G,*v) :返回顶点v的一个邻接顶点，若顶点在G中无邻接顶点返回空。 NextAdjVex (G,v,*w) :返回顶点v相对于顶点w的下一一个邻接顶点，若w是v的最后 一个邻接点则返回“空"。 InsertVex (*G,v) :在图G中增添新顶点V。 DeleteVex ( *G,v):删除图G中顶点v及其相关的弧。 InsertArc ( *G,v,w):在图G中增添弧<v,w>,若G是无向图，还需要增添对称弧 <w,v>。 DeleteArc (*G,v,w):在图G中删除弧<v,w>,若G是无向图，则还删除对称弧 DFSTraverse(G):对围G中进行深度优先遍历，在遍历过程对每个顶点调用。 HFSTraverse(G) :对图G中进行广度优先遍历，在遍历过程对每个顶点调用。 endADT
7.3图的存储结构
7.3.1领接矩阵
图的邻接矩阵(Adjacency Matrix) 存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。
1.无向图的邻接矩阵
2.有向图的邻接矩阵
分析1: 有向图的邻接矩阵可能是不对称的。 分析2: 顶点的出度=第i行元素之和顶点的入度=第列元素之和顶点的度=第i行元素之和+第j元素之和
3.网(即有权图)的邻接矩阵表示法
代码实现：
用两个数组分别存储顶点表和邻接矩阵
#define MaxInt 32767 //表示极大值，即∞ #define MVNum 100 //最大顶点数 typedef char VerTexType; //设顶点的数据类型为字符型 typedef int ArcType;//假设边的权值类型为整型 typedef struct{ VerTexType vexs{MVNum]; //顶点表 ArcType arcs[MVNum][MVNum]; //邻接矩阵 int vexnum, arcnum; //图的当前点数和边数。 }AMGraph; // Adjacency Matrix Graph
