这个项目的截止日期很快就会结束,我没有太多时间来处理剩下的事情.因此,我正在寻找最简单的算法来实现Graph结构上的一些操作,而不是寻找最好的(可能更复杂/耗时)算法.
我需要做的操作如下:
- 在给定距离X的情况下列出图形网络中的所有用户
- 给定距离X和关系类型,列出图形网络中的所有用户
- 在给定一种关系的情况下,计算图形网络上2个用户之间的最短路径
- 计算图形网络上2个用户之间的最大距离
- 计算图形网络上最远的连接用户
关于我的Graph实现的一些注意事项:
- 边缘节点有2个属性,一个是类型
char,另一个是属性int.它们分别代表关系和重量的类型.
- 图表使用链接列表实现,包括顶点和边.我的意思是,每个顶点指向下一个顶点,每个顶点也指向不同链表的头部,即该特定顶点的边.
我知道我需要做什么:
- 我不知道这是否是最简单的,如上所述,但对于2个用户之间的最短路径,我相信Dijkstra算法是人们似乎经常推荐的,所以我想我会继续这样做.
- 我一直在搜索和搜索,我发现很难实现这个算法,有没有人知道任何教程或易于理解的东西所以我可以自己实现这个算法？如果可能的话,使用C源代码示例,它会有很大帮助.我看到许多带有数学符号的例子,但这让我更加困惑.
- 如果我将图形"转换"为邻接矩阵来表示链接权重和关系类型,您认为这会有所帮助吗？是否更容易执行该算法而不是链接列表？我可以轻松地实现一个函数来在需要时进行转换.我这样说是因为我觉得在阅读了几页关于这个主题之后会更容易,但我可能错了.
- 我对其他4个操作,建议没有任何想法？