文档介绍：第七章图
ADT Graph {
数据对象V:V是具有相同特性的数据元素的集合,
称为顶点集。
数据关系R:
R={VR}
VR={<v,w>| v,w∈V且P(v,w),
<v,w>表示从v到w的弧,
谓词P(v,w)定义了弧<v,w>的意义或信息}
名词和术语
有向图、无向图、网、子图
弧头、弧尾、边
完全图、稀疏图、稠密图
邻接点、度、入度、出度
路径、路径长度、回路
简单路径、简单回路
连通图、连通分量、
强连通图、强连通分量
生成树、生成森林、最小生成树
基本操作P:
结构的建立和销毁:
CreateGraph(&G,V,VR); // 按V和VR的定义构造图G。
DestroyGraph(&G); // 销毁图G。
对顶点的访问操作:
LocateVex(G, u); // 若G中存在顶点u,则返回该顶点
// 在图中位置;否则返回其它信息。
GetVex(G, v); // 返回v的值。
PutVex(&G, v, value); // 对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是无
// 向的,则还删除对称弧<w,v>。
遍历
DFSTraverse(G, v, Visit()); // 从顶点v起深度优先遍历图
// G,并对每个顶点调用函数
// Visit一次且仅一次。
BFSTraverse(G, v, Visit()); // 从顶点v起广度优先遍历图
// G,并对每个顶点调用函数
// Visit一次且仅一次。
图的存储表示
图的数组(邻接矩阵)存储表示
const int MaxGraphSize = 30;
template <class T>
class Graph
{
private:
SeqList<T> vertexList;
int edge [MaxGraphSize][MaxGraphSize];
int graphsize;
// methods to find vertex and identify position in list
int FindVertex(SeqList<T> &L, const T& vertex);
int GetVertexPos(const T& vertex);
public:
// constructor
Graph(void);
¼¼
二、图的邻接表存储表示
template <class T>
class vertex
{
protected:
List<int> arc;
public:
T data;
int firstAdj;
int nextAdj;
}
template<class T>
class Graph
{
private:
SeqList<vertex> adjList;
int vexnum, um; // 图的当前顶点数和弧数
int kind; // 图的种类标志
Array<BOOL> visited(MaxGraphSize);
// 访问标志数组
int getVexPos(const T& vertex); //确定顶点位置
T getVertex(int pos); // 返回第pos个顶点
public:
int FirstAdjVex(int vertex);
int NextAdjVex(int vertex);
void DFSearch( int v, SeqList<T> *LP);
SeqList<T>& DFSTraverse;
SeqList<T>& BFSTraverse;
¼¼
} // class Graph;
有向图的十字链表存储表示
cl