我刚刚开始使用图论.我无法弄清楚如何使用链表编码邻接列表.例如,如果我有这个图(未定向):
A--------B
| /|\
| / | \
| / | \
| / | \
| / | \
| / | \
| / | \
C E-------D
我该如何编码？我知道如何使用邻接矩阵,但如何使用邻接列表和链接列表(c ++)来编码它？
我遇到了这个问题:
http://www.iarcs.org.in/inoi/contests/oct2005/Advanced-2.php
问题基本上是图表.您将获得一个包含多达70个节点的图形,以及一个邻接矩阵,用于说明两个节点之间存在多少条边.每条边都是双向的.
现在的问题是问你找出的任意两个节点N1和N2之间的固定长度的N个不同路径的数量.路径可以重复.即,路径可以通过已包含的节点.
最天真的算法是运行广度优先搜索并检查Nth层中出现的N2数量,其中BFS树以N1为根.但这不会奏效.
怎么去呢？