Подскажите пожалуйста, каким способом лучше всего задать граф на языке программирования C# для целей реализации алгоритма топологической сортировки?

Обычно это зависит от текущего способа представления графа. Самый простой способ - массив узлов с доп. свойством. Впрочем, если такие вопросы не решаются на ходу - имеет смысл воспользоваться готовыми решениями.

нужны входные данные

Двумерный массив

(3) двумерный массив - это как? Квадратная матрица, где по горизонтали это вершины, а по вертикали это в какую вершину ведут ребра из этой вершины? Я правильно понял?

структура описывающая узел, в ней вектор с указателями на другие узлы. Дополнительно в структуру можно добавлять другие данные необходимые для описания узла или расчетов

Лабораторка, 3й курс

(3) Если вершин более 40000 сколько оперативной памяти сожрет такой массив??? КРОКовский сервер рухнет - не то что хиленькй домашний ПК. (6) +1. Это в лабораторках на 3-м курсе так можно делать, а не в реальных задачах.

В 1С, к примеру, можно задействовать Соответствие/Структура, которое будет в качестве ключа использовать идентификатор вершины (ГУИД, Ссылка и т. д.) + каждая вершина будет содержать массив узлов, на которые эта вершина имеет выходы. В Си-Шарп явно есть аналоги этих коллекций в 1С.

map аналог соответствие
struct аналог структуры

(8) map имхо в java, в шарпе это Dictionary

графы тоже разные бывают
направленный или нет?

с весами или без

(0)В виде матрицы смежности, либо в виде списка рёбер

Я (правда в Паскале, давно) для алгоритма Мака задавал граф в виде списка дуг. Потом по этому списку формировал массив вершин с количееством входящих дуг - для последующего поиска очередной "топологически" подходящей вершины.
На выходе получался топологически упорядоченный список дуг, или список дуг, содержащий цикл(ы).
Где-то валялась реализация и на 1С. Если нужно - пишите на мыло (в профиле) - поищу.

(7) Алгоритмы обработки графов оперируют двумерными массивами, при 40к элементов это всего 1.6 ГБ данных, не надо никаких структур и соответствий

(14) "Алгоритмы обработки графов оперируют двумерными массивами" - совсем необязательно.

+(15) Мало того, что необязательно. Задача сортировки, как правило, предшествует более тяжёлым (в смысле вычислительной сложности) задачам, так что при выборе способа представления лучше ориентироваться именно на проблемы последующих задач. Если это, конечно, не лабы.

(16) Поиск кратчайших путей работает на двумерном массиве, по универу помню

Топологическая сортировка графа
Описание и реализация алгоритма
http://rain.ifmo.ru/cat/view.php/vis/graph-general/topological-sort-2007/algorithm

все уже разжевано, в чем проблема то?

(14) Пусть для 40000 вершин хватит памяти, а если число вершин увеличить в 2 раза, то кол-во памяти нужно в 4(!) раза больше, в 4 - в 16(!) раз. То есть ОП отжирается пропроционально КВАДРАТУ числа вершин.

(17) Ну да ладно, предположим ОП нам хватает, а если попробовать засечь средствами отладки как растет количество проверок несуществующих связей между вершинами???

Насколько я помню, по теории алгоритмов если что-то растет пропорционально квадрату числа объектов (оперативная память, кол-во проверок/присваиваний), то это уже не очень хороший алгоритм.

(19) Например, "классические" методы решения систем линейных уравнений: как N^3. Но для систем общего вида лучше, можно сказать, нет.
Если граф "сильно" заполнен, все равно получите N^2. Здесь речь о том, что представлять граф в виде матрицы смежности в случае разреженного графа неэкономно. По-моему, экономнее списка дуг трудно что-нибудь придумать.

(20) А часты ли на практике ситуации, при которых в огромных графах порядка нескольких десятков тысяч элементов, связан практически "каждый с каждым"?