4393

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

Контрольная

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

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

Русский

2012-11-18

116.5 KB

87 чел.

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

  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


 

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

30368. Понятие лексического значения слова 51 KB
  Лексическое значение слова это отражение в слове явлений реальной действительности В. ЛЗС это закреплённое в сознании говорящих соотнесенного звукового комплекса языковой единицы с тем или иным явлением действительности большинство слов называют предметы их признаки количество действия процессы и выступают как полнозначные самостоятельные слова выполняя в языке номинативную функцию. Значение слова отражает только различные признаки т.
30369. Понятие ЧП в свете современной концепции организации предложения 49.5 KB
  Важна дифференциация ГЧП и ВЧП. Второстепенные члены предложения ВЧП. Потебня строит классификацию ВЧП психологическое направление в основе синтаксиса предложение психологическое явление на их соответствие частям речи. В частности Пешковский: следует говорить не о ВЧП а о согласуемых управляемых и примыкающих ЧП.
30370. Предложение как коммуникативная единица. Актуальное членение предложений, средства его выражения. Понятие высказывания 38.5 KB
  Одним из свойств предложения является порядок слов то есть их определённая последовательность. Таким образом все предложения кроме синтаксической структуры имеют деление на логическое подлежащее предмет речи и логическое сказуемое признак. В конечном счёте чешский учёный Вильям Матезиус сказал что деление предложения на две части имеет чисто языковой смысл. Это коммуникативное членение предложения.
30371. Понятие об осложненном предложении. Спорные вопросы теории. Виды осложнения 50 KB
  К понятию осложненного предложения относится: предложения с однородными членами предложения с обособленными членами предложения с вводными и вставными конструкциями предложения с обращением Степень осложнения разная нужно основание для их объединения. Осложнение в семантической структуре предложения диктум и модус Осложнение диктума Я смотрю на звезды; монопредикативное монопропозитивное Я слушаю пенье соловья монопредикативное 2 пропозиции осложнение семантики которое не влечет за собой синтаксическое осложнения Соловей...
30372. Языковой статус сложного предложения. Основные типы СП. ССП 80.5 KB
  Языковой статус сложного предложения. Понятие сложного предложения является основополагающим в синтаксисе. В теории сложного предложения существует множество дискуссионных вопросов в частности вопрос об объёме СП о границах между простым и сложным предложением о понятиях сочинения и подчинения в СП и др. На основе анализов частей сложного предложения можно сделать вывод что поскольку очень часто материальные элементы простых предложений совпадают с материальными элементами сложного предложения СП это сумма нескольких простых предложений.
30373. Технические средства САПР и их развитие 139.5 KB
  Рассматриваются архитектуры ЭВМ в зависимости от последовательности обработки данных. Представляются классы ЭВМ в зависимости от множественности одиночности потоков команд и данных ОКОД ОКМД МКМД. Основное назначение лекции дать более глубокие знания по техническому обеспечению САПР: архитектуры ЭВМ в зависимости от последовательности обработки данных и классы ЭВМ в зависимости от множественности одиночности потоков команд и данных 6. Усложнение решаемых задач и вычислительных алгоритмов САПР привело к внедрению в эту область более...
30374. Технические средства САПР и их развитие. Периферийное оборудование САПР 159 KB
  Каждый метод и устройства реализующие его имеют свои достоинства и недостатки. По программному обслуживанию периферийные устройства САПР делятся на два класса: растровые и координатные векторные. В растровых устройствах выводится мозаичный рисунок из отдельных точек пикселей или ПЭЛов от англ. Все периферийные устройства делятся на три основные группы: средства ввода вывода с машинных носителей; средства ввода вывода с документов; средства непосредственного взаимодействия с ЭВМ.
30375. Методическое обеспечение САПР. Математический и лингвистический виды обеспечений 167.5 KB
  Лекция: Методическое обеспечение САПР. Математический и лингвистический виды обеспечений Рассматривается состав методического обеспечения САПР его сущность состав. Приводятся его компоненты методический и лингвистический виды обеспечения САПР для случая когда последний не является самостоятельным. Изучение одного из важнейших видов обеспечения САПР методического обеспечения 8.
30376. Программное обеспечение САПР 111.5 KB
  Лекция: Программное обеспечение САПР Рассматривается сущность программного обеспечения систем автоматизированного проектирования ПО САПР документы в составе ПО САПР. Даются структура общесистемного ПО и основные характеристики прикладного ПО САПР. Основное назначение лекции усвоение сущности программного обеспечения САПР ПО САПР его функций состава а также роли операционных систем ОС 9. Программное обеспечение САПР.