Graph Problems
2024-02-25 00:04:42 # Algorithm #Graph

Graph题的一些trick

  • 无向图（undirected graph）需要使用visited数组来避免遍历时重复访问节点。
  • 一般build成List<Integer>[] = new ArrayList[n];

二分图

定义

A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.

简单来说就是一条边的两个vertex要分别属于不同的集合A和B。

如何判断二分图？

通常使用颜色标记法，根据定义，我们对每条边的两个nodes分别进行染色，例如染成红色（代表集合A），染成蓝色(代表集合B)。染色过程就是遍历过程，若在染色过程中发现冲突，即某个节点的邻居节点与该节点颜色相同，则说明并非二分图，相反如果遍历完整个图都未发现相邻两个节点有颜色相同的情况，则为二分图。

相关题

Prev
2024-02-25 00:04:42 # Algorithm #Graph
Next