}EDGETYPE,*pEDGETYPE;
注意：
以上数据结构的定义只是景点和路线的基本信息定义，由于实验中采用了类模版编程技术，在实现图算法的时候景点和路线的类型是不确定的，因此在算法实现时所采用的数据结构定义如下：
3.图算法中顶点数据结构的定义
template//顶点的定义，T为景点信息结构类型，E为路线信息结构类型；
structCVertex
{
public:
TdataNode;//顶点数据结构类型；
CEdge*pAdjList;//指向边链表的头指针；
CVertex（）
{
this->pAdjList=NULL;
}
CVertex（Tdata）
{
this->dataNode=data;
this->pAdjList=NULL;
}
booloperator!
=（constCVertex&V）
{
returnthis->dataNode!
=V.dataNode;
}
booloperator==（constCVertex&V）
{
returnthis->dataNode==V.dataNode;
}
};
4.图算法中边的数据结构定义
template//边的定义，T为景点信息结构类型，E为路线信息结构类型；
structCEdge
{
public:
CEdge（）{}
CEdge（intnum,Eweight）:
destVertex（num）,costOfEdge（weight）
{
this->pNextEdge=NULL
}
booloperator!
=（CEdge&R）const
{
return（destVertex!
=R.destVertex）?
true:
false;
}
public:
intdestVertex;//记录另外一个顶点的位置；
EcostOfEdge;//边的权值
CEdge*pNextEdge;//指向下一条边链的指针；
};
5.图（CGraphLink）类数据结构定义（图存储结构采用了邻接表的存储结构）
template//邻接表存储结构的定义；
classCGraphLink
{
public:
CGraphLink（void）;
CGraphLink（intnum）;
~CGraphLink（void）;
boolisGraphEmpty（）const
{
if（numVertices==0）returntrue;
elsereturnfalse;
}
boolisGraphFull（）const
{
if（numVertices==maxNumOfVertex||
numEdges==maxNumOfVertex*（maxNumOfVertex-1）/2）returntrue;
elsereturnfalse;
}
intGetNumberOfVertices（void）
{
returnnumVertices;
}
intGetNumberOfEdges（void）
{
returnnumEdges;
}
TGetValue（inti）;
EGetWeight（intV1,intV2）;
intGetFirstNeighbor（intV）;
intGetNextNeighbor（intV,intW）;
boolInsertVertex（constT&vertex）;
boolInertEdge（intV1,intV2,EcostOfEdge）;
boolRemoveVertex（intV）;
boolRemoveEdge（intV1,intV2）;
voidDepthFirstSearch（constCGraphLink&G,intV,T*nodeContainer）;
voidBreadthFirstSearch（constCGraphLink&G,intV,T*nodeContainer）;
intGetVertexPos（constTvertex）;
voidFindArticulationPoints（CGraphLink&G,CVertex*pVertexArray）;
voidShortestPathByDijkstra（CGraphLink&G,intV,EdistArray[],UINTpathArray[]）;
voidShortestPathByBellman_Ford（CGraphLink&G,intV,EdistArray[],intpathArray[]）;
voidShortestPathByFloyd（CGraphLink&G,Edist2DArray[][DEFAULTMAXVERTEX],intpath2DArray[][DEFAULTMAXVERTEX]）;
voidMinSpanTreeByPrim（CGraphLink&G,constTU,CMinSpanTree&MST）;
voidShowShortestPath（CGraphLink&G,intV,EdistArray[],intpathArray[]）;
vector>FindAllPaths（CGraphLink&G,intStart,intEnd）;
boolisCircle（intpop,vectorpath）;
intnumEdges;//当前的边数目；
intnumVertices;//当前顶点数；
intmaxNumOfVertex;//最大顶点数；
CVertex*NodeTable;//顶点表（各边链表的头结点）；
};
3.4功能模块分析
系统主要分为以下几个模块：
1、景点信息模块：
包括添加景点，删除景点，移动景点位置，查看景点信息，搜索相关景点
2、路线模块：
包括添加路线，删除路线，查看路线信息等
3、搜索模块：
包括深度有限遍历，广度优先遍历，两点间所有路径搜索，两点间最短路径搜索，景区所有景点最短路径搜索。
4、保存模块：
包括保存图片信息，保存其他基本信息。
5、读入模块：
包括读入图片信息，读入其他信息。
3.5关键算法分析
3.5.1图的相关概念
1.邻接表存储结构
2.深度优先搜索DFS（DepthFirstSearch）
1.算法简介
正如算法名称那样，深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。
在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探测到的边，就沿此边继续搜索下去。
当结点v的所有的边都己被探寻过后，搜索将回溯到发现结点v有那条边的始结点。
这一过程一直进行到已发现从源结点可达的所有结点为止。
如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被发现为止。
2.算法伪代码：
1.访问顶点v;VISITED[v]=1;
2.w=顶点v的第一个邻接点；
3.while（w存在）
3.1if（w未被访问）从顶点w出发递归执行该算法;
3.2w=顶点v的下一个邻接点;
3.C++代码：
template
voidCGraphLink:
:
DepthFirstSearch（constCGraphLink&G,intV,T*nodeContainer）
{
boolisVisited[DEFAULTMAXVERTEX]={0};
CEdge*myStack[DEFAULTMAXVERTEX],*p=NULL;
inttop=0;
*nodeContainer=G.NodeTable[V].dataNode;
nodeContainer++;
isVisited[V]=true;
p=G.NodeTable[V].pAdjList;
while（top>0||p!
=NULL）
{
while（p!
=NULL）
{
if（isVisited[p->destVertex]!
=0）p=p->pNextEdge;
else
{
（*nodeContainer）=G.NodeTable[p->destVertex].dataNode;
nodeContainer++;
isVisited[p->destVertex]=true;
myStack[++top]=p;
p=G.NodeTable[p->destVertex].pAdjList;
}
}
if（top>0）
{
p=myStack[top--];
p=p->pNextEdge;
}
}
}
3.广度优先搜索
1.算法简介
宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。
Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。
已知图G=（V,E）和一个源点s，宽度优先搜索以一种系统的方式探寻G的边，从而“发现”s所能到达的所有顶点，并计算s到所有这些顶点的距离（最少边数），该算法同时能生成一棵根为s且包括所有可达顶点的宽度优先树。
对从s可达的任意顶点v，宽度优先树中从s到v的路径对应于图G中从s到v的最短路径，即包含最小边数的路径。
该算法对有向图和无向图同样适用。
之所以称之为宽度优先算法，是因为算法自始至终一直通过已找到和末找到顶点之间的边界向外扩展，就是说，算法首先搜索和s距离为k的所有顶点，然后再去搜索和S距离为k+1的其他顶点。
为了保持搜索的轨迹，宽度优先搜索为每个顶点着色：
白色、灰色或黑色。
算法开始前所有顶点都是白色，随着搜索的进行，各顶点会逐渐变成灰色，然后成为黑色。
在搜索中第一次碰到一顶点时，我们说该顶点被发现，此时该顶点变为非白色顶点。
因此，灰色和黑色顶点都已被发现，但是，宽度优先搜索算法对它们加以区分以保证搜索以宽度优先的方式执行。
若（u,v）∈E且顶点u为黑色，那么顶点v要么是灰色，要么是黑色，就是说，所有和黑色顶点邻接的顶点都已被发现。
灰色顶点可以与一些白色顶点相邻接它们代表着已找到和未找到顶点之间的边界。
2.算法伪代码：
1.初始化队列Q;
2.访问顶点v;visited[v]=1;顶点v入队Q;
3.while（队列Q非空）
3.1v=队列Q的队头元素出队;
3.2w=顶点v的第一个邻接点;
3.3while（w存在）
3.3.1如果w未被访问，则
访问顶点w;visited[w]=1;顶点w入队列Q；
3.3.2w=顶点v的下一个邻接点；
1.C++代码：
template
voidCGraphLink:
:
BreadthFirstSearch（constCGraphLink&G,intV,T*nodeContainer）
{
boolisVisited[DEFAULTMAXVERTEX]={0};
intmyQueue[DEFAULTMAXVERTEX],nFront,nRear;
CEdge*p;
nFront=nRear=0;
*nodeContainer=G.NodeTable[V].dataNode;
nodeContainer++;
isVisited[V]=true;
myQueue[++nRear]=V;
while（nFront!
=nRear）
{
V=myQueue[++nFront];
p=G.NodeTable[V].pAdjList;
while（p!
=NULL）
{
if（isVisited[p->destVertex]==0）
{
V=p->destVertex;
（*nodeContainer）=G.NodeTable[p->destVertex].dataNode;
nodeContainer++;
isVisited[V]=true;
myQueue[++nRear]=V;
}
p=p->pNextEdge;
}
}
}
3.5.2Dijkstra算法
1.算法简介：
Dijkstra（迪杰斯特拉）算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。
主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。
2.算法伪代码：
1.初始化数组dist、path和s；
2.while（s中的元素个数2.1在dist[n]中求最小值，其下标为k（则vk为正在生成的终点）；
2.2输出dist[j]和path[j]；
2.3修改数组dist和path；
2.4将顶点vk添加到数组s中；
3.C++代码：
template
voidCGraphLink:
:
ShortestPathByDijkstra（CGraphLink&G,intV,Edis
升级会员 