在此基础上用java代码实现这个区域的重要场所至少有10个。若有人咨询,只需提供起始点和目的地,咨询结果是一条公交线路提供重要区域的信息查询功能,包括场所名称、经过的公交线路等信息。要求使用图相关知识实现。用键盘输出。
时间: 2024-03-13 12:42:38 浏览: 55
好的,我可以使用Java来实现这个功能。首先,我需要定义一个图来表示这些场所和公交线路之间的关系。这个图可以用邻接表或邻接矩阵来表示。在这里,我将使用邻接表来表示图。
接下来,我需要定义场所和公交线路的节点类。每个节点都有一个名称和一个唯一的ID。
```java
public class Node {
private String name;
private int id;
public Node(String name, int id) {
this.name = name;
this.id = id;
}
public String getName() {
return name;
}
public int getId() {
return id;
}
}
```
然后,我需要定义边类来表示场所和公交线路之间的关系。每条边都有一个起始节点、终止节点和权重。
```java
public class Edge {
private Node start;
private Node end;
private int weight;
public Edge(Node start, Node end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
public Node getStart() {
return start;
}
public Node getEnd() {
return end;
}
public int getWeight() {
return weight;
}
}
```
接下来,我需要定义一个图类来表示整个图。这个类包含了场所和公交线路的节点和边。通过添加节点和边,我可以建立整个图。在这里,我将使用ArrayList来存储节点和边。
```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
public class Graph {
private ArrayList<Node> nodes;
private ArrayList<Edge> edges;
private Map<Node, ArrayList<Edge>> adjacencyList;
public Graph() {
nodes = new ArrayList<Node>();
edges = new ArrayList<Edge>();
adjacencyList = new HashMap<Node, ArrayList<Edge>>();
}
public void addNode(Node node) {
nodes.add(node);
adjacencyList.put(node, new ArrayList<Edge>());
}
public void addEdge(Edge edge) {
edges.add(edge);
adjacencyList.get(edge.getStart()).add(edge);
}
public ArrayList<Node> getNodes() {
return nodes;
}
public ArrayList<Edge> getEdges() {
return edges;
}
public ArrayList<Edge> getAdjacentEdges(Node node) {
return adjacencyList.get(node);
}
}
```
现在,我需要定义一个搜索算法来查找两个节点之间的最短路径。在这里,我将使用Dijkstra算法来实现。通过使用优先队列来存储节点,我可以找到距离起始节点最近的节点,并计算出到达该节点的距离。通过遍历整个图,我可以找到起始节点和目的地节点之间的最短路径。
```java
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
public class Search {
public static ArrayList<Node> dijkstra(Graph graph, Node start, Node end) {
Map<Node, Integer> distance = new HashMap<Node, Integer>();
Map<Node, Node> previous = new HashMap<Node, Node>();
PriorityQueue<Node> queue = new PriorityQueue<Node>(new Comparator<Node>() {
public int compare(Node node1, Node node2) {
return distance.get(node1) - distance.get(node2);
}
});
for (Node node : graph.getNodes()) {
distance.put(node, Integer.MAX_VALUE);
previous.put(node, null);
}
distance.put(start, 0);
queue.add(start);
while (!queue.isEmpty()) {
Node current = queue.poll();
if (current.equals(end)) {
break;
}
for (Edge edge : graph.getAdjacentEdges(current)) {
int alt = distance.get(current) + edge.getWeight();
if (alt < distance.get(edge.getEnd())) {
distance.put(edge.getEnd(), alt);
previous.put(edge.getEnd(), current);
queue.add(edge.getEnd());
}
}
}
ArrayList<Node> path = new ArrayList<Node>();
Node current = end;
while (current != null) {
path.add(current);
current = previous.get(current);
}
return path;
}
}
```
最后,我需要定义一个主函数来演示这个功能。在这里,我将添加10个场所和公交线路的节点和边,并使用搜索算法来找到两点之间的最短路径。用户可以输入起始节点和目的地节点,并输出包括场所名称、经过的公交线路等信息的路径。
```java
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Graph graph = new Graph();
Node node1 = new Node("场所1", 1);
Node node2 = new Node("场所2", 2);
Node node3 = new Node("场所3", 3);
Node node4 = new Node("场所4", 4);
Node node5 = new Node("场所5", 5);
Node node6 = new Node("场所6", 6);
Node node7 = new Node("场所7", 7);
Node node8 = new Node("场所8", 8);
Node node9 = new Node("场所9", 9);
Node node10 = new Node("场所10", 10);
graph.addNode(node1);
graph.addNode(node2);
graph.addNode(node3);
graph.addNode(node4);
graph.addNode(node5);
graph.addNode(node6);
graph.addNode(node7);
graph.addNode(node8);
graph.addNode(node9);
graph.addNode(node10);
graph.addEdge(new Edge(node1, node2, 5));
graph.addEdge(new Edge(node1, node3, 10));
graph.addEdge(new Edge(node2, node3, 2));
graph.addEdge(new Edge(node2, node4, 20));
graph.addEdge(new Edge(node3, node4, 5));
graph.addEdge(new Edge(node3, node5, 10));
graph.addEdge(new Edge(node4, node6, 5));
graph.addEdge(new Edge(node5, node6, 5));
graph.addEdge(new Edge(node5, node7, 20));
graph.addEdge(new Edge(node6, node8, 10));
graph.addEdge(new Edge(node7, node8, 5));
graph.addEdge(new Edge(node7, node9, 10));
graph.addEdge(new Edge(node8, node10, 5));
graph.addEdge(new Edge(node9, node10, 20));
Scanner scanner = new Scanner(System.in);
System.out.print("请输入起始节点:");
int start = scanner.nextInt();
System.out.print("请输入目的地节点:");
int end = scanner.nextInt();
ArrayList<Node> path = Search.dijkstra(graph, graph.getNodes().get(start - 1), graph.getNodes().get(end - 1));
System.out.println("最短路径为:");
for (int i = path.size() - 1; i >= 0; i--) {
System.out.println(path.get(i).getName());
}
}
}
```
这个程序可以让用户输入起始节点和目的地节点,并输出包括场所名称、经过的公交线路等信息的路径。用户可以根据自己的需求,来查询不同的起始节点和目的地节点,以获取他们需要的信息。
阅读全文