图Graph

public class Graph<T>
    {
        /// <summary>
        /// 图包含接点
        /// </summary>
        public List<Node<T>> Nodes;
        public Graph()
        {
            Nodes = new List<Node<T>>();
        }
    }

    public class Node<T>
    {
        /// <summary>
        /// 接点值
        /// </summary>
        public T Value;
        /// <summary>
        /// 是否被访问过
        /// </summary>
        public bool IsVisited;
        /// <summary>
        /// 关系接点
        /// </summary>
        public List<Node<T>> AssociatedNodes;

        public Node(T value)
        {
            Value = value;
            IsVisited = false;
            AssociatedNodes = new List<Node<T>>();
        }
    }

    public class GraphFactory<T>
    {
        /// <summary>
        /// 创建一个简单的关系图
        /// </summary>
        /// <returns></returns>
        public static Graph<int> CreateSimpleGraph()
        {
            Graph<int> graph = new Graph<int>();
            int len = 20;
            int i = 1;
            //图中有len个接点
            for (i = 0; i < len; i++)
                graph.Nodes.Add(new Node<int>(i));

            //随机创建40条边，可重复
            Random random = new Random();
            for (i = 0; i < 40; i++)
            {
                int n1 = random.Next(0, len);
                int n2 = random.Next(0, len);
                //如果随机到相同的点
                if (n1 == n2)
                    n2 = (n1 + 1) % len;
                graph.Nodes[n1].AssociatedNodes.Add(graph.Nodes[n2]);
                graph.Nodes[n2].AssociatedNodes.Add(graph.Nodes[n1]);
            }

            return graph;
        }

        /// <summary>
        /// 打印图
        /// 显示各接点的关系接点
        /// </summary>
        /// <param name="graph"></param>
        public static void PrintGraph(Graph<T> graph)
        {
            foreach (Node<T> node in graph.Nodes)
            {
                Console.Write("Node {0} connected to: ", node.Value);
                foreach (Node<T> associatednode in node.AssociatedNodes)
                    Console.Write("\t{0}", associatednode.Value);
                Console.WriteLine();
            }
        }

        /// <summary>
        /// 深度优先遍历
        /// </summary>
        /// <param name="graph"></param>
        public static void DepthFirstTraversal(Graph<T> graph)
        {
            Reset(graph);
            if (graph.Nodes.Count == 0)
                return;
            Node<T> node = GetNodeUnVisited(graph);
            while (node != null)
            {
                DepthFirstTraversal_Node(node);
                node = GetNodeUnVisited(graph);
            }
        }

        /// <summary>
        /// 广度优先遍历
        /// </summary>
        /// <param name="graph"></param>
        public static void BreadthFirstTraversal(Graph<T> graph)
        {
            Reset(graph);
            if (graph.Nodes.Count == 0)
                return;
            Node<T> node = GetNodeUnVisited(graph);
            Queue<Node<T>> nodequeue = new Queue<Node<T>>();

            while (node != null)
            {
                BreadthFirstTraversal_Node(node, nodequeue);
                node = nodequeue.DeQueue();
                if (node == null)
                    node = GetNodeUnVisited(graph);
            }
        }
        #region private method
        /// <summary>
        /// 深度优先遍历接点
        /// 先访问该接点，然后递归其关系接点
        /// </summary>
        /// <param name="node"></param>
        private static void DepthFirstTraversal_Node(Node<T> node)
        {
            if (node.IsVisited || node == null)
                return;
            node.IsVisited = true;
            Console.WriteLine("Node {0} is visited!", node.Value.ToString());
            foreach (Node<T> associatednode in node.AssociatedNodes)
            {
                DepthFirstTraversal_Node(associatednode);
            }
        }
        /// <summary>
        /// 广度优先遍历接点
        /// 访问该接点(如果该接点未被访问)，然后将其关系接点(如果该接点未被访问)放入队列中
        /// </summary>
        /// <param name="node"></param>
        /// <param name="nodequeue"></param>
        private static void BreadthFirstTraversal_Node(Node<T> node, Queue<Node<T>> nodequeue)
        {
            if (node.IsVisited || node == null)
                return;
            node.IsVisited = true;
            Console.WriteLine("Node {0} is visited!", node.Value.ToString());
            foreach (Node<T> n in node.AssociatedNodes)
            {
                if (!n.IsVisited)
                    nodequeue.EnQueue(n);
            }
        }
        /// <summary>
        /// 获取图中一个未访问的接点
        /// </summary>
        /// <param name="graph"></param>
        /// <returns></returns>
        private static Node<T> GetNodeUnVisited(Graph<T> graph)
        {
            foreach (Node<T> node in graph.Nodes)
                if (!node.IsVisited)
                    return node;
            return null;
        }
        /// <summary>
        /// 重新设置图中各接点的访问状态为false
        /// </summary>
        /// <param name="graph"></param>
        private static void Reset(Graph<T> graph)
        {
            foreach (Node<T> node in graph.Nodes)
                node.IsVisited = false;
        }
        #endregion
    }