C#,結構為圖型,可以使用任意型別的變數存放資料。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
public class mapNode<T>
{
public List<mapNode<T>> neighbors = new List<mapNode<T>>();
public T data;
}
public class mapNodePathFinding<T>
{
List<mapNode<T>> path, perfactPath, blockWay;
int smallestDistance;
public List<mapNode<T>> getPath(mapNode<T> start, mapNode<T> end)
{
smallestDistance = int.MaxValue;
blockWay = new List<mapNode<T>>();
path = new List<mapNode<T>>();
perfactPath = null;
var node = start;
if (start == end)
{
path.Add(start);
return path;
}
else
{
findNode(start, end);
path = perfactPath;
}
return path;
}
private void findNode(mapNode<T> node, mapNode<T> target)
{
if (path.Contains(node) || blockWay.Contains(node))
{
return;
}
path.Add(node);
if (path.Count < smallestDistance)
{
if (node==target)
{
smallestDistance = path.Count;
perfactPath = new List<mapNode<T>>();
perfactPath.AddRange(path);
path.Remove(node);
return;
}
else
{
if (node.neighbors.Count==0)
{
blockWay.Add(node);
}
else
{
foreach (var nextNode in node.neighbors)
{
findNode(nextNode, target);
}
}
}
}
path.Remove(node);
}
}