如何知道是否有一轮是由父母引起的（A=>B=>C=>A）

Question

我有以下结构：

[Employee]
ID
Manager1ID
Manager2ID

场景：

我想进行验证以确保所选的 Manager1 或 Manager2 不会导致回合。换句话说，我想知道这种情况是否存在：

A 的经理是 B & B 的经理是 C，C 的经理也是 A // 无效

A =>; B => C=> A

告诉用户 A 不是 C 的有效经理，因为 C 已经是 A 的经理 。

---

问题：

我想在一个 while 循环中将管理器作为树中的父级进行检查，当我在列表中找到所选的管理器时，我知道它是无效的。 （对于 Manager1 和 Manager2 的两个列表有两个循环）

问题是每个员工可能有两个经理，并且在这样的情况下可能存在一轮：

A =>; B（经理1）=> C（经理2）=>

Which 无法签入我建议的解决方案。

任何想法！

Answer 1

您尝试在有向图中找到循环 。

Answer 2

从有问题的员工开始，对经理组进行广度优先搜索，并不断累积您在列表中遇到的经理列表。每次向列表中添加条目时，请检查它是否会创建重复项。如果是这样，则意味着您已达到您想要检查的条件。继续此过程，直到遇到重复条件或到达没有管理器的节点

Answer 3

使用递归函数：

List<Employee> lineage = new List<Employee>();
Validate(theUser, lineage);

public void Validate(Employee employee, List<Employee> lineage)
{
  if (lineage.Contains(employee))
     throw new InvalidOperationException("Circular graph");

  lineage.Add(employee);

  if (employee.Manager != null)
    Validate(employee.Manager, lineage)
}

Answer 4

我为n个被举报者提供了一个完整的通用解决方案，这比被举报者更符合逻辑。如果您想将报告者重命名为经理，您可以这样做。
您可以修改遍历以满足您的需要。我已经通过循环和不循环测试了这一点。看起来效果很好。让我知道这是否适合您。

using System;
using System.Collections.Generic;


namespace GenericDictionary
{
    class Program
    {
        static void Main(string[] args)
        {
            Employee employee = new Employee("Employee", null);
            Employee manager = new Employee("Manager", employee);
            Employee CEO = new Employee("CEO", manager);
            CEO.AddReportee(new Employee("Manager2", employee));

            // Uncomment this line to see exception in action
            // employee.AddReportee(CEO);
            try
            {
                CEO.DisplayReportees();
            }
            catch (InvalidOperationException ex)
            {
                Console.WriteLine();
                Console.WriteLine("***** Exception: " + ex.Message + " *****");
            }

            Console.ReadLine();
        }

        public class Employee
        {
            public List<Employee> Reportees { get; private set; }
            public string Name { get; private set; }
            public Employee(string name, Employee reportee)
            {
                this.Reportees = new List<Employee>();
                this.Name = name;
                this.Reportees.Add(reportee);
            }
            public void AddReportee(Employee reportee)
            {
                Reportees.Add(reportee);
            }
            int indentationCount = 0;
            List<Employee> traversedNodes = new List<Employee>();
            void DisplayReportees(Employee employee)
            {
                traversedNodes.Add(employee);
                for (int i = 0; i < indentationCount; i++)
                    Console.Write(" ");
                Console.WriteLine(employee.Name);
                indentationCount = indentationCount + 3;

                foreach (Employee reportee in employee.Reportees)
                {
                    if (AlreadyTraversed(reportee))
                        throw new InvalidOperationException("Circular graph at node " + reportee.Name);
                    if (reportee != null)
                        DisplayReportees(reportee);
                }
                indentationCount = indentationCount - 3;
                traversedNodes.Remove(employee);
            }

            bool AlreadyTraversed(Employee employee)
            {
                return traversedNodes.Contains(employee);
            }

            public void DisplayReportees()
            {
                DisplayReportees(this);
            }
        }
    }
}

Answer 5

使用以下递归函数：

Boolean CheckManagers(Employee emp)
{

    if ((emp.Manager1ID.HasValue && emp.Manager1ID == emp.ID) ||
       (emp.Manager2ID.HasValue && emp.Manager2ID == emp.ID)) return false;

    return 
    (
        (!emp.Manager1ID.HasValue || (emp.Manager1ID.HasValue && CheckManagers((Employee) emp.Manager1)) && 
        (!emp.Manager2ID.HasValue || (emp.Manager2ID.HasValue && CheckManagers((Employee) emp.Manager2))
    );

}