原书出处
大数据日知录_架构与算法
14 图数据库:架构与算法
算法运行经过以下四个阶段。 阶段一:对于二部图中左端尚未匹配的节点,向其邻接节点发出消息,要求进行匹配,之后转入非活跃状态。 阶段二:对于二部图中右端尚未匹配的节点,从接收到的请求匹配消息中随机选择一个接收,并向接收请求的左端节点发出确认信息,之后主动转入非活跃状态。 阶段三:左端尚未匹配的节点接收到确认信息后,从中选择一个节点接收,写入匹配节点ID以表明已经匹配,然后向右端对应的节点发送接收请求的消息。左端节点已经匹配的节点在本阶段不会有任何动作,因为这类节点在第一阶段中根本就没有发送任何消息。 阶段四:右端尚未匹配的节点至多选择一个阶段三发过来的请求,然后写入匹配节点ID以表明已经匹配。 通过上述类似于两次握手的四个阶段的不断迭代,即可获得一个二部图最大匹配结果。
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/大数据日知录_架构与算法/_epub-src/OEBPS/text00019.html
EPUB SHA-256:e45b74c4bdd8959aef24f2a5183280eb73ec5f173108f8679a4bbf44bbd5b34d