Обектно-ориентирано програмиране 2004/05 - упражнения и практикум

  Дадени са n града с транспортните връзки между тях. Не всеки два града са свързани с транспортна линия, освен това наличието транспорт от град A до град B не означава наличие на транспорт от град B до град A.

 Да се провери дали с наличния транспорт може да се стигне от произволен даден град до друг.

  Ако именуваме градовете с естествените числа от 0 до n-1 описания проблем най-естествено се представя със структурата от данни граф. Градовете представяме с т.нар. върхове на графа, а транспортните връзки - с дъги. На фигурата върховете са отбелязани с кръгчета, в които е написа съответния град, а дъгите - със насочени стрелки.

 Такъв граф можем да опишем а квадратна NxN матрица, кидето aij=1 тогава и само тогава, когато между град i и град j има дъга, тоест транспорт. Такива върхове наричаме съседи. За графа на фигурата матрицата е:

1 0 0 0 0
0 1 0 0 0
1 0 0 1 0
0 0 0 0 0
0 0 1 0 0

  Търсенето на маршрут между върхове в графа да наречем обхождане на графа. На фигурата е показан граф с цикъл, тоест има връх с маршрут до самия него. При графи с цикъл е възможно обхождащата програма да не завърши. Затова въвеждаме още една структура - едномерен масив visited, в които си отбелязваме посетение еърхове (в началото никой не е посетен).

  Следният рекурсивен алгоритъм е т.нар. алгоритъм за обхиждане в дълбочина на граф и проверява дали може от връх start да се стигне до връх end.

way (start, end)

  if (start==end)
    return true;
  visited[start] = true;

  for i - съсед на start and not visited[i]
    if way(i,end)
      return true;

  return false;
 

 За някои задачи е по-удобно използването на алгоритъма за обхождане в широчина, при който е удобна структурата от данни опашка:

way (start,end)

  Queue q;
  q.insert (start);
  
  while q.get (i) and i <> end
    for j - съсед на i and not visited[j]
      {visited[j] = true; q.insert (j)}

  return i == end