晚上無聊寫了個二叉樹（圖）的廣度和深度遍歷算法，算法本身很簡單，但是如何做到通用呢，一下代碼是我的設計，請大家幫忙看看有什麼問題，我自己感覺有問題就是不知道具體什麼問題
public interface IGraph<TVertex>
{
IEnumerable<IEdge<TVertex>> Edges { get; }
}
public interface IEdge<TVertex>
{
TVertex From { get; set; }
TVertex To { get; set; }
}
public interface INode
{
IEnumerable<TNode> GetNextNodes<TNode>() where TNode : INode;
}
public class Edge<TVertex> : IEdge<TVertex>
{
public TVertex From { get; set; }
public TVertex To { get; set; }
}
public static class NodeVisitor
{
public static void BreadthVisit<TNode>(TNode rootNode, Action<TNode> visitAction)
where TNode : INode
{
BreadthVisit(rootNode, n => n.GetNextNodes<TNode>(), visitAction);
}
public static void BreadthVisit<TNode>(TNode rootNode, Func<TNode,IEnumerable<TNode>> nextNodeSelector, Action<TNode> visitAction)
{
var nodeQueue = new Queue<TNode>();
nodeQueue.Enqueue(rootNode);
while (nodeQueue.Any())
{
var currentNode = nodeQueue.Dequeue();
if (visitAction != null)
{
visitAction(currentNode);
}
foreach (var nextNode in nextNodeSelector(currentNode))
{
nodeQueue.Enqueue(nextNode);
}
}
}
public static void DepthVisit<TNode>(TNode rootNode, Func<TNode, IEnumerable<TNode>> nextNodeSelector, Action<TNode> visitAction)
{
var nodeStack = new Stack<TNode>();
nodeStack.Push(rootNode);
while (nodeStack.Any())
{
var currentNode = nodeStack.Pop();
if (visitAction != null)
{
visitAction(currentNode);
}
foreach (var nextNode in nextNodeSeletor(currentNode))
{
nodeStack.Push(nextNode);
}
}
}
public static void DepthVisit<TNode>(TNode rootNode, Action<TNode> visitAction)
where TNode : INode
{
DepthVisit(rootNode, n => n.GetNextNodes<TNode>(), visitAction);
}
}
public class GraphVisitor<TVertex>
{
private IGraph<TVertex> _graph;
public GraphVisitor(IGraph<TVertex> graph)
{
_graph = graph;
}
public TVertex GetRoot()
{
var vertexs = _graph.Edges.Select(t => t.From).Concat(_graph.Edges.Select(t => t.To));
var toVertexs = _graph.Edges.Select(t => t.To);
return vertexs.FirstOrDefault(t => toVertexs.All(v => !v.Equals(t)));
}
public IEnumerable<TVertex> GetNextVertexs(TVertex current)
{
return _graph.Edges.Where(t => t.From.Equals(current)).Select(t => t.To);
}
public void BreadthVisit(Action<TVertex> visitAction, TVertex startVertex)
{
NodeVisitor.BreadthVisit(startVertex, t => GetNextVertexs(t), visitAction);
}
public void BreadthVisit(Action<TVertex> visitAction)
{
NodeVisitor.BreadthVisit(GetRoot(), t => GetNextVertexs(t), visitAction);
}
public void DepthVisit(Action<TVertex> visitAction, TVertex startVertex)
{
NodeVisitor.DepthVisit(startVertex, t => GetNextVertexs(t), visitAction);
}
public void DepthVisit(Action<TVertex> visitAction)
{
NodeVisitor.DepthVisit(GetRoot(), t => GetNextVertexs(t), visitAction);
}
private class GraphNode : INode
{
private IList<INode> nodes = new List<INode>();
public string Id { get; set; }
public void AddNext(INode node)
{
nodes.Add(node);
}
public IEnumerable<TNode> GetNextNodes<TNode>() where TNode : INode
{
return nodes.Cast<TNode>();
}
}
}
單元測試代碼：
