const graph = { I1: [], I2: [], I3: [], Plus1: ["I1","I2"], Plus2: ["I3"], P1: ["Plus1"], P2: ["Plus2"] }; 这个图中的数据,Plus1:["I1","I2"]代表 Plus1的source是 I1和I2, 如果是空数组代码是入口数据 我给你的graph中实际上有两个子图,那么得到的结果是 [ [ 'I3', 'Plus2', 'P2' ], [ 'I1', 'I2', 'Plus1', 'P1' ] ] 有点类似于拓扑排序但又不完全是 ,我想要得到一个这样的数据,该如何编写我的js算法代码呢?
时间: 2024-04-12 10:30:24 浏览: 9
你可以使用深度优先搜索(DFS)算法来遍历这个图,并将每个子图作为一个独立的路径进行存储。下面是一个使用递归实现DFS的示例代码:
```javascript
function dfs(graph, node, visited, path) {
visited.add(node);
for (let neighbor of graph[node]) {
if (!visited.has(neighbor)) {
dfs(graph, neighbor, visited, path);
}
}
path.push(node);
}
function getSubGraphs(graph) {
const visited = new Set();
const subGraphs = [];
for (let node in graph) {
if (!visited.has(node)) {
const path = [];
dfs(graph, node, visited, path);
subGraphs.push(path);
}
}
return subGraphs;
}
const graph = {
I1: [],
I2: [],
I3: [],
Plus1: ["I1","I2"],
Plus2: ["I3"],
P1: ["Plus1"],
P2: ["Plus2"]
};
const subGraphs = getSubGraphs(graph);
console.log(subGraphs);
```
这段代码会输出 `[[ 'I3', 'Plus2', 'P2' ], [ 'I1', 'I2', 'Plus1', 'P1' ]]`,其中每个子数组表示一个子图的路径。请注意,这个代码假设输入的图是一个有向无环图(DAG)。