中级农民
- 积分
- 100
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2015-5-19
- 最后登录
- 1970-1-1
|
本帖最后由 Latte 于 2016-4-11 08:56 编辑
我感觉在tree都还容易理解,但在graph里我就很头疼,分享一个题目吧,昨天OA的一个题,隔壁版有人分享过,我规定时间没做出来Input是这样的:在input.txtfile里:
A F
A : B C
B : C D E
C : F
D : F
第一行字母代表start和end,后面是node和node相邻的path/node
求A -> F所有path,很蛋疼的是网上和书里好多例子都是int代表的。我很弱希望牛人指点轻拍,BFS构建所有A出发的path,一旦发现终点是F,立马加入final list里面
不知是否需要一个纪录node是否visit的list- static List<String> parseLines(List<String> lines) {
-
- HashMap<String, ArrayList<String>> gh = new HashMap<String, ArrayList<String>>();
-
- String node = lines.get(0);
- String[] nodeArray = node.split(" "); //[A, E]
- String startNode = nodeArray[0];
- String endNode = nodeArray[1];
- // create the graph as a hashmap[A: [B, C, D]]
- for (String line : lines.subList(1, lines.size()-1)) {
- String[] list = line.split(" : ");
- ArrayList<String> neighbor = new ArrayList<String>(Arrays.asList(list[1].split(" ")));
-
- List<String> tempPaths = new ArrayList<String>();
- // initialize a paths array ["A"]
- tempPaths.add(0, startNode);
-
- List<String> finalPaths = new ArrayList<String>();
-
- int n = gh.keySet().size();
-
- // not sure if needs to track if the node has been visited
- HashMap<String, Boolean> visitMap = new HashMap<String, Boolean>();
- // Create a queue for BFS
- LinkedList<String> queueBFS = new LinkedList<String>();
- // Mark the current node as visited and enqueue it
- visitMap.put(startNode, true);
- queueBFS.add(startNode);
-
- while (queueBFS.size() > 0) {
-
- // get the node in the queue(head of list)
- String polled = queueBFS.poll();
-
- // get the neighbor(ArrayList) of this node
- ArrayList<String> neighbor = gh.get(polled);
-
- for (int i = 0; i < tempPaths.size(); i++) {
- if (neighbor == null) {
- break;
- }
- String path = tempPaths.get(i);
- // find the path that ends with current node
- if (path.substring(path.length() -1).equals(polled)) {
-
- for (String thisNode: neighbor) {
-
- String newPath = path.concat(thisNode);
- tempPaths.add(newPath);
-
- // if found an required path like "start----end", add it to final list
- // and remove it from temp list
- if (newPath.substring(newPath.length() - 1).equals(endNode)) {
- finalPaths.add(newPath);
- tempPaths.remove(newPath);
- }
-
- }
-
- // after update the path to new path "A" -> "AB", AC", remove "A"?
- tempPaths.remove(path);
-
- } // end if
-
- } // end for
-
- // after all is done, add neighbors to queue
- // Can't figure out how to do this in the above loop without repeating
- if (neighbor != null) {
- for (String currentNode: neighbor) {
- queueBFS.add(currentNode);
- }
- }
- }
-
- return finalPaths;
- }
复制代码 |
|