图中所有和初始出发点 V1 有路径相通的顶点都已访问为止。此时，从 V1 开始的搜索过程结束，若 G 是连通图则搜索完成。
显然，上述搜索法的特点是尽可能先对横向进行搜索，故称之为广度优先搜索。设 x 和 y 是两个相继被访问过的顶点，若当前是以 x 为出发点进行搜索，则在访问 x 的所有未曾访问过的邻接点之后，紧接着是以 y 为出发点进行横向搜索，并对搜索到的 y 的邻接点中尚未被访问的顶点进行访问。也就是说，先访问的顶点其邻接点先被访问。为此，需引进队列保存已访问过的顶点。
下面以邻接矩阵作为图的存储结构，给出广度优先搜索算法。
BFS(k)
int k;
{
int i,j;
SETNULL(Q); //置空队Q
printf(“%c\n”,g.vexs[k]); //访问出发点VK+1
visited[k]=TRUE; //标记VK+1已访问过
ENQUEUR(Q,K); //已访问过的顶点（序号）入队
while(!EMPTY(Q)) //队非空时执行
{
i=DEQUEUQ(Q); //队头元素序号出队
for(j=0;j<n;j++)
if((g.arcs[i][j]==1)&&(!visited[j]))
{
//访问Vi+1 的未曾访问的邻接点//Vj+1
printf(“%c\n”,g.vexs[j]);
visited[j]=TRUE;
ENQUEUE(Q,j); //访问过的顶点入队
}
}
}//BFS
在一个城市中，所有站点是通过公交线路联结在一起的，可以将整个城市的所有站点看作是一个连通图上的点。从任一站点出发，经过有限次转车一定可以到达另一个站点。考虑到实用性，规定一个转车上限，因为超过一定次数的转车基本上没有乘客会选用。
欲查找从起始站点A到目的站点B的换乘最少的路径，我们可以从A点出发，以公交车路线为基础进行广度优先搜索，到B站点即告终止。找到B站点时，一定是转车次数最少的。
假定从A站到B站的换乘车次数的上限是3次，查找从A站到B站的换乘最少的路径的具体步骤如下:
第一步：设站点A的所有可达站点的集合为NeighborNodeA(能坐一次车直达的站点即为可达站点)，如果B∈NeighborNodeA，则乘一次车即可到达，如图3.2（a）所示，算法结束。否则转第二步。
第二步：找出 NeighborNosdeA的所有邻接站点集合NeighborNodeA1，如果B∈NeighborNodeA1，按顺序找出这个交集中的车由哪些车转来。即知经一次转车即可到达目的站点，如图3.2（b）所示，C,D, E 均为换乘车站，算法结束。否则转第三步。
第三步：找出NeighborNodeA1中车的所有邻接站点的集合NeighborNodeA2，如果B∈NeighborNodeA2，则按顺序找出这个交集中的车由哪些车转来。即知经两次转车即可到达目的站点，如图3.2（c）所示，C,E 为第一次换乘车站，D, F为第二次换乘车站，算法结束。由于换乘车次数的上限为3次，当三次换乘仍无法到达终止站点时，则认为没有符合条件的换乘方案。
图3.2 顶点A的可达顶点
如果以地理意义上的可达站点做为邻接点进行广度优先搜索的话，由于站点较多，会影响查找的效率，因此可以改为以车的线路为基础进行广度优先搜索。
将整个公交网络看作是一个连通图，图中的每一个节点代表一路公共汽车经过站点的集合，两个邻接节点代表可以通过某个站互相换乘的两路公共汽车经过站点的集合。如果换乘点不同，用不同的邻接点表示。邻接边应该是有权值的，该权值可以表示换车的方便程度，或者其他一些实时信息。
同样，如果乘客欲从A到B，经过A的车有A1，A2，A3。经过B的车有B1，B2。Al可换乘C1，C2，C3车，A2可换乘C4, C5车，A3可换乘C6, C7车，C1可换乘B1车，C7可换乘B2。
该搜索过程在改进的广度优先算法中的表示如图3.3所示。
图3.3 改进的广度优先搜索算法
则从A到B的路径为A乘A1转C1, B1到达B站，或者乘A3转C7, B2到达B站。
由于在一个城市中车的数目会远远小于车站的数目，在查询换乘最少路径时，按公交线路为基础一定比按车站为基础时查询速度要快很多。
在SQL Server 2000 中新建数据库，命名为“Dijkstra”,步骤如下：
“开始”->“所有程序”->“Microsoft SQL Server”->“企业管理器”->“LOCAL”->“数据库”,单击右键，选择“新建数据库”，出现下面的窗口，将数据库的名称命名为“Dijkstra”。这样，数据库就成功建立了。建表界面如图4.1所示。
图4.1 数据库属性界面
将数据库“Dijkstra”伸展开，如下图所示，选择“表”，单击右键，选择“新建表”，输入所要建立的表的相关信息，即成功新建了一张表。如图4.2所示。
图4.2
这时的表是张空表，想要表里有内容显示，可以点在刚刚新建的那张表的名字上，单击右键，选择“打开表”->“返回所有行”，即可向表里插入内容。
1、建筑信息表：
建筑信息表中各字段的属性如图4.3所示。
图4.3
建筑信息表的内容如图4.4所示。
图4.4
2、门牌信息表
门牌信息表中各个字段的属性如图4.5所示。
图4.5
门牌信息表的内容如图4.6所示。
图4.6
3、车站基本信息表
车站基本信息表中各个字段的属性如图4.7所示。
图4.7
车站基本信息表的内容如图4.8所示。
图4.8
4、公交线路基本信息表
公交线路基本信息表中各个字段的属性如图4.9所示。
图4.9
公交线路基本信息表的内容如图4.10所示。
图4.10
5、线路站点信息表
线路站点信息表中各个字段的属性如图4.11所示。
图4.11
线路站点信息表的内容如4.12图所示。
图4.12
6、弧段要素表
弧段要素表中各个字段的属性如图4.13所示。
图4.13
弧段要素表的内容如图4.14所示。
图4.14
7、换乘车次表
换乘车次表中各个字段的属性如图4.15所示。
图4.15
换乘车次表的内容如图4.16所示。
图4.16
首先在Visual Studion.NET 2003 中新建我们的项目，操作如图4.17所示。
选择“Visual C#项目”的“Windows应用程序”，名称命名为“毕业设计电子地图”，点击“确定” ，即可完成项目的新建。如图4.18所示。
新建的窗口显示如图4.19所示。
上一页 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] ... 下一页 >>