С точки зрения времени выполнения, матрица смежности почти всегда превосходила списки.Реализация List будет использовать меньше памяти (пропорционально количеству ребер) для хранения графика.
Так что, если память имеет значение (это наверняка будет с разреженными графами с большим количеством узлов), используйте списки.Если время выполнения имеет значение, и график, вероятно, будет плотным, используйте матрицу смежности.