我正在阅读教科书Introduction to Algorithms
,CLRS
我想在 c 中实现mst
usingkruskal
算法,我想知道的是,我应该使用哪个图形实现,邻接表还是邻接矩阵?edges
我认为在使用邻接表时排序并不直观,当edge
像这样定义邻接表时,邻接表中的表示令人困惑:
typedef struct tagAdjList
{
int endPointIndex;
struct tagAdjList * next;
}AdjNode, *AdjList, *AdjPNode;
在对边缘进行排序时,我想使用一个指针数组来指向上面定义的节点,问题是上面定义的结构找不到start point
边缘的,但是end point
. 所以我改变了这样的结构:
typedef struct tagAdjList
{
int startPointIndex;
int endPointIndex;
struct tagAdjList * next;
}AdjNode, *AdjList, *AdjPNode;
我想问的是:这样定义邻接表可以吗?还是有更好的做法?或者我应该使用邻接矩阵(因为我看到有些人在搜索互联网时使用矩阵实现 kruskal)?为什么?对不起英语不好。任何帮助将不胜感激。