реализация алгоритмов и структур данных

Question

Я успешно реализовал несколько алгоритмов и структур данных. Однако я не уверен, как реализовать алгоритм графа, так как тогда мне нужно будет представлять граф. Я пытаюсь реализовать алгоритмы и структуры данных от введения к алгоритмам cormen et. и др. Однако многие алгоритмы принимают граф в качестве входных данных или берут древовидную структуру в качестве входных данных, которые вы не можете просто предоставить как текст. Я не знаю, как реализовать dijkstra, bellman-ford, floyd-warshall, kruskal и т. Д. Могу ли я представить любой граф в виде матрицы, даже если это взвешенный или направленный граф? потому что я думаю, что могу использовать многомерные массивы для матриц. я думаю, 0 или 1 может указать, есть ли край или нет, но я не уверен, как я буду представлять любой граф, используя матрицу. и как насчет бинарного дерева, если алгоритм принимает это как вход?

благодарит заранее.

Answer 1

Это очень открытый вопрос. Ответ зависит от вида операций, которые вы хотите сделать.

Один из способов представления простого графика - это массив N x N, где каждый элемент представляет собой ребро. Очевидно, вам нужен только один треугольник и может игнорировать другую половину или дублировать информацию, чтобы упростить поиск.

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