深度优先搜索算法

最近在看图论中遍历两点间的不同路径，找到深度优先搜索算法。

先来记录下原本的算法方法

1. 准备一个栈来存储临时数据

2. 获得所有点之间的所有直接路径

3. 将起始节点压入栈

4. 从起始节点出发，找到第一个临节点

5. 如果这个临节点就是结束点，就把这个节点压入栈，那么这个栈内元素就是一条路径

6. 把结束点弹出，再继续寻找其他的结束节点，直到栈内没有元素

7. 如果这个节点不是结束点，就把这个节点作为开始节点，loop4-7步


直接贴代码吧

private void searchRoutes(Town startTown, 
                          Town endTown) throws Exception {
    for (Route knownRoute : knownRouteList) {
	if (knownRoute.getStartTown().equals(startTown)) {
	    backStack.push(knownRoute.getEndTown());
	    if (knownRoute.getEndTown().equals(endTown)) {
		createNewRoute(business);// 一个新的路线
		
	        backStack.pop();// 将最后一个弹出
	        /* 再以最后一个城市为开始城市重新选择 */
		continue;
	    }

            /* 结束城市不符合但是开始城市符合，就变换开始城市，从新循环 */
	    searchRoutes(knownRoute.getEndTown(), endTown, business);
	}
    }

    backStack.pop();
}

这里有一个问题，原先的深度优先搜索算法是不允许出现回路的。即ACA，当再次碰到A时，就会结束，不会出现ACACA的情况，但是如果遇到有变态的业务，可以有回路，那么需要在算法中进些修改

回路及时出现，必须要有所节制，不然会出现死循环。

private void searchRoutes(Town startTown, 
                          Town endTown) throws Exception {
    for (Route knownRoute : knownRouteList) {
	if (knownRoute.getStartTown().equals(startTown)) {
	    backStack.push(knownRoute.getEndTown());
	    if (knownRoute.getEndTown().equals(endTown)) {
		createNewRoute(business);// 一个新的路线
		
                if (backStack.size() >= 5) {
	            backStack.pop();// 将最后一个弹出
	            /* 再以最后一个城市为开始城市重新选择 */
		    continue;
                }
	    }

            if (backStack.size() >= 5) {
                backStack.pop();
            } else {
                /* 结束城市不符合但是开始城市符合，就变换开始城市，从新循环 */
	        searchRoutes(knownRoute.getEndTown(), endTown, business);
            }
	}
    }

    backStack.pop();
}

这个是如果节点超过5个就跳出

转载于:https://my.oschina.net/zzg/blog/313947