广度优先遍历公交路线寻路算法JAVA实现
最近写了一个生成公交电子票的工具，里面用到了公交路线寻路算法，分享一下
此算法为测试算法，仅供参考
RoadUtil.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 |
package net.code2048.swift.util; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; import net.code2048.swift.dao.PointsDaoImpl; import net.code2048.swift.dao.RoadDaoIpml; import net.code2048.swift.util.tree.Node; /** * @author 破晓(www.code2048.net) * 广度优先遍历 */ public class RoadUtil { private static Map<Integer, Node> allNode = null; /** * 根据ID获取站点名称 * @param pid * @return */ public static String getNameById(int pid) { if(allNode == null) buildTree(); return allNode.get(pid).name; } public static Map<String, Object> findRoad(int start, int end) { if(start == end) return null; Map<String, Object> result = new HashMap<String, Object>(); if(allNode == null) buildTree(); Node sn = allNode.get(start); Node en = allNode.get(end); List<Node> findNodes = new ArrayList<Node>(); // 已遍历节点 List<Node> currentNodes = new ArrayList<Node>(); // 当前到达节点 findNodes.add(sn); currentNodes.add(sn); List<HashMap<String, Object>> road = new ArrayList<HashMap<String, Object>>(); HashMap<String, Object> roadItem; if(findRoadAI(currentNodes, en, findNodes)) { Node temp = en; while(temp.parent != null && temp != sn) { roadItem = new HashMap<String, Object>(); roadItem.put("id", temp.id); roadItem.put("name", temp.name); road.add(0, roadItem); temp = temp.parent; } roadItem = new HashMap<String, Object>(); roadItem.put("id", sn.id); roadItem.put("name", sn.name); road.add(0, roadItem); } result.put("road", road); result.put("len", road.size()); return result; } /** * 寻路AI 此方法无法用于多线程并发 * @param cNode * @param end * @param fNode */ private static boolean findRoadAI(List<Node> cNode, Node end, List<Node> fNode) { //TODO: 此方法无法用于多线程并发 if(cNode.size() == 0) return false; List<Node> newCNode = new ArrayList<Node>(); // 当前到达节点 for(Node item:cNode) { for(Node ci:item.children) { if(ci == end) { ci.parent = item; return true; } if(fNode.contains(ci)) continue; ci.parent = item; newCNode.add(ci); fNode.add(ci); } } return findRoadAI(newCNode, end, fNode); } /** * 构建路线数 */ private static void buildTree() { allNode = new HashMap<Integer, Node>(); PointsDaoImpl pdi = new PointsDaoImpl(); Node item; for(Map<String, Object> pi:pdi.getPoints()) { item = new Node(); item.id = (int) pi.get("id"); item.name = (String) pi.get("pname"); item.type = (int) pi.get("type"); allNode.put(item.id, item); } RoadDaoIpml rdi = new RoadDaoIpml(); Node start = null; Map<String, Object> currentRoad = null; Node preItem = null; Node currentItem; for(Map<String, Object> pi:rdi.getRoadPoints()) { currentItem = allNode.get(pi.get("pointId")); if(currentRoad == null || !pi.get("roadId").equals(currentRoad.get("roadId"))) // 切换路线 { if(currentRoad != null && start != null && currentRoad.get("type").equals(2)) { preItem.children.add(start); start.children.add(preItem); // start.parent = preItem; // preItem.parent = start; } currentRoad = pi; start = currentItem; } else { preItem.children.add(currentItem); currentItem.children.add(preItem); // currentItem.parent = preItem; // preItem.parent = currentItem; } preItem = currentItem; } // 如果最后一个站点是环形线路终点 if(currentRoad != null && preItem != null && start != null && currentRoad.get("type").equals(2)) { preItem.children.add(start); start.children.add(preItem); // start.parent = preItem; // preItem.parent = start; } start = null; currentRoad = null; preItem = null; currentItem = null; } } |
Node.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
package net.code2048.swift.util.tree; import java.util.ArrayList; import java.util.List; /** * @author 破晓(www.code2048.net) * */ public class Node{ public Node parent; public List<Node> children = new ArrayList<>(); public String name; public int type; public int id; } |
RoadDaoIpml.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 |
package net.code2048.swift.dao; import java.sql.ResultSet; import java.sql.SQLException; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; import net.code2048.swift.connect.DataBaseManager; /** * @author 破晓(www.code2048.net) * */ public class RoadDaoIpml { public String addRoad() { return null; } public List<Map<String, Object>> getRoads() { List<Map<String, Object>> resultList = new ArrayList<Map<String, Object>>(); String sql = "select * from road order by Id"; DataBaseManager db = null; try { db = DataBaseManager.getDefaultConnection(); db.createStmt(); ResultSet result = db.getResult(sql); Map<String, Object> item; while(result.next()) { item = new HashMap<String, Object>(); item.put("id", result.getInt("Id")); item.put("rname", result.getString("rname")); item.put("type", result.getInt("rtype")); item.put("numpoint", result.getInt("numpoint")); resultList.add(item); } } catch (Exception e) { // TODO Auto-generated catch block e.printStackTrace(); } finally{ if(db != null) try { db.close(); } catch (SQLException e) { // TODO Auto-generated catch block e.printStackTrace(); } } return resultList; } public List<Map<String, Object>> getRoadPoints() { List<Map<String, Object>> resultList = new ArrayList<Map<String, Object>>(); String sql = "select t1.pindex, t1.pointId,t1.roadId, t2.rname,t2.rtype, t2.numpoint " + "from roadpoint t1, road t2 " + "where t2.Id = t1.roadId " + "order by t2.Id, t1.pindex"; DataBaseManager db = null; try { db = DataBaseManager.getDefaultConnection(); db.createStmt(); ResultSet result = db.getResult(sql); Map<String, Object> item; while(result.next()) { item = new HashMap<String, Object>(); item.put("pindex", result.getInt("pindex")); item.put("rname", result.getString("rname")); item.put("type", result.getInt("rtype")); item.put("pointId", result.getInt("pointId")); item.put("numpoint", result.getInt("numpoint")); item.put("roadId", result.getInt("roadId")); resultList.add(item); } } catch (Exception e) { // TODO Auto-generated catch block e.printStackTrace(); } finally{ if(db != null) try { db.close(); } catch (SQLException e) { // TODO Auto-generated catch block e.printStackTrace(); } } return resultList; } } |
下面是获取数据的类 不重要 可以不看
PointsDaoImpl.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
package net.code2048.swift.dao; import java.sql.ResultSet; import java.sql.SQLException; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; import org.apache.log4j.Logger; import net.code2048.swift.connect.DataBaseManager; /** * @author 破晓(www.code2048.net) * */ public class PointsDaoImpl { private static Logger logger = Logger.getLogger(PointsDaoImpl.class); public List<Map<String, Object>> getPoints() { List<Map<String, Object>> resultList = new ArrayList<Map<String, Object>>(); String sql = "select * from points order by ename"; DataBaseManager db = null; try { db = DataBaseManager.getDefaultConnection(); db.createStmt(); ResultSet result = db.getResult(sql); Map<String, Object> item; while(result.next()) { item = new HashMap<String, Object>(); item.put("id", result.getInt("Id")); item.put("pname", result.getString("pname")); item.put("type", result.getInt("ptype")); item.put("ename", result.getString("ename")); resultList.add(item); } logger.info("########Points:"); logger.info(resultList.size()); } catch (Exception e) { // TODO Auto-generated catch block logger.error(e.toString()); e.printStackTrace(); } finally{ if(db != null) try { db.close(); } catch (SQLException e) { // TODO Auto-generated catch block e.printStackTrace(); } } return resultList; } } |
DataBaseManager.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 |
package net.code2048.swift.connect; import java.sql.Connection; import java.sql.DriverManager; import java.sql.ResultSet; import java.sql.SQLException; import java.sql.Statement; import java.util.HashMap; import org.apache.log4j.Logger; import net.code2048.swift.util.ContextUtil; /** * @author 破晓(www.code2048.net) * */ public class DataBaseManager { private Connection con; private ResultSet rs; private Statement stmt; private static Logger logger = Logger.getLogger(DataBaseManager.class); /** * @param url 例：jdbc:mysql://127.0.0.1/eshop * @param user * @param password */ private DataBaseManager(String url, String user, String password) { try{ Class.forName( "com.mysql.jdbc.Driver" ); // con=DriverManager.getConnection("jdbc:mysql://localhost:3306/eshop","root","123456"); con=DriverManager.getConnection(url + "?user=" + user + "&password=" + password + "&allowMultiQueries=true&useUnicode=true&characterEncoding=UTF8"); con.setAutoCommit(false); } catch ( ClassNotFoundException cnfex ) { logger.error("Failed to load JDBC/ODBC driver." ); cnfex.printStackTrace(); System.exit( 1 ); } catch(SQLException sqle) { sqle.printStackTrace(); logger.error(sqle.toString()); } } /** * 查询数据库 * @param strSQL * @return */ public ResultSet getResult(String strSQL) { try{ rs=stmt.executeQuery(strSQL); return rs; } catch(SQLException sqle) { logger.error(sqle.toString()); return null; } } public Statement createStmt() throws SQLException { stmt=con.createStatement(ResultSet.TYPE_SCROLL_SENSITIVE,ResultSet.CONCUR_UPDATABLE); return stmt; } /** * 更新数据库 * @param strSQL * @return */ public boolean updateSql(String strSQL) { try{ stmt.executeUpdate(strSQL); con.commit(); return true; } catch(SQLException sqle) { try { con.rollback(); } catch (SQLException e) { // TODO Auto-generated catch block e.printStackTrace(); } logger.error(sqle.toString()); return false; } finally { } } /** * 回收对象 * @throws SQLException */ public void close() throws SQLException { if(rs != null) rs.close(); if(stmt != null) stmt.close(); closeConnection(); rs = null; stmt = null; con = null; // stack.push(this); } /** * 关闭当前连接 */ public void closeConnection() { try { if(con != null) con.close(); } catch(SQLException sqle) { logger.error(sqle.toString()); } } /** 连接池堆栈 */ // private static Stack<DataBaseManager> stack = new Stack<DataBaseManager>(); /** * @param url 例：jdbc:mysql://127.0.0.1/eshop * @param user * @param password * @return */ public static DataBaseManager getConnection(String url, String user, String password) { logger.info("###DBinfo:"); logger.info(url); logger.info(user); logger.info(password); return new DataBaseManager(url, user, password); } public static DataBaseManager getDefaultConnection() throws Exception { HashMap<String, String> map = ContextUtil.getInstance().getDbCon(); return getConnection(map.get("url"), map.get("user"), map.get("password")); } } |
ContextUtil.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
package net.code2048.swift.util; import java.io.File; import java.net.URL; import java.util.HashMap; import javax.xml.parsers.DocumentBuilder; import javax.xml.parsers.DocumentBuilderFactory; import org.w3c.dom.Document; import org.w3c.dom.NamedNodeMap; /** * @author 破晓(www.code2048.net) * */ public class ContextUtil { /**单例*/ private static ContextUtil instance; private HashMap<String, String> dbCon = null; private HashMap<String, String> serverCon = null; /** * 获取唯一实例 * @return * @throws Exception */ public static ContextUtil getInstance() throws Exception { if(instance == null) instance = new ContextUtil(); return instance; } private ContextUtil() throws Exception { initData(); } private void initData() throws Exception { URL fileUrl = getClass().getResource("/config.xml"); if(fileUrl != null) { String fileName = fileUrl.toURI().getPath(); File f = new File(fileName); DocumentBuilderFactory factory = DocumentBuilderFactory.newInstance(); DocumentBuilder builder = factory.newDocumentBuilder(); Document doc = builder.parse(f); dbCon = new HashMap<String, String>(); serverCon = new HashMap<String, String>(); NamedNodeMap db = doc.getElementsByTagName("db").item(0).getAttributes(); NamedNodeMap server = doc.getElementsByTagName("server").item(0).getAttributes(); dbCon.put("url", db.getNamedItem("url").getNodeValue()); dbCon.put("user", db.getNamedItem("user").getNodeValue()); dbCon.put("password", db.getNamedItem("password").getNodeValue()); serverCon.put("url", server.getNamedItem("url").getNodeValue()); } } public HashMap<String, String> getDbCon() { return dbCon; } public HashMap<String, String> getServerCon() { return serverCon; } } |
