java - 从 BST 中删除多余的边缘
问题描述
我有一个 BST,如下所示。如何从 BST 中删除不需要的额外边缘?
1->2, 1->3, 2->4, 2->5, 3->5
应该删除 2->5 或 3->5
void BFS(int s)
{
// Mark all the vertices as not visited(By default
// set as false)
boolean visited[] = new boolean[V];
// Create a queue for BFS
LinkedList<Integer> queue = new LinkedList<Integer>();
// Mark the current node as visited and enqueue it
visited[s]=true;
queue.add(s);
while (queue.size() != 0)
{
// Dequeue a vertex from queue and print it
s = queue.poll();
System.out.print(s+" ");
// Get all adjacent vertices of the dequeued vertex s
// If a adjacent has not been visited, then mark it
// visited and enqueue it
Iterator<Integer> i = adj[s].listIterator();
while (i.hasNext())
{
int n = i.next();
if (!visited[n])
{
visited[n] = true;
queue.add(n);
}
}
}
}
解决方案
您拥有的不是树,而是有向无环图(DAG):
您正在寻找的算法是生成树算法。找到它的最简单方法之一是先遍历图形深度,并在找到它们时标记图形节点。如果一条边将您带到您已经看到的节点,请删除该边并继续。一旦你完成了深度优先遍历,剩下的图就是一棵树。
推荐阅读
- typescript - 如何使脚本在量角器中执行下一个它之前等待给定的时间跨度
- python - 根据两个条件预测某人离开的概率
- android - TabLayout 文本重力启动
- java - 我想根据从我的 firebase 数据库中获得的值打开一个特定的活动
- python - pyspark 数据帧的数据类型与 Presto 数据类型的详尽映射是什么?
- python - 如何获取要在请求中设置的 cookie 值?
- jenkins - 如果有两个 jenkins freestyleproject 具有相同的 scm git url,我如何仅触发特定的 freestyleproject?
- python - 检查两行并插入新行,如果它们在增加 starttime 后不匹配
- sql - 创建一个包含数组列 ms sql 的表
- youtube - 向现有视频 Youtube API 插入字幕,错误“请求不包含字幕轨道内容。”