Я подумал о создании таблицы Vertices и таблицы Edges, но для построения графиков в памяти и для прохождения подграфов требуется большое количество поисков? Я бы хотел избежать чрезмерного чтения базы данных. Есть ли другой способ сохранения графика?
Боковое примечание: я слышал о Neo4j, но мой вопрос заключается в том, как концептуально представлять граф в стандартной базе данных. Я открыт для некоторых решений NoSQL, таких как mongodb.
Ответ, к сожалению, таков: ваше рассмотрение абсолютно верно в каждом пункте. Вы должны хранить узлы (вершины) в одной таблице, а Edges ссылаются на FromNode и ToNode для преобразования структуры данных графа в реляционную структуру данных. И вы также правы, что это приводит к большому количеству поисков, потому что вы не можете разбить его на подграфы, которые могут быть запрошены сразу. Вы должны пройти от узла к краю к узлу от края к узлу... и т.д. (Рекурсивно, пока SQL работает с наборами).
Дело в том...
Реляционные, графо-ориентированные, объектно-ориентированные, на основе документов - это различные типы структур данных, которые отвечают различным требованиям. Вот о чем идет речь и почему возникло так много разных баз данных NoSQL (большинство из них - простые хранилища документов), потому что просто не имеет смысла организовывать большие данные реляционным способом.
Альтернатива 1 - Графо-ориентированная база данных
Но есть также графо-ориентированные базы данных NoSQL, которые делают модель графовых данных первоклассным гражданином, таким как OrientDB, с которым я сейчас немного играюсь. Приятно то, что, несмотря на то, что они сохраняют данные в виде графика, они все же могут быть использованы как в реляционном, так и даже объектно-ориентированном или документно-ориентированном способах (т.е. Путем запросов с простым старым SQL). Тем не менее, обход графика является оптимальным способом получить из него данные наверняка.
Вариант 2 - работа с графиками в памяти
Когда дело доходит до быстрой маршрутизации, фреймворки маршрутизации, такие как Graphhopper, создают полный граф (миллиарды узлов) в памяти. Поскольку Graphhopper использует MemoryMapped-реализацию своего GraphStore, это работает даже на устройствах Android, требующих только несколько МБ памяти. Полный график считывается из базы данных в память при запуске, и тогда выполняется маршрутизация, поэтому вам не нужно искать базу данных.
Я столкнулся с этой же проблемой и решил, наконец, перейти со следующей структурой, которая требует 2 запросов к базе данных, затем остальная часть работы находится в памяти:
Хранить узлы в таблице и ссылаться на график с каждой записью node:
Table Nodes
id | title | graph_id
---------------------
105 | node1 | 2
106 | node2 | 2
Также храните края в другой таблице и снова ссылайтесь на график, к которому эти ребра относятся к каждому ребру:
Table Edges
id | from_node_id | to_node_id | graph_id
-----------------------------------------
1 | 105 | 106 | 2
2 | 106 | 105 | 2
Получить все узлы с одним запросом, а затем получить все ребра с другим.
Теперь создайте предпочтительный способ хранения графика (например, список смежности) и продолжите свой поток приложений.
Добавление к предыдущим ответам того факта, что MS SQL Server добавляет поддержку графической архитектуры, начиная с 2017 года.
Он следует описанному шаблону наличия таблиц Nodes и Edges (которые должны быть созданы со специальными ключевыми словами "AS NODE" и "AS EDGE"). 
Также введено новое ключевое слово MATCH "для поддержки сопоставления с образцом и обхода по графику", например: "Друг" - это имя таблицы ребер в следующем примере):
SELECT Person2.name AS FriendName
FROM Person Person1, friend, Person Person2
WHERE MATCH(Person1-(friend)->Person2)
AND Person1.name = 'Alice';
Существует также очень хороший набор статей о графических базах данных SQL Server на Redgate Hub.