频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
Tree Operations 打印出有向图中的环
2014-08-17 11:32:41         来源:he wolf  
收藏   我要投稿

题目:

You are given a binary tree with unique integer values on each node. However, the child pointers on each node may point to any other node in the tree including itself, introducing cycles into the binary tree. A cycle is defined when you can traverse back to the same node by following its descendants. Write a function that takes in the root node of the tree and prints out the cycles, if any, in the binary tree. The only operations available on each node are node.left (returns another Node or null), node.right, and node.value (returns the integer value of the node). Pseudocode is fine.

即找出有向图中的环(loop或者cycle),并且全部打印出来。

Example: https://www.2cto.com/uploadfile/Collfiles/20140817/20140817093505111.png

\

cycles: [1, 2, 4], [5], [3,6]


解答:

import java.util.ArrayList;

public class Graph {

    enum VertexState {
        White, Gray, Black
    }
    
    public static void main(String[] args) {
        Node node = new Node(0);
        node.color = VertexState.White;
        Node left = new Node(1);
        left.color = VertexState.White;
        node.left = left;
        Node right = new Node(2);
        right.color = VertexState.White;
        Node rightright = new Node(3);       
        node.right = right;
        left.left = node;
        right.right = rightright;
        rightright.right = node;
        
        ArrayList list = new ArrayList();
        ArrayList> ret = new ArrayList>();
        rec(node, list, ret);
        System.out.println(ret);
    }

    public static void rec(Node node, ArrayList list, ArrayList> ret) {
        if(node.color == VertexState.Gray) {
            ret.add(new ArrayList(list));
            return;
        }
        node.color = VertexState.Gray;
        list.add(node);
        if(node.left != null && node.left.color != VertexState.Black) {
            rec(node.left, list, ret);
        }
        if(node.right != null && node.right.color != VertexState.Black) {
            rec(node.right, list, ret);
        }
        list.remove(list.size()-1);
        node.color = VertexState.Black;
    }
    
    public static class Node {
        int val;
        Node left;
        Node right;
        VertexState  color;
        public Node(int val_) {
            val = val_;
        }
        @Override
        public String toString() {
            return this.val + "";
        }
    }
}



点击复制链接 与好友分享!回本站首页
相关TAG标签 有向图
上一篇:HDU 1074 Doing Homework(状压DP)
下一篇:socket编程之二:两种链接类型upd和upd
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站