Facebook User Group and Bipartite Graph

The Problem

大家都知道Facebook用户都是双向的好友,a是b的好友,那么b一定是a的好友,现在给定一个用户列表,其中有些用户是好友,有些不是,请判断,这些用户是否可以划分为两组,并且每组内的用户,互相都不是好友。如果能,请给出这个划分。

例子1:

1
2
3
用户:{1, 2, 3}
好友关系:1-2, 2-3
划分:{1,3} {2}

例子2:

1
2
3
用户{1,2,3,4}
好友关系:1-2, 2-3, 3-4,4-1
划分:{1, 3} {2, 4}

Analysis

有很多面试题比较直接,看到题目,面试者很自然的就想到用什么方法,这时候,往往面试官要的是bug-free的code;还有一些问题,不那么直接,那就是考察,应试者的分析问题、分解问题的能力。往往是一个相对复杂的问题,分解为我们见过的、相对简单的问题;还有一类问题,从实际当中来,这就需要有建模的能力,也可以说是把问题抽象出来的能力,然后才是分解成小的问题等。这样的题目,能够全面的考察应试者的能力。例如Facebook这个题目。

这个面试题来自Facebook的实际问题。像在我们国内,有很多同学在做新浪微博的数据挖掘,好友推荐、关系预测、圈子发现、转发分析、影响力分析等等,这些都是很实际、很有用的问题,每一个问题,都可以作为一个值得深入探讨的面试题。大家可以思考一下:这个问题可以归结为一个什么问题?排序?查找?树?图?确定这个,大概的解决方法,也基本可以确认。

相对而言,这个面试题目比较简单。因为建模的部分,已经在题目中给出了。简单思考,就发现是一个图分割的问题,既然是图,无非也就是深度优先,或者宽度优先遍历了,递归或者非递归的实现。Facebook的好友关系是双向的,意味着是无向图(新浪微博,twitter都是有向图)。然后,要把图划分为两组,这两组满足什么条件呢?组内没有边,组间有边。了解图结构的,立刻会想到,这就是一个二分图。

那问题很明显了,就是判断Facebook好友关系构成的图,是否是一个二分图?如果是,请找到这个划分。就是二分图判断+找到一个划分即可。

根据二分图的特性,一条边上的两个点,肯定是属于不同的组。如果它们出现在同一个组中,肯定就不是二分图了。怎么判断,一条边上的两个点,分属于不同的组呢?我们需要遍历图,如果找到一条边,两个节点,都在同一组,则不是二分图;如果图遍历完成之后,没有找到这样的边,则是二分图。我们在遍历的过程中,我们需要区分,一条边的两个节点分属于不同的组,这里我们用到了染色法。核心思想如下:

从某一个点开始,将这个节点染色为白色,并且开始广度优先遍历,找到与其相邻的节点,如果是二分图,相邻节点的颜色都应该不同。如果是黑色,则不变;如果是无色,则染成黑色;如果是白色,也就是同色,程序退出。当图遍历完毕时,没有相邻节点同色的,则是二分图,标记为白色和黑色的两组就是一个划分。

Step by Step Explanation

E.g.1

1
2
3
用户{1,2,3,4}
好友关系:1-2, 2-3, 3-4,4-1
划分:{1, 3} {2, 4}
steps vertex visiting neighbours queue
1 1: white 2: black, 4: black 2, 4
2 2: black 1: white, 3: white 4, 3
3 4: black 1: white, 3: white 3
4 3: white 2: black, 4: black empty

队列空,结束遍历。找到划分{1,3}白 {2,4}黑。

E.g.2
再看一个不是二分图的例子:

1
2
用户{1,2,3,4}
关系:1-2,1-3,1-4,2-3,3-4

判断步骤如下:

steps vertex visiting neighbours queue
1 1: white 2: black, 3: black, 4: black 2, 3, 4
2 2: black 1: white, 3: white (but is already black) 3, 4

发现3矛盾了,则上面的关系,不够成二分图。


借鉴于’待字闺中’的微信公众号