Как создать граф в с++? Как сделать поиск минимального пути?

[Абсалютдин]

Всем здравствуйте, одно из заданий в моей курсовой создать произвольный граф и найти минимальный путь от конечной точки до начальной. И также написать программу ( код ) для всего этого.
Пути от одной любой точки к другой проходят через ребра "e", которым также надо присвоить любые числа. и Вот по этим ребрам и будет вычислять минимальный путь от начала к концу!
Главные вопросы:
1) КАК СОЗДАТЬ ГРАФ В С++(графически изображать в самой программе не нужно)
2) Как сделать этот поиск минимального пути?
Хотя бы 1) помогите

[Alex11223]

https://ru.wikipedia.org/wiki/%D0%93...B8.D0.BA.D0.B5

[ura_111]

Я могу ошибаться, но мне кажется что тебе нужны "списки в с++". Типа такого:

struct graf
{
    int key;
    graf *next;
};

Ну вот пример (обрати внимание на "узлы" и "связи между узлами"):

0.jpg

Да, я понимаю, что когда в структуре присутствует только один указатель ("graf *next;") это мало кому интересно, потому что кроме змейки больше ничего и не реализовать. Но представь себе что станет возможным с 2-мя указателями, типа такого:

struct graf
{
    int key;
    graf *next;
    graf *pref;
};

Можно будет реализовать, ну например, такой граф:

1.jpg

... вот пример с 26 ссылками (26- это количество букв в английском языке):

3.jpg

я понимаю, что задачи "построить алфавит" и "граф" разные (хотя бы по тому что в графе могут быть кольца, а в алфавите их не может быть в принципе), но принцип построения один и тот же: создаём узел и определяемся со связями (интегрируем этот узел в общую структуру графа)...

___________________________________ ____________________
p.s.1: определись сколько нужно ссылок (максимально количество связи у самой разветвлённой развязки в графе): 1,2,3....
p.s.2: информацию о списках ищи в интернете:

2.jpg

[Абсалютдин]

Благодарю друг, как раз списки и структуры по программированию проходим! попробую! Только граф намного сложнее должен быть! и как обозначить и присвоить ребрам графа цену!?? Ведь в задании программа после введенных данных должна будет найти минимальный путь, как раз по этим присвоенным ценам! блин очень запутанно объясняю, простите))

[Абсалютдин]

[IMG]file:///C:/Users/ADMIN/Desktop/Безымянный.png[/IMG]

[ura_111]

картинка только в
jpeg
прокатывает.

[Alex11223]

Да давай уж сразу C:/Users/ADMIN/Desktop/пароли.txt )

Для загрузки картинок есть кнопка в расширенной форме ответа.

[ura_111]

Я тут порыскал (на форуме) и заметил, что граф делают и на основе обычного массива:

10.jpg

11.jpg


Ты не думал об этом?
Типа такого:

12.jpg

[ura_111]

А что насчёт списков - можно сделать два вида структур: один для узлов другой для ветвей....
А нужны ли узлы вообще?
Там будет хоть какая-нибудь информация храниться?

[Абсалютдин]

Вот е1,е2,е3.... - получается узлы соединяющие все эти вершины. и пользователь должен будет в начале программы вводить ( присвоить ) каждому узлу опреленную цену перехода с одной точки на другую. потом дале с этой накопленной суммой идти дальше по вершинам пока не придет от вершины 7 до вершины 1( в данном случае) Программа должна вывести и показать маршрут,который является самым минимальным (по итоговой сумме) - это все дискретная математика)