Java数据结构用图的知识构造公交路线代码
时间: 2023-07-11 10:40:40 浏览: 50
以下是使用Java数据结构构造公交路线图的示例代码:
```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class BusRoute {
// 定义节点类
private static class Node {
String name; // 站点名称
double longitude; // 经度
double latitude; // 纬度
public Node(String name, double longitude, double latitude) {
this.name = name;
this.longitude = longitude;
this.latitude = latitude;
}
}
// 定义边类
private static class Edge {
Node start; // 起点
Node end; // 终点
String name; // 路线名称
String startStation; // 起点站
String endStation; // 终点站
List<String> stations; // 经过的站点
public Edge(Node start, Node end, String name, String startStation, String endStation, List<String> stations) {
this.start = start;
this.end = end;
this.name = name;
this.startStation = startStation;
this.endStation = endStation;
this.stations = stations;
}
}
// 定义图类
private static class Graph {
Map<Node, List<Edge>> adjList; // 邻接表
public Graph() {
adjList = new HashMap<>();
}
// 添加节点
public void addNode(Node node) {
adjList.putIfAbsent(node, new ArrayList<>());
}
// 添加边
public void addEdge(Edge edge) {
adjList.get(edge.start).add(edge);
}
}
public static void main(String[] args) {
// 创建节点
Node nodeA = new Node("A", 120.2, 30.3);
Node nodeB = new Node("B", 120.3, 30.4);
Node nodeC = new Node("C", 120.4, 30.5);
// 创建边
Edge edge1 = new Edge(nodeA, nodeB, "路线1", "A1", "B1", List.of("A1", "A2", "B1"));
Edge edge2 = new Edge(nodeB, nodeC, "路线2", "B1", "C1", List.of("B1", "B2", "C1"));
// 创建图
Graph graph = new Graph();
graph.addNode(nodeA);
graph.addNode(nodeB);
graph.addNode(nodeC);
graph.addEdge(edge1);
graph.addEdge(edge2);
// 查询路线
List<Edge> route = new ArrayList<>();
boolean found = dfs(graph, nodeA, nodeC, new ArrayList<>(), route);
if (found) {
System.out.println("从A到C的路线为:");
for (Edge edge : route) {
System.out.println(edge.name + " " + edge.startStation + "-" + edge.endStation);
}
} else {
System.out.println("没有找到从A到C的路线");
}
}
// 深度优先搜索算法
private static boolean dfs(Graph graph, Node start, Node end, List<Node> visited, List<Edge> route) {
if (start == end) {
return true;
}
visited.add(start);
for (Edge edge : graph.adjList.get(start)) {
if (!visited.contains(edge.end)) {
route.add(edge);
if (dfs(graph, edge.end, end, visited, route)) {
return true;
}
route.remove(edge);
}
}
return false;
}
}
```
这段代码演示了如何使用Java创建节点、边和图,并使用深度优先搜索算法查询从节点A到节点C的公交路线。