liang14658fox

Appearance

深度优先遍历有向无环图 ​

深度优先遍历是一种用于遍历或搜索树或图的算法，它通过从根节点开始依次访问每个子节点，直到到达没有子节点的节点为止，然后返回到上一个未访问完的节点，继续访问其未访问的子节点。在此过程中，每个节点只被访问一次。

深度优先遍历有两种常见的实现方式：递归和迭代。

如果有向无环图的数据存储在一个对象数组中，可以先遍历数组，将所有节点初始化为active为true，同时给每个节点设置一个id属性，方便后面的操作。

然后再遍历一次数组，根据每个节点对象中提供的子节点信息，将节点之间的关联关系建立起来。这样就可以在遍历时方便地找到每个节点的子节点了。

最后使用递归方式，从根节点开始遍历整个DAG。在递归过程中，检查每个节点的active属性值，如果为f则将其所有子节点的active属性都设为f，然后继续遍历子节点，以此类推，直至遍历完整个DAG。

下面是一个使用JavaScript实现的示例代码：

javascript
// 定义一个有向无环图
let graph = [
    {
        id: 'A',
        children: ['B', 'C']
    },
    {
        id: 'B',
        children: ['D', 'E']
    },
    {
        id: 'C',
        children: ['F']
    },
    {
        id: 'D',
        children: ['G']
    },
    {
        id: 'E',
        children: ['G', 'H']
    },
    {
        id: 'F',
        children: []
    },
    {
        id: 'G',
        children: []
    },
    {
        id: 'H',
        children: []
    }
];

// 将节点数组转换为节点对象字典，方便查找
let nodes = {};
for (let node of graph) {
    nodes[node.id] = { id: node.id, active: true, children: [] };
}

// 建立节点之间的关联关系
for (let node of graph) {
    let parent = nodes[node.id];
    for (let childId of node.children) {
        let child = nodes[childId];
        parent.children.push(child);
    }
}

// 遍历DAG的函数
function traverseDAG(node) {
    if (!node.active) {
        // 如果当前节点的active属性为f，将其所有子节点的active属性也设置为f
        for (let child of node.children) {
            child.active = false;
            traverseDAG(child);
        }
    } else {
        // 如果当前节点的active属性为t，继续遍历其子节点
        for (let child of node.children) {
            traverseDAG(child);
        }
    }
}

// 示例：从起始节点A开始遍历整个DAG
traverseDAG(nodes['A']);
// 定义一个有向无环图
let graph = [
    {
        id: 'A',
        children: ['B', 'C']
    },
    {
        id: 'B',
        children: ['D', 'E']
    },
    {
        id: 'C',
        children: ['F']
    },
    {
        id: 'D',
        children: ['G']
    },
    {
        id: 'E',
        children: ['G', 'H']
    },
    {
        id: 'F',
        children: []
    },
    {
        id: 'G',
        children: []
    },
    {
        id: 'H',
        children: []
    }
];

// 将节点数组转换为节点对象字典，方便查找
let nodes = {};
for (let node of graph) {
    nodes[node.id] = { id: node.id, active: true, children: [] };
}

// 建立节点之间的关联关系
for (let node of graph) {
    let parent = nodes[node.id];
    for (let childId of node.children) {
        let child = nodes[childId];
        parent.children.push(child);
    }
}

// 遍历DAG的函数
function traverseDAG(node) {
    if (!node.active) {
        // 如果当前节点的active属性为f，将其所有子节点的active属性也设置为f
        for (let child of node.children) {
            child.active = false;
            traverseDAG(child);
        }
    } else {
        // 如果当前节点的active属性为t，继续遍历其子节点
        for (let child of node.children) {
            traverseDAG(child);
        }
    }
}

// 示例：从起始节点A开始遍历整个DAG
traverseDAG(nodes['A']);

这个示例中先将有向无环图转换为节点对象字典，方便后续查找节点。然后使用两次遍历，一次建立节点之间的关联关系，一次进行DAG的遍历。

为只有父节点信息的节点添加child ​

如果对象数组中，每个节点只有父节点的name信息，而没有子节点的信息，通过什么方式才能给节点添加他们的子节点信息呢？

可以使用循环遍历这个对象数组，在遍历每个节点的同时，根据它们的父节点name信息来找到它们的子节点，然后将子节点信息添加到相应的节点中。具体步骤如下：

  1. 创建一个空的子节点存储对象。
  2. 在循环中遍历每个节点。
  3. 对于每个节点，在循环中再次遍历整个对象数组。
  4. 对于每个对象数组中的节点，检查它的父节点name信息是否与当前节点的name信息相同。
  5. 如果是，将这个节点添加到当前节点的子节点数组中。
  6. 继续遍历，直到整个对象数组中的所有节点都被处理完毕。
  7. 返回处理完毕后的对象数组，每个节点都包含相应的子节点信息。

以下是一个示例实现：

javascript
// 假设你的对象数组名为nodeArray，每个节点只有name和parentName信息
// 创建空的子节点存储对象
let nodesWithChildren = [];

// 遍历每个节点
for (let i = 0; i < nodeArray.length; i++) {
    // 创建一个新的对象，将当前节点信息添加到其中
    let currentNode = {
        name: nodeArray[i].name,
        children: []
    };

    // 遍历整个对象数组，查找当前节点的子节点
    for (let j = 0; j < nodeArray.length; j++) {
        if (nodeArray[j].parentName === currentNode.name) {
            // 如果找到了子节点，就将其添加到当前节点的子节点数组中
            currentNode.children.push(nodeArray[j]);
        }
    }

    // 将包含子节点信息的当前节点添加到新的存储对象中
    nodesWithChildren.push(currentNode);
}

// 返回包含子节点信息的新对象数组
return nodesWithChildren;
// 假设你的对象数组名为nodeArray，每个节点只有name和parentName信息
// 创建空的子节点存储对象
let nodesWithChildren = [];

// 遍历每个节点
for (let i = 0; i < nodeArray.length; i++) {
    // 创建一个新的对象，将当前节点信息添加到其中
    let currentNode = {
        name: nodeArray[i].name,
        children: []
    };

    // 遍历整个对象数组，查找当前节点的子节点
    for (let j = 0; j < nodeArray.length; j++) {
        if (nodeArray[j].parentName === currentNode.name) {
            // 如果找到了子节点，就将其添加到当前节点的子节点数组中
            currentNode.children.push(nodeArray[j]);
        }
    }

    // 将包含子节点信息的当前节点添加到新的存储对象中
    nodesWithChildren.push(currentNode);
}

// 返回包含子节点信息的新对象数组
return nodesWithChildren;

浅拷贝

利用浅拷贝特性，不需要转换数组赋值给原来的data

转换为数组

将对象结构转换为数组需要图形结构扁平化相关操作，而不是仅仅const result = Object.values(nodes);