>

요소 목록이 있으며 각 요소에는 ID와 부모 ID가 있습니다. 내가 원하는 것은이 '계층 구조'에 루프가 있는지 감지하고 루프를 시작하는 ID를 표시하는 것입니다.

list = [
  {
    id: '1',
    parent: '2'
  },
  {
    id: '2',
    parent: '3'
  },
  {
    id: '3',
    parent: '4'
  },
    {
    //This id is causing the loop
    id: '4',
    parent: '1'
  }
]

루프가 없을 때 작동하지만 루프에서는 작동하지 않는 트리를 빌드하려고 시도했습니다.

function treeify(list, idAttr, parentAttr, childrenAttr) {
    if (!idAttr) idAttr = 'id';
    if (!parentAttr) parentAttr = 'parent';
    if (!childrenAttr) childrenAttr = 'children';
    var treeList = [];
    var lookup = {};
    list.forEach(function(obj) {
        lookup[obj[idAttr]] = obj;
        obj[childrenAttr] = [];
    });
    list.forEach(function(obj) {
        if (obj[parentAttr] != null) {
            lookup[obj[parentAttr]][childrenAttr].push(obj);
        } else {
            treeList.push(obj);
        }
    });
    return treeList;
};

루프가있을 때도 감지 할 수 없습니다.

루프가 뒤에있는 데이터를 수정하게하는 요소의 ID를 반환하고 싶습니다.


  • 답변 # 1

    자손을 방문하는 동안 방문한 노드를 감지하기 위해 흰색-회색-검정 색을 적용 할 수 있습니다 (그래프를 부모-자식 쌍 목록으로 단순화했습니다) :

    graph = [
        [2, 1],
        [3, 2],
        [1300023, 3],
        [1, 1300023],
    ];
    
    colors = {}
    
    function visit(vertex) {
        if (colors[vertex] === 'black') {
            // black = ok
            return; 
        }
        if (colors[vertex] === 'grey') {
            // grey = visited while its children are being visited
            // cycle!
            console.log('cycle', colors); 
            return; 
        }
        // mark as being visited
        colors[vertex] = 'grey';
        // visit children
        graph.forEach(edge => {
            if (edge[0] === vertex)
                visit(edge[1]);
        });
        // mark as visited and ok
        colors[vertex] = 'black'
    }
    visit(1)
    
    

    이 접근법의 좋은 예 : https://algorithms.tutorialhorizon.com/graph-detect-cycle-in-a-directed-graph-using-colors/

  • 답변 # 2

    모두 수집 할 수 있습니다 방문한 노드를 가져 와서 모든 노드를 필터링하고 필터링합니다.

    무한 배열은 순환 참조를 일으키는 모든 노드를 포함합니다.
    function isCircular(id, visited = []) {
        return visited.includes(id)
            || Object.keys(links[id]).some(k => isCircular(k, visited.concat(id)));
    }
    var list = [{ id: '1', parent: '2' }, { id: '2', parent: '3' }, { id: '3', parent: '4' }, { id: '4', parent: '1' }],
        links = {},
        infinite = [];
        
    list.forEach(({ id, parent }) => {
        links[parent] = links[parent] || {};
        links[parent][id] = true;
    });
    
    infinite = list.filter(({ id }) => isCircular(id));
    console.log(links);
    console.log(infinite);
    
    
    .as-console-wrapper { max-height: 100% !important; top: 0; }
    
    

관련 자료

  • 이전 파이썬이 왜 내 사전을 그렇게 주문합니까?
  • 다음 xml - 현재 요소의 하위 요소/하위 속성을 다음 요소의 하위 요소/하위 속성과 비교