风之谷 - BlogJava

随笔-1 评论-44 文章-3 trackbacks-0

2012年3月23日

[算法]Java判断一个DAG图（无回路有向图Directed Acyclic Graph）

废话不多说，直接上代码

package com.primeton.eos;

import java.util.ArrayList;

import java.util.HashMap;

import java.util.List;

import java.util.Map;

import java.util.Stack;

public class DAG {

public static Map createNode(String name) {

HashMap node = new HashMap();

node.put("name", name);

node.put("child", new ArrayList());

return node;

}

public static void main(String[] args) {

Map start = createNode("start");

Map node1 = createNode("node1");

Map node2 = createNode("node2");

Map node3 = createNode("node3");

Map node4 = createNode("node4");

Map node5 = createNode("node5");

Map end = createNode("end");

((List) start.get("child")).add(node1);

((List) start.get("child")).add(node2);

((List) node1.get("child")).add(node2);

((List) node1.get("child")).add(node3);

((List) node2.get("child")).add(node3);

((List) node3.get("child")).add(node4);

((List) node4.get("child")).add(node5);

((List) node5.get("child")).add(start);

((List) node5.get("child")).add(end);

System.out.println(checkChild(start));

}

public static Stack<String> stack = new Stack<String>();

public static boolean a = false;

public static boolean checkChild(Map cursor) {

if (stack.contains(cursor.get("name"))) {

return false;

}

stack.push((String) cursor.get("name"));

List childs = (List) cursor.get("child");

if (childs != null) {

for (int i = 0; i < childs.size(); i++) {

if (!checkChild((Map) childs.get(i))) {

return false;

}

}

}

stack.pop();

return true;

}

}

注意，stack中不能直接放cursor，否则就会出问题了，呵呵

posted @ 2012-03-23 20:25 黑旋风阅读(2571) | 评论 (0) | 编辑收藏

仅列出标题