编辑代码

/**
 * 图节点接口，定义了图中节点的基本属性。
 */
export interface GraphNode {
  id: string; // 节点唯一标识
  width?: number; // 节点宽度（可选）
  height?: number; // 节点高度（可选）
  selected?: boolean; // 节点是否被选中（可选）
  logLevel?: number; // 日志级别（可选）
}

/**
 * 图边接口，描述了图中边的连接信息。
 */
export interface GraphEdge {
  source: string; // 边的起始节点ID
  target: string; // 边的目标节点ID
}

/**
 * 并查集类，用于处理图中元素的连通性问题。
 */
class UnionFind {
  private parent: { [key: string]: string }; // 记录每个节点的父节点
  private rank: { [key: string]: number }; // 记录树的高度，优化合并操作

  /**
   * 初始化并查集实例，构造方法中创建空的父节点记录和排名记录。
   */
  constructor() {
    this.parent = {};
    this.rank = {};
  }

  /**
   * 查找节点所属集合的代表元素（根节点）。
   * @param node 待查找的节点ID
   * @returns 节点所在集合的根节点ID
   */
  find(node: string): string {
    if (!(node in this.parent)) {
      this.parent[node] = node;
      this.rank[node] = 0;
    }
    if (this.parent[node] !== node) {
      this.parent[node] = this.find(this.parent[node]); // 路径压缩
    }
    return this.parent[node];
  }

  /**
   * 合并两个集合。
   * @param node1 集合1的代表元素ID
   * @param node2 集合2的代表元素ID
   */
  union(node1: string, node2: string): void {
    const root1 = this.find(node1);
    const root2 = this.find(node2);

    if (root1 !== root2) {
      // 按秩合并
      if (this.rank[root1] > this.rank[root2]) {
        this.parent[root2] = root1;
      } else if (this.rank[root1] < this.rank[root2]) {
        this.parent[root1] = root2;
      } else {
        this.parent[root2] = root1;
        this.rank[root1]++;
      }
    }
  }
}

/**
 * 判断新边添加到图中是否会形成环。
 * @param edges 当前图的所有边
 * @param newEdge 待添加的新边
 * @returns 如果添加新边不会形成环则返回true，否则返回false
 */
function canAddEdge(edges: GraphEdge[], newEdge: GraphEdge): boolean {
  const unionFind = new UnionFind();

  // 处理所有已有边，构建并查集
  for (const edge of edges) {
    const { source, target } = edge;
    if (unionFind.find(source) === unionFind.find(target)) {
      // 图中已存在环，跳过此边
      continue;
    }
    unionFind.union(source, target);
  }

  // 检查新边是否会形成环
  const { source, target } = newEdge;
  if (unionFind.find(source) === unionFind.find(target)) {
    // 添加新边会形成环
    return false;
  }

  // 添加新边不会形成环
  return true;
}

// 示例使用：
const nodes: GraphNode[] = [
  { id: 'A' },
  { id: 'B' },
  { id: 'C' },
  { id: 'D' },
];

const edges: GraphEdge[] = [
  { source: 'A', target: 'B' },
  { source: 'B', target: 'C' },
];

const newEdge: GraphEdge = { source: 'A', target: 'C' };
console.log(canAddEdge(edges, newEdge)); // 输出false，因为添加这根边会形成环

const anotherNewEdge: GraphEdge = { source: 'C', target: 'D' };
console.log(canAddEdge(edges, anotherNewEdge)); // 输出true，因为添加这根边不会形成环