Вопросы о графах

@zago-vlad · Регистрация: 12.01.2010

Author24 — интернет-сервис помощи студентам

Всем привет!

Появилось несколько вопросов о графах:
1) Как представить граф в C++?
2) Как найти самый краткий путь между двумя вершинами графа?

Заранее спасибо!

@Hi4ko · 03.02.2012, 21:05

Сообщение от zago-vlad

Всем привет!

Появилось несколько вопросов о графах:
1) Как представить граф в C++?
2) Как найти самый краткий путь между двумя вершинами графа?

Заранее спасибо!

1) Таблица смежности, матрица смежности
2) Алгоритм Дейкстры

@Алексaндр · 03.02.2012, 21:11

Здесь найдешь полезное о графах....

@zago-vlad · 04.02.2012, 00:48 **[ТС]**

Сообщение от Hi4ko

Таблица смежности, матрица смежности

А можно подробнее?

@Paporotnik · 04.02.2012, 01:01

что подробнее? гуглом пользоваться умеем?

это раздел для помощи в программировании на языках C/C++, а не в дискретной математике и теории графов.

@zago-vlad · 04.02.2012, 01:19 **[ТС]**

Сообщение от Paporotnik

это раздел для помощи в программировании на языках C/C++

Под "подробнее" я имел ввиду пример кода на C++ с комментариями. Гуглил с самого начала - нашел только код на Паскале.

@Vancan · 04.02.2012, 01:28

Сообщение от zago-vlad

Как представить граф в C++?

Вот пример (моя лаба с универа)

@Evgen311293 · 04.02.2012, 01:41

Сообщение от zago-vlad

Всем привет!

Появилось несколько вопросов о графах:
1) Как представить граф в C++?
2) Как найти самый краткий путь между двумя вершинами графа?

Заранее спасибо!

Есть такое слово slice - адаптер для линейных массивов.
Суть - любой массив любой размерности представляется линейной последовательностью элементов, но пересчитывая индексы через slice, можно получать представление массива произвольной размерности и его под-элементы (строки, столбцы и т.д.).

@Hi4ko · 04.02.2012, 10:21

с матрицей смежности смешно не разобраться
а вот со списком смежности я обычно делаю двумерный ВЕКТОР

C++

vector< vector<int> > g;
int main(){
int n;\\кол-во вершин
cin>>n;
for(int i=0;i<n;i++){\\пишу для случая, если 0 означает конец списка для данной вершины
int t;
vector<int> Temp; \\вектор с номерами вершин
cin>>t;
if(t!=0)
{
    Temp.push_back(t-1);\\нумерация вершин в плюсах с нуля же)
while(t!=0)
    {
cin>>t;
if(t!=0)
    Temp.push_back(t-1);
}
}
g.push_back(Temp);
}
}

Что такое вектор? Это класс "продвинутый массив", который также является динамическим.
Про методы почитай тут

@zago-vlad · 04.02.2012, 14:15 **[ТС]**

Всем спасибо, разобрался!

@zago-vlad 13 / 8 / 1 Регистрация: 12.01.2010 Сообщений: 106
		1
	Вопросы о графах 03.02.2012, 19:47. Показов 978. Ответов 9 Метки нет (Все метки) Всем привет! Появилось несколько вопросов о графах: 1) Как представить граф в C++? 2) Как найти самый краткий путь между двумя вершинами графа? Заранее спасибо! 0

@Hi4ko 74 / 74 / 13 Регистрация: 21.10.2010 Сообщений: 376
	03.02.2012, 21:05	2
	Сообщение от zago-vlad Всем привет! Появилось несколько вопросов о графах: 1) Как представить граф в C++? 2) Как найти самый краткий путь между двумя вершинами графа? Заранее спасибо! 1) Таблица смежности, матрица смежности 2) Алгоритм Дейкстры 1

@zago-vlad 13 / 8 / 1 Регистрация: 12.01.2010 Сообщений: 106
	04.02.2012, 00:48 [ТС]	4
	Сообщение от Hi4ko Таблица смежности, матрица смежности А можно подробнее? 0

@Paporotnik 385 / 229 / 12 Регистрация: 06.07.2011 Сообщений: 512
	04.02.2012, 01:01	5
	что подробнее? гуглом пользоваться умеем? это раздел для помощи в программировании на языках C/C++, а не в дискретной математике и теории графов. 0

@zago-vlad 13 / 8 / 1 Регистрация: 12.01.2010 Сообщений: 106
	04.02.2012, 01:19 [ТС]	6
	Сообщение от Paporotnik это раздел для помощи в программировании на языках C/C++ Под "подробнее" я имел ввиду пример кода на C++ с комментариями. Гуглил с самого начала - нашел только код на Паскале. 0

@Evgen311293 57 / 57 / 3 Регистрация: 23.03.2011 Сообщений: 567 Записей в блоге: 3
	04.02.2012, 01:41	8
	Сообщение от zago-vlad Всем привет! Появилось несколько вопросов о графах: 1) Как представить граф в C++? 2) Как найти самый краткий путь между двумя вершинами графа? Заранее спасибо! Есть такое слово slice - адаптер для линейных массивов. Суть - любой массив любой размерности представляется линейной последовательностью элементов, но пересчитывая индексы через slice, можно получать представление массива произвольной размерности и его под-элементы (строки, столбцы и т.д.). 1

@zago-vlad 13 / 8 / 1 Регистрация: 12.01.2010 Сообщений: 106
	04.02.2012, 14:15 [ТС]	10
	Всем спасибо, разобрался! 0