graph

graph.ts

class GraphNode {
  public neighbors: Set<GraphNode>
  public color: string
  constructor(public label) {
    this.label = label;
    this.neighbors = new Set();
    this.color = null;
  }
}

/**
 * 给图上色，相邻节点不能同色
 */
function colorGraph(graph: GraphNode[], colors: string[]) {
    
  graph.forEach(graphNode => {

    if (graphNode.neighbors.has(graphNode)) {
      throw new Error('detect loop')
    }

    // 将相邻节点的颜色存放，相当于加入黑名单
    const adjacentColor: Set<string> = new Set()
    graphNode.neighbors.forEach(neighborNode => {
      if (neighborNode.color) {
        adjacentColor.add(neighborNode.color)
      }
    })

    for (let i = 0, len = colors.length; i < len; i++) {
      if (!adjacentColor.has(colors[i])) {
        graphNode.color = colors[i]
        break;
      }
    }
  })
}