4393

Поиск на графе в С++

Контрольная

Информатика, кибернетика и программирование

Поиск на графе в С++ Представление графа в виде матрицы смежности Граф (graph) – это графическая схема, представляющая собой совокупность вершин (vertexes), соединенных между собой ребрами (edges). Иногда вершины также называют узлами (no...

Русский

2012-11-18

116.5 KB

92 чел.

Поиск на графе в С++

  1.  Представление графа в виде матрицы смежности

Граф (graph) – это графическая схема, представляющая собой совокупность вершин (vertexes), соединенных между собой ребрами (edges). Иногда вершины также называют узлами (nodes). На рис. 9.1. показан пример неориентированного (undirected) графа.

Рис. 9.1. Граф

Один из простых методов представления графа в компьютерной программе заключается в использовании двумерного массива, называемого матрицей смежности (adjacency matrix). Она позволяет быстро определять, существует ли ребро между вершинами i и j путем простой проверки наличия ненулевого значения в елементе матрицы, находящегося на пересечении i-ой строки и j-ого столбца. Для неориентированного графа матрица смежности симметрична. В листинге 9.1 показана программа создания матрицы смежности для вводимой последовательности ребер.

Листинг 9.1. Представление графа в виде матрицы смежности

#include <iostream.h>

void main()

{ int i, j, V, adj[100] [100];

cout<<"Input number of nodes: ";

cin>>V;

for (i=0; i<V; i++)

 for (j=0; j<V; j++)

  adj[i][j]=0;

for (i=0; i<V; i++) adj[i][i]=1;

cout<<"Input numbers of linked nodes: i-j.\n";

cout<<"If (i<0) or (j<0) - end.\n\n";

 int k=0;

for (;;) //"Бесконечный цикл"

 {

  cout<<k<<": ";

  cin>>i>>j;

  if ((i<0)||(j<0)) break; // Условие выхода

  k++;       // из цикла

  adj[i][j]=1; adj[j][i]=1;

 }

cout<<endl;

cout<<"Adjacency matrix:\n";

cout<<endl;

for (i=0; i<V; i++)

{

 for (j=0; j<V; j++)

  cout<<adj[i][j]<<" ";

 cout<<endl;

}

char res;

cin>>res;

}

РЕЗУЛЬТАТ

На распечатке показана матрица смежности графа, представленного на рис. 9.1. Иногда в матрице смежности элементы главной диагонали приравнивают нулю. В данном примере они равны единице. Вообще-то, это философский вопрос: нужно ли учитывать соединение вершины с самой собой.

  1.  Представление графа в виде списков смежности

Другой простой метод представления графа предусматривает использование массива связанных списков, называемых списками смежности (adjacency lists). Каждой вершине соответствует связной список с узлами для всех вершин, связанных с данной. На рис. 9.2 показан пример представления неориентированного графа (рис. 9.1) с помощью списков смежности.

Рис. 9.2. Представление графа в виде списков смежности

Обозначим количество вершин графа буквой , а количество ребер – буквой . Для матрицы смежности необходимо пространство в памяти, пропорциональное , а для списков смежности расход памяти пропорционален величине +. При небольшом количестве ребер (такой граф называется разреженным (sparse)), представление с использованием списков смежности потребует намного меньшего пространства. Если большинство пар соединено ребрами (такой граф называется насыщенным), использование матрицы смежности предпочтительнее, поскольку оно не связано со ссылками.

Оба рассмотренных типа представлений можно просто распространить и на другие типы графов. Они служат основой большинства алгоритмов обработки графов. 

  1.  Обход графа

Рассмотрим одну из наиболее важных рекурсивных программ: рекурсивный обход графа, или поиск в глубину (depth-first search). В листинге  

9.2 приведена программа поиска в глубину. При этом используется представление графа в виде списка соседних узлов. Начиная с любого узла  (в данной программе это узел с индексом 0, однако программу легко переделать, чтобы индекс начального узла был любым), мы посещаем , а затем рекурсивно посещаем каждый непосещенный узел, связанный с . Если граф является связным (connections), то со временем будут посещены все узлы.

Листинг 9.2. Поиск в глубину

#include <iostream.h>

struct node

{

int v; node* next;

node(int x, node* t)

 { v=x; next=t;}

};

void traverse(int k, void visit(int));

void visit(int n);

typedef node *link;

link adj[100];

int visited[100];

void main() {

int i, j, V;

cout<<"Input number of nodes:";

cin>>V;

cout<<endl;

for (i=0; i<V; i++) adj[i]=0;

cout<<"Input numbers of linked nodes as: i_j

       <Enter>"<<endl;

cout<<endl;

cout<<"(if i < 0 or j < 0 - this is indication of

end)"<<endl;

cout<<endl;

int k=0;

for (;;)  

{

  cout<<k<<": ";

  cin>>i>>j;

  if ((i<0)||(j<0)) break;

  k++;

  adj[j]=new node(i, adj[j]);

  adj[i]=new node(j, adj[i]);

 }

cout<<endl;

traverse(0, visit);

char res;

cin>>res;

}

void traverse(int k, void visit(int)) {

visit(k);

visited[k]=1;

for (link t=adj[k]; t!=0; t=t->next)

 if (!visited[t->v]) traverse(t->v, visit);

}

void visit(int n) {

cout<<"visit "<<n<<endl;

}

РЕЗУЛЬТАТ

Для посещения в графе всех узлов, связанных с узлом k, мы помечаем его как посещенный, а затем рекурсивно посещаем все непосещенные узлы в списке смежности для узла k. Функция traverse() вызывает функцию  visit()для каждого из узлов графа. Время, требующееся для выполнения поиска в глубину в графе с  вершинами и  ребрами, пропорционально +, если использовать представление графа в виде списков смежности.

В программе используется структура node. В языке C++ структура представляет собой класс, все члены которого по умолчанию открыты (public). Структуру можно объявить точно так же, как и класс, наделив ее такими же переменными-членами и функциями. А если следовать всем правилам программирования и всегда объявлять в явном виде открытые и закрытые разделы структуры, то никаких отличий не будет вовсе.

Возникает закономерный вопрос: почему два ключевых слова выполняют одинаковые действия? Так сложилось исторически. Когда разрабатывался язык C++, за основу был принят язык C, который содержал структуры. Но эти структуры не имели методов, как классы. Создатель языка C++ Бьерн Страуструп опирался на структуры, но заменил имя типа данных struct типом class, чтобы заявить о новых расширенных функциональных возможностях этого нового образования. Это позволило также продолжать использование множество библиотек функций языка C в программах C++.

В функции traverse() используется оператор косвенного доступа (indirection operator): «указатель на» (->), который состоит из символов «минус» и «больше». Компилятор С++ воспринимает его, как единый оператор. Выражение (t->v) означает: «получить доступ к переменной v (которая является членом структуры node) по заданному указателю t.


2

1

6

0

5

3

4

5

2

7

7

0

1

6

7

0

5

4

6

5

7

3

0

4

3

4

0

1

2

0

4

0

1

2

3

4

5

6

7


 

А также другие работы, которые могут Вас заинтересовать

54170. Урок-казка. Чарівні слова. Розвязування рівнянь 165 KB
  Таблиці плакати до казки про ІванаЦаревича і Чахлика Невмирущого. Клас розбивається на 3 команди і вибирається ІванЦаревич. Там під дубом вчений кіт Русалонька за принцем плаче КоникГорбоконик на підмогу скаче Привид Кентервільський всіх лякає ІванЦаревич Змія перемагає. Учитель: В деякому царстві живбув ІванЦаревич.
54171. Особливості навчання математиці дітей із затримкою психічного розвитку в умовах якісної освіти 450.5 KB
  Поданий матеріал може бути використаний вчителями математики, які працюють як в спеціалізованих класах корекції для дітей із затримкою психічного розвитку, так і звичайних класах загальноосвітньої школи. В посібнику відображені питання класифікації дітей із затримкою психічного розвитку, зазначені причини затримки розвитку, подана характеристика дітей даної категорії та визначені особливості їх навчальної діяльності на уроках математики.
54172. Применение свойств действий при вычислениях и решении уравнений в 5-м и 6-м классах 151.5 KB
  На усвоение этих свойств достаточно на такой ранней стадии устные упражнения с дальнейшим переходом к письменным упражнениям, развивая у учеников умение и навыки работы с числовыми выражениями, решении уравнений без использования правил нахождения неизвестного компонента действия: развивая у учеников творческий подход к решению математических задач.
54173. Система практичних завдань при вивченні математики у 5-6 класах 199.5 KB
  Звичайно в шкільних підручниках є задачі-розрахунки, в основу яких покладено залежності між величинами, які часто зустрічаються в житті, між компонентами руху; між ціною, кількістю і вартістю; між продуктивністю праці, часом роботи і одержаною продукцією; розрахунки часу; знаходження периметрів, площ; обчислення витрат різних матеріалів тощо.
54174. Система дидактичних умов пізнавальної діяльності учнів на уроках математики 119.5 KB
  Система дидактичних розумів розвитку пізнавальної діяльності учнів на уроках математики. Розвиток пізнавального інтересу учнів. Прийоми активізації пізнавальної діяльності учнів на уроках математики. Інтерактивні технології навчання спосіб створення умов залучення учнів до пізнавальної діяльності.
54175. Первісна. Інтеграл. Застосування інтегралу при розвязуванні задач економічного змісту 690.5 KB
  Група студентів ділиться на чотири команди. На першому етапі заняття проводиться узагальнення та систематизація знань учнів з теми, розглядаються учнівські презентації про виникнення інтегралу та його використання. На другому етапі – пояснення нового матеріалу, потім його закріплення в вигляді створення проектів кожною підгрупою.
54176. Развитие культуры в условиях нижнего и среднего палеолита 33 KB
  Одним из важнейших способов выживания человека в первобытную эпоху стал беспрерывный процесс познания окружающего мира. На раннем этапе жизни человека предметом познания и осмысления является природа, от которой напрямую зависит жизнь человеческого общества.
54177. Новые информационные технологии в профильном обучении математики на примере темы „Многогранники” в 11 классе 827.5 KB
  Рассмотрение различных случаев взаимного расположения диагоналей ребер и граней многогранника использование для этого моделей и готовых чертежей способствует развитию пространственных представлений учащихся их интуиции Рис. Особо подчеркиваются характеристические свойства призмы.
54178. Видатні вчені на уроках математики 165 KB
  Задача 2 Вирішивши поділити всі свої заощадження між усіма синами хтось склав такий заповіт: Старший з моїх синів повинен отримати 1000 франків і 1 8 частину остачі; наступний 2000 франків і 1 8 нової остачі; третій син 3000 франків і 1 8 частини третьої остачі і т. Так як усі сини отримали порівну то 1 8 частина кожної нової остачі була на 1000 франків менше 1 8 частини попередньої остачі тобто уся нова остача була на 8000 франків менше попередньої. Так як за умовою усі гроші були розділені повністю то коли молодший син отримав по...