WHCSRL 技术网

2021-10-21

并检查收藏

找出图片中是否有环
在此处插入图片描述

//结合查看里面是否有环照片
//作为测试,先定义一个图
//现在有6个节点‘0 1 2 3 4 5’,图显示了这6个节点之间的连接
让图 = [[0, 1], [1, 2], [1, 3], [2, 5], [2, 4], [3, 4]];

//定义一个数组来存储每个节点的父节点 parent[i] 存储第i个节点的父节点,初始值为-1
让父母= [];
for (让 i = 0; i <6; i ++) {
    父推(-1);
}

//为了避免生成的联合树的高度太高,在寻找根节点时消耗过多的性能,设置rank数组
//rank[i] 存储 i 为根节点时树的高度。初始高度为0
让等级 = [];
for (让 i = 0; i <6; i ++) {
    排名.push(0);
}

//找到一个节点的根节点
const findRoot = (i, parent) => {
    让根 = i;
    而(父 [root] !== -1){
        根 = 父 [根];
    }
    返回根;
}

//如果两个节点可以有相同的根节点,则表示这两个节点在一个集合中相互连接
//合并连接节点:连接这两点的根节点
const union_vertices = (x, y, parent, rank) => {
    让 root_x = findRoot(x, parent);
    让 root_y = findRoot(y, parent);
    如果(root_x === root_y){
        //如果发现x和y的根节点,root_x和root_y是同一个点,说明图已经形成环
        返回 1;
    } 别的 {
        //以root_x和root_y为根节点查看树的高度,较高的为新树的根节点。新树的高度保持不变
        如果(排名[root_x]> 排名[root_y]){
            父 [root_y] = root_x;
        } else if (rank[root_x]  {
    for (let i = 0; i 
  • 1
  • 2
  • 3
  • 4< /li>
  • 5
  • 6
  • < li style="color: rgb(153, 153, 153);">7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • li> li>
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • li> li>
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36< /li >
  • 37
  • 38
  • < li style ="color: rgb(153, 153, 153);">39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • li>
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60< /li>
  • 61
  • 62
  • < /ul>

    ref:
    https://www.youtube.com/watch?v=YKE4Vd1ysPI
    https://www.youtube.com/watch?v=gpmOaSBcbYA
    https:// /www.youtube.com/watch?v=zos–xohLT0

推荐阅读