| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > Графы, кратчайший путь на С\С++ |
| Автор: Gether 15.12.2004, 20:16 |
| Люди!Помогите пожалуйста!Срочно нужна программа! Программа на C/C++: Представление графов Вершины графов заданы номерами или названиями пунктов На дугах определены числа ("расстояние" или "стоимость") Граф G задается списком исходящих из а дуг, например, (помеченных взвешенных дуг) вида G=a:(b,2.0),(c,2),(f,3.1); или списком троек вида G=(a,b,1.2),(a,c,2),(a,f,3.1); где a - название исходной вершины. Задание: 5. Вершины графа разбиты на два подмножества - красные (A) и синие (B). Найти кратчайший путь из красной вершины а до ближайшей синей.  |
| Автор: sergejzr 15.12.2004, 20:34 |
Начинай писать, поможем  |
| Автор: Gether 15.12.2004, 20:46 |
| sergej.z Как лучше описывать граф на C?В виде матрицы? |
| Автор: sergejzr 15.12.2004, 21:37 |
| Я просто делал массив из узлов. узел - структура. |
| Автор: Gether 15.12.2004, 21:40 |
| sergej.z Есть какие-нибудь примеры?С чего начать? |
| Автор: sergejzr 15.12.2004, 21:45 | ||
| У тебя структура узел. В ней указатели на всех соседей(структуры дуги). Добавочно цвет, номер, название. Дуга - содержит просто указатель на соседний узел и свой вес. Добавлено @ 21:49
Ну, если на Си++ пишешь, можешь ессно классы делать, а не структуры. Вообще по моему здесь на форуме этот вопрос часто задавался. Попробуй поиск... |
| Автор: lexer 19.2.2007, 19:48 |
| для представления графов используются матрица смежности или инциденции... в аттаче пример поиска кратчайшего пути между вершинами методом фронта волны. вводим кол-во вершин, заполняем матрицу смежности и задаем между какими вершинами нужно показать путь (консольный вариант) |
| Автор: lexer 19.2.2007, 20:40 |
| вообще сейчас у меня похожая проблема, пишу программу с графическим интерфейсом для работы с графами. Вообщем она должна будет делать следующее: 1) заполняем матрицу смежности, программа строит граф и заполняет матрицу инциденций 2) заполняем матрицу инциденций, программа строит граф и заполняет матрицу смежности 3) сами рисуем граф, нанесением точек("вершин") и соединяющих линий("ребер") с возможностью их вращения, программа заполняет матрицу смежности и инциденций. 4) планирую сохранение в файл проекта и последующая загрузка из него. Подскажите может есть готовые модули для работы с графами или литература, где можно почитать про них? Заранее спасибо! |
| Автор: Earnest 20.2.2007, 19:33 |
| Boost graph library |
| Автор: Okonner 21.2.2007, 00:13 |
| А если сделать двухсвязный список, а потом сортировку??? Или я не понял задания? |
| Автор: lexer 21.2.2007, 20:52 |
| Вот еще проблема с алгоритмом: есть у меня граф, состоящий из N вершин(в этом конкретном примере N=4), он представлен следующим образом: 1 2 (1-ая вершина смежна второй) 1 3 (1-ая смежна третьей) 2 4 (2-ая четвертой и тд) 3 2 Не важно где они записаны, в массиве, в файле..Нужно преобразовать это в матрицу смежности и забить в StringGrid (размером NxN): -|-------| |1 1 1 0| |1 1 1 1| |1 1 1 0| |0 1 0 1| -|-------| Считываю данные циклом, сначала 1 2, затем 3 1 и тд... Заранее спасибо за помощь |
| Автор: lexer 22.2.2007, 01:09 |
| со смежной матрицой разобрался ;) |
| Автор: pablo 22.2.2007, 14:13 |
| В Boost есть всё что надо для работы с графами. Как представление, так и поиск на графах. www.boost.org |