图的操作和应用之景区信息管理系统
信息:
现有一个景区，景区里面有若干个景点，景点之间满足以下条件：
(1) 某些景点之间铺设了道路（相邻）
(2) 这些道路都是可以双向行驶的（无向图）
(3) 从任意一个景点出发都可以游览整个景区（连通图）
开发景区信息管理系统，对景区的信息进行管理。使用图的数据结构来保存景区景点信息，为用户提供创建图、查询景点信息、旅游景点导航、搜索最短路径、铺设电路规划等功能。
(1) 景点信息：景点编号、名字和介绍
编号 名字 介绍
0 A区 ……
1 B区 ……
2 C区 ……
3 D区 ……
4 E区 ……
5 F区 ……
6 G区 ……
(2) 道路信息：景点1，景点2、两个景点之间的距离。
景点1 景点2 距离(m)
A C 700
A E 1000
A F 600
B C 1000
B G 1000
C D 400
D E 300
D G 400
E F 600
F G 500
(1) 读文件创建图
输入：从Vex.txt文件中读取景点信息，从Edge.txt文件中读取道路信息。
处理：根据读取的景区信息创建景区景点图。
1、数据格式
Vex.txt每一行记录一个点的信息，格式为：“景点编号，景点名字，景点介绍”（景点编号从0开始逐个加1）
文件示例如下：
Edge.txt每一行记录一条边的信息，格式为：“景点1的编号，景点2的编号，道路的长度”（字段用中文逗号分割）若文件没有某两个点的信息，则表示这两个点之间没有直接路径。
文件示例如下：
使用Java语言采用邻接表存储：
点的定义：
public class Node {
private int num;//景点编号
private String name;//景点名字
private String info;//景点介绍
private Edge nextEdge;//指向第一条边邻接边
}
边的定义：
public class Edge {
private Node front;//边的前顶点即路径出发点
private Node back;//边的后顶点即路径终点
private int weight;//边的权重即路径长度
private Edge next;//下一条从出发点开始的边
}
图的定义：
public class AdjecentList {
private List<Node> nodes = new ArrayList<Node>();
}
读文件：
File filename1=new File(path);//path为txt文件的绝对路径
InputStreamReader reader1= new InputStreamReader(new FileInputStream(filename1));
BufferedReader br1 = new BufferedReader(reader1);
List<String> list1=new ArrayList<String>();//存储从文件中读出的信息
String line = "";
line = br1.readLine();
while (line != null) {
list1.add(line);
line = br1.readLine();
}
br1.close();
图的创建：
AdjecentList graph = new AdjecentList();
for(String nodeInfo : list1){
if(nodeInfo==null){
IOTool.print("数据读入错误！");
}
else{//添加点集
Node node = new Node();
node.setnode(nodeInfo);
graph.addNode(node);
}
}
for(String edgeInfo : list2){
if(edgeInfo!=null){//添加边集
String []pair = edgeInfo.split("，");
int frontNode =Integer.parseInt(pair[0]);
int backNode =Integer.parseInt(pair[1]);
int weight=Integer.parseInt(pair[2]);
Node front = graph.findNode(frontNode);
Node back = graph.findNode(backNode);
if (front != null && back != null) {
Edge edge = new Edge();
edge.setFront(front);
edge.setBack(back);
edge.setweight(weight);
front.addEdge(edge);
}
(2) 查询景点
输入：想要查询的景点的编号。
处理：根据输入的景点编号，查询该景点及相邻景点的信息。
输出：
① 景点名字
② 景点介绍
③ 相邻景区的名字
④ 到达相邻景区的路径长度
for(Node node : nodes){
if (node.getnum()==data) {
return node;
}
}
(3) 旅游景点导航
输入：起始景点的编号。
处理：使用深度优先搜索(DFS)算法，查询以该景点为起点，无回路游览整个景区的路线。
输出：所有符合要求的导航路线。
//输出所有符合要求的导航路线：（重点代码）
visited.put(node,1);//输入第一个顶点编号得的第一个顶点放入DFS,用Map集合visited作为标志该点是否被访问集合，置为1表示已访问
stack.add(node);//用栈结构存储深度优先搜索路径以便回溯
while(!stack.isEmpty())
{
Node adjvex=getfirstunvisited(stack.peek(),visited,visit);//得到栈顶顶点没有被访问过的邻接边的且没有被访问过的后顶点，Map集合visit作为标志该边是否被访问集合，并标记邻接边为已访问
if(stack.size()==visited.size())//说明已经访问过所有景点
{
printPath(stack);
Node n=stack.pop();//开始回溯
visited.put(n,0);
}
if(adjvex!=null) {
DFS(adjvex,visited,visit,stack);//用递归达成深度优先搜索
}
else {//该点的所有邻接边的没有访问过的后顶点都已经访问完
Node n=stack.pop();//回溯到上一顶点
visited.put(n,0);
Edge edge=n.getNextEdge();//得到已出栈顶点的第一条邻接边
while(edge!=null)
{
visit.put(edge,0);//将出栈顶点的所有邻接边释放即由已访问标志为未访问以使下次访问能得到所有路径
edge=edge.getNext();//指针后移指向下一条从edge前顶点出发的边
}
}
}
(4) 搜索最短路径
输入：
① 起始景点的编号
② 终点的编号。
处理：使用迪杰斯特拉(Dijkstra)算法，求得从起始景点到终点之间的最短路径，计算路径总长度。
输出：
① 最短路线
② 路径总长度
//迪杰斯特拉(Dijkstra)算法：（重点代码）
init(x,y);//初始化各点距离及路径
System.out.println("开始执行...");
while(!unVisited.isEmpty()){//unVisited未求出最短路径的点集合
int vertexId=pickMinInUnvisited(x);
if(vertexId==-1)
break;
//将其加入到已hasvisited集合中,并从未访问列表中去除
hasVisited.add(vertexId);//hasVisited已求出最短路径的点集合
unVisited.remove((Integer)vertexId);//对u为起点,相邻的点为终点的临接点进行松弛操作
relax(vertexId);
}
init(int x,int y){
distances=new int[graph.getNodes().size()];//记录从起点到其他任意一点的路径长度
paths=new int[graph.getNodes().size()];//记录Path[i]表示从S到i的最短路径中，结点i之前的结点的编号,即对应点的前一个节点
for(int i=0;i<distances.length;i++){
distances[i]=Integer.MAX_VALUE;
}
distances[x]=0;//把与x相邻的点的距离求出,并标准初始路径
for(Edge edge=gh.findNode(x).getNextEdge();edge!=null;edge=edge.getNext()){
distances[edge.getBack().getnum()]=edge.getweight();
paths[edge.getBack().getnum()]=x;
}//初始化未知最短路点集合和已知最短路集合
unVisited.clear();
hasVisited.clear();
hasVisited.add(x);
//其余点为未知
for(int i=0;i<gh.getNodes().size();i++){
if(i!=x){
unVisited.add(i);
}
}
}
pickMinInUnvisited(x){//从未求出最短路径的集合中找到与原点最近的点
int minIndex=-1;
int min=Integer.MAX_VALUE;
for(int i=0;i<distances.length;i++){
if(unVisited.contains(i)){
if(distances[i]<min){
minIndex=i;
min=distances[i];}}}
}
relax(int u){//考察所有以点u为起点的边,对每一条边进行松弛操作
for(Edge edge=gh.findNode(u).getNextEdge();edge!=null;edge=edge.getNext()){
int v=edge.getBack().getnum();
//对v进行松弛,看是否满足distances[v]>distances[u]+w[u][v]
int w=edge.getweight();
if(distances[v]>distances[u]+w){
distances[v]=distances[u]+w;
//记录v的最短路径时,前一个节点为u
paths[v]=u;
}
}
}
(5) 铺设电路规划
处理：根据景区景点图使用普里姆(Prim)算法构造最小生成树，设计出一套铺设线路最短，但能满足每个景点都能通电的方案。
输出：
① 需要铺设电路的道路
② 每条道路铺设电路的长度
③ 铺设电路的总长度
int n=graph.getNodes().size();//获取图的所有顶点数目
String[] c=new String[n] ;
for(int i=0;i<n;i++){
c[i]=graph.findNode(i).getname();
}
int[] lowcost = new int[n]; //到新集合的最小权
int[] mid= new int[n];//存取前驱结点
List<String> list=new ArrayList<String>();//用来存储加入结点的顺序
int i, j, min, minid , sum = 0;
//初始化辅助数组
for(i=1;i<n;i++){
lowcost[i]=getWeight(start,i); //初始是以0为起点到各个节点的权重
mid[i]=0; //记录每个节点的起点为0
}
list.add(c[0]);
//一共需要加入n-1个点
for(i=1;i<n;i++){
min=Integer.MAX_VALUE;
minid=0;
//每次找到距离集合最近的点
for(j=1;j<n;j++) {
if(lowcost[j]!=0&&lowcost[j]<min) {
min=lowcost[j];
minid=j;
}
}
if(minid==0) return;
list.add(c[minid]);
lowcost[minid]=0;
sum+=min;
System.out.println(c[mid[minid]] + "到" + c[minid] + " 权值：" + min);
//加入该点后，更新其它点到集合的距离
for(j=1;j<n;j++)
{
if(lowcost[j]!=0&&lowcost[j]>getWeight(minid,j)){
lowcost[j]=getWeight(minid,j);
mid[j]=minid;
}
}
}
(6) 修改图保存文件
插入、删除、修改顶点、边的信息，注意顶点和边的关系，之后保存文件，重新读取文件建立图的存储结构并显示。
重点注意顶点和边的关系，考虑边是否重复？顶点是否存在？……
不详细写增删查改操作了…
就这样子吧！