我正在尝试一个社交图问题,它将分析图并回答关于实体之间的连接类型的问题。所谓社会图,我指的是代表社会世界各实体之间友谊的图。顶点是实体,边是两个实体之间的友谊,例如:
1跳:1度
2跳:2度
3跳:3度等。
在这里,我有5个人,阿比,卡皮尔,哈里,伊莎和贾亚。
哈里是卡皮尔、贾亚和伊莎的朋友。
阿比是卡皮尔的朋友。
现在,我要编写一个函数连接(实体1,实体2),它将返回它们之间的连接类型。
例如-如果我写连接(Kapil,Isha),则返回2
同样,连接(Abhay,Jaya)将返回3
如果是断开连接的图,则在没有连接函数的情况下应返回0。
我想设计Connection()函数,它的工作方式如下:-input::Abhay Jaya output::Degree:3
我理解它是BFS算法的一个应用,但是不能成功地实现它。我怎么才能得到C类伪代码或C/C++代码呢?
最佳答案
你应该看看一些图算法来解决它。这些算法不是特定于语言的,因此您可以在线获取想法和实现/查找实现。
您可以使用两种方案解决它:
使用Floyd Warshall
使用Dijkstra