c# - 在这种情况下如何检查链表是否有循环

Question

必须创建一个链接列表，我们将在其中添加相互依赖或不依赖的部门。

输入将是部门名称，后跟它们所依赖的部门名称，有些可以后跟空字符串，这意味着它们不依赖于任何部门。

所以输出将首先是第二个部门，依此类推

1. 一个部门不能靠自己（小心）

2. 必须查找部门是否具有循环依赖（问题）

输入

销售量

营销账户

财务销售

所以输出将是

销售财务账户营销

输入

销售与市场营销

营销账户

账户销售

输出

错误它不能有循环依赖

尝试使用以下代码查看我的链接列表是否有循环

private bool DoesItHasLoops()
        {
            var fast = myLinkedList.First;
            var slow = myLinkedList.First;
            while (fast != null && fast.Next != null)
            {
                fast = fast.Next.Next;
                slow = slow.Next;
                if (slow == fast)
                    return true;


            }
            return false;
        }

它不工作，无法找到循环。

下面的代码是我在链表中​​添加字符串的方式。

private LinkedList<strings> myLinkedList;

public void AddDepartments(string[] input)
{
   if (input.Count() > 1)
      {
        if (myLinkedList.Contains(input[0]))  
         {

          myLinkedList.AddBefore(adjList.Find(input[0]), input[1]);

          }
        else
         {
          myLinkedList.AddLast(input[1]);                            
          myLinkedList.AddLast(input[0]);
         }
      }
    else
    {
     myLinkedList.AddLast(input[0]);
     myLinkedList.AddLast(string.empty());

     }
}

这适用于所有情况，只有循环情况它不起作用

标签： c#.netlinked-list

Answer 1

在我看来，识别这些循环的最简单方法是找到那些具有依赖关系的部门在某个时候也被列为依赖关系本身的那些，并遍历它们之间的依赖关系链以查看它们是否连接。也就是说，您的架构似乎有点不对劲。我将创建一个对象来保存该部门及其依赖项列表以及一个标志，以确定它是否具有这样的循环引用：

public class Department
{
    public int Id { get; set; }
    public string Name { get; set; }
    public IList<int> Dependencies { get; set; }
    public bool HasCircularReferences { get; set; } 
}

然后，您传入一个部门列表并遍历每个部门，并找到将该部门列为依赖项的其他部门。然后，您通过依赖链从这些方面进行工作，以查看您是否最终回到当前部门。您可以使用这样的循环（请注意，这是一个静态方法，因为我在控制台应用程序中对其进行了测试）：

private static void GetDependents(IList<int> dependencies, int seed)
{
    foreach (var dependent in dependencies)
    {
        var dependentDept = departments.Where(d => d.Id == dependent).FirstOrDefault();
        if (dependentDept.Dependencies.Count > 0)
        {
            if (dependencies.Contains(seed) || dependentDept.HasCircularReferences)
            {
                SetCircularReferenceFlag(seed, true);
                break;
            }
            GetDependents(dependentDept.Dependencies, seed);
        }
        else
        {
            SetCircularReferenceFlag(seed, false);
            break;
        }
    }
}

这使用 SetCircularReferenceFlag 方法在部门上设置 HasCircularReferences 标志，该方法是：

private static void SetCircularReferenceFlag(int departmentId, bool hasCircularReferences)
{
    var seedDept = departments.Where(d => d.Id == departmentId).FirstOrDefault();
    seedDept.HasCircularReferences = hasCircularReferences;
}

然后可以为列表中的每个部门调用 GetDependents 方法，如下所示：

foreach (var department in departments)
{
    GetDependents(department.Dependencies, department.Id);
}

使用上面定义的 Department 对象，已将 Departments 设置为如下所示：

private static List<Department> departments = new List<Department>
{
    new Department
    {
        Id = 1,
        Name = "sales",
        Dependencies = new List<int>{ 2 }
    },
    new Department
    {
        Id = 2,
        Name = "accounts",
        Dependencies = new List<int>{ 3 }
    },
    new Department
    {
        Id = 3,
        Name = "marketing",
        Dependencies = new List<int>{ 1 }
     },
     new Department
     {
        Id = 4,
        Name = "finance",
        Dependencies = new List<int>{ 1 }
     }
 };

通过控制台应用程序运行它时，您会得到以下结果：