Как считать граф из файла

Обновлено: 07.07.2024

Репутация: нет
Всего: 32

Вот тут думаю изложить основы реализации теории графов на Паскале. Просьба не судить слишком строго - первый опыт. А если критиковать, то с подсказками.
При написании буду в основном пользоваться: Кормен, Лейзерсон, Ривест - Алгоритмы. Построение и анализ

Репутация: нет
Всего: 32

3. Поиск в глубину
Поиск в глубину - еще один способ обхода графа. Он используется в таких алгоритмах, как алгоритм топологической сортировки, алгоритм поиска сильно связанных компонент.
Стратегия поиска в глубину такова: идти вглубь пока это возможно (есть непройденные исходящие ребра), возвращатся и искать другой путь когда таких ребер не существует. Если после этого остаются неиспользованные вершины - можно выбрать одну из них и повторять процесс пока остаются необнаруженные вершины.
Найдя впервые вершину v, смежную с u, ми отмечаем это событие, записывая в поле p[v] значение u. Таким образом образуется дерево или несколько деревьев.
Как и поиск в ширину, алгоритм поиска в глубину использует цвета вершин. Сначала все вершины - белые. При обнаружении новой вершины, она красится в серый цвет. Когда вершина полностью обработана, она перекрашивается в черный цвет.
Кроме этого, поиск в глубину ставит на вершинах метки времени. Каждая вершина имеет две метки: d[v] показывает, когда вершина была обнаружена, f[v] - когда обработана. Эти метки впоследствии используются во многих алгоритмах на графах.
Во время выполнения этого алгоритма, обработка каждой вершины происходит ровно один раз. Общее же количество выполнения строк 3 - 6 процедуры DFS-Visit составляет O(E). В итоге сложность данного алгоритма составляет O(V+E), где V - количество вершин в графе, а E - количество ребер.

Репутация: нет
Всего: 32

4. Топологическая сортировка

Пусть имеется ориентированный граф без циклов. Задача о топологической сортировке этого графа состоит в следующем: надо указать такой линейный порядок на его вершинах, что любое ребро ведет от меньшей вершины к большей (в смысле этого порядка). Очевидно, что если в графе есть циклы, то такого порядка не существует. Можно сформулировать задачу о топологической сортировке и так: расположить вершины графа на горизональной прямой так, что чтобы все ребра шли слева направо.
Во пример ситуации, когда возникает побобная задача: во время обучения программированию, какие-то темы нужно учить раньше других. Например, циклы нужно обязательно знать до изучения реализации теории графов. В некоторых случаях порядок не имеет значения (например, алгоритмы вычислительной геометрии можно учить как перед изучением теории графов, так и после).
Мы составляем граф по следующем принципу: существует ребро (u,v) если тема u должна быть изучена перед прохождением темы v. Тем самым, топологическая сортировка описывает возможный порядок изучения тем.

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

Цитата

Topological-Sort
1 вызвать DFS(G), при этом
2 завершая обработку вершины (DFS-Visit, строка 8), добавлять ее в начало списка
3 вернуть построенный список вершин

Репутация: нет
Всего: 32

Алгоритм Дейкстры

Представим себе карту автомобильных дорог Украины. Как найти кратчайший путь например из Днепропетровска в Ужгород? Можно, конечно, перебрать все возможные пути и выбрать минимальный из них. Но тогда получаются миллионы заведомо неверныз вариантов. Вот например зачем мне ехать из Днепра в Ужгород через Донецк, наматывая около шестисот лишних километров? Далее будет рассмотрен эффективный способ решения этой задачи.
Алгоритм Дейкстры решает задачу о кратчайших путях из одной вершины для взвешенного ориентированного графа G = (V,E) с исходной вершиной s, в котором веса всех ребер неотрицательны.
В процессе работы алгоритма поддерживается множетсво S, состоящее из вершин v, для которых расстояние от s до v уже известно. На очередном шаге алгоритм выбирает вершину u, не принадлежащую V и имеющую минимальное d[u] (где d[u] это расстояние от s до u). Далее производится т.н. релаксация всех ребер, выходящих из u. Это означает, что для каждого ребра ui если d[u ]+w(u,i)<d[i ] то d[i ]=d[u ]+w(u,i), где w(u,i) - это вес ребра ui. Все вершины, не принадлежащие S, хранятся в очереди Q

Алгоритм Дейкстры:

Цитата

АЛГ DIJKSTRA(G,s)
Для всех вершин v из V
нц
d[v]<=MAX
parent[v]<=NIL
кц
d[s]<=0
S<=пустое множество
Q<=V
Пока Q - не пустое множество
нц
u<=минимальное из Q
S<=S+
Для всех вершин v, являющихся потомком u
нц
Если d[v]>d[u ]+w(u,v) то
не
d[v]<=d[u ]+w(u,v)
parent[v]<=u
ке
кц
кц
КОН

Репутация: нет
Всего: 25

Спасибо за информацию и перевод общего описания в родной Паскаль по учебе приходится изучать теорию графов и алгоритмы на графах, но описание всего этого дается в таком непонятном виде, что все желание заниматься этим пропадает.

Дали вот задание: написать процедуру, реализующую метод, отличающийся от поиска в ширину только тем, что вновь достигнутая вершина помещается не в очередь, а в стек . с какой стороны подходить к нему? . что будет на входе, и что должно оказаться на выходе . не понятно.

Репутация: нет
Всего: 110

Цитата

Дали вот задание: написать процедуру, реализующую метод, отличающийся от поиска в ширину только тем, что вновь достигнутая вершина помещается не в очередь, а в стек

так это и есть отличие поиска вглубину от поиска в ширину
очередь соответствует поиску в ширину, а стек - в глубину
отличие стека от очереди.
гы. вспомнил интересную иллюстрацию: автомат Калашникова преобразует стек в очередь:
магазин у автомата построен так: последний вставленный патрон находится сверху, он и будет взят первым
ствол построен принципиально иначе: та пуля, которая попала в его начало первой, первой и вылетит с другого конца

Репутация: нет
Всего: 25

Буду мучиться ))) тока суть все равно не пойму. поиск в ширину или глубину. поиск чего? что там ищется? что будет найдено? и зачем это вообще с практической точки зрения )))

Репутация: нет
Всего: 110

если ограничение на длину строки не 10, а 3 (для наглядности), получим следующую последовательность:
1. в ширину: A,B,C,AA,AB,AC,BA,BB,BC,CA,CB,CC,AAA,AAB,AAC,ABA,ABB,ABC,не, мен даже при 3-х символах уже надоело
2. в глубину: A,AA,AAA,AAB,AAC,AB,ABA,ABB,ABC,AC,ACA,ACB,ACC,B,BA,BAA.

вот и все объяснение
P.S.
ну и обещанный возврат к ограничению на длину строки
в общем случае это - ограничение на глубину дерева (маскимальную длину ветки), так вот оно не всегда есть
например, в Прологе, когда производится попытка доказательства новых утверждений на основе старых получается именно вот такой проход по дереву (в каждый момент мы можем вспомнить одну из нескольких базовых посылок, а значит, получается ветвление). Но есть одна проблема: доказательство в принципе может быть любой длины, т.е. ограничения на глубину дерева нет
в таких ситуациях поиск в глубину принципиально неприменим, поэтому там, насколько я припоминаю, используется поиск в ширину.

Файлы позволяют пользователю считывать большие объемы данных непосредственно с диска, не вводя их с клавиатуры. Существуют два основных типа файлов: текстовые и двоичные.

Текстовыми называются файлы, состоящие из любых символов. Они организуются по строкам, каждая из которых заканчивается символом «конца строки». Конец самого файла обозначается символом «конца файла». При записи информации в текстовый файл, просмотреть который можно с помощью любого текстового редактора, все данные преобразуются к символьному типу и хранятся в символьном виде.

В двоичных файлах информация считывается и записывается в виде блоков определенного размера, в которых могут храниться данные любого вида и структуры.

Для работы с файлами используются специальные типы данных, называемые потоками. Поток ifstream служит для работы с файлами в режиме чтения, а ofstream в режиме записи. Для работы с файлами в режиме как записи, так и чтения служит поток fstream.

В программах на C++ при работе с текстовыми файлами необходимо подключать библиотеки iostream и fstream.

Для того чтобы записывать данные в текстовый файл, необходимо:

описать переменную типа ofstream.
открыть файл с помощью функции open.
вывести информацию в файл.
обязательно закрыть файл.

Для считывания данных из текстового файла, необходимо:

описать переменную типа ifstream.
открыть файл с помощью функции open.
считать информацию из файла, при считывании каждой порции данных необходимо проверять, достигнут ли конец файла.
закрыть файл.

Запись информации в текстовый файл

Как было сказано ранее, для того чтобы начать работать с текстовым файлом, необходимо описать переменную типа ofstream. Например, так:

ofstream F;

Будет создана переменная F для записи информации в файл. На следующим этапе файл необходимо открыть для записи. В общем случае оператор открытия потока будет иметь вид:

F.open(«file», mode);

Здесь F — переменная, описанная как ofstream, file — полное имя файла на диске, mode — режим работы с открываемым файлом. Обратите внимание на то, что при указании полного имени файла нужно ставить двойной слеш. Для обращения, например к файлу accounts.txt, находящемуся в папке sites на диске D, в программе необходимо указать: D:\\sites\\accounts.txt.

Файл может быть открыт в одном из следующих режимов:

ios::in — открыть файл в режиме чтения данных; режим является режимом по умолчанию для потоков ifstream;
ios::out — открыть файл в режиме записи данных (при этом информация о существующем файле уничтожается); режим является режимом по умолчанию для потоков ofstream;
ios::app — открыть файл в режиме записи данных в конец файла;
ios::ate — передвинуться в конец уже открытого файла;
ios::trunc — очистить файл, это же происходит в режиме ios::out;
ios::nocreate — не выполнять операцию открытия файла, если он не существует;
ios::noreplace — не открывать существующий файл.

Параметр mode может отсутствовать, в этом случае файл открывается в режиме по умолчанию для данного потока.

После удачного открытия файла (в любом режиме) в переменной F будет храниться true, в противном случае false. Это позволит проверить корректность операции открытия файла.

Открыть файл (в качестве примера возьмем файл D:\\sites\\accounts.txt) в режиме записи можно одним из следующих способов:

После открытия файла в режиме записи будет создан пустой файл, в который можно будет записывать информацию.

Если вы хотите открыть существующий файл в режиме дозаписи, то в качестве режима следует использовать значение ios::app.

После открытия файла в режиме записи, в него можно писать точно так же, как и на экран, только вместо стандартного устройства вывода cout необходимо указать имя открытого файла.

Например, для записи в поток F переменной a, оператор вывода будет иметь вид:

Для последовательного вывода в поток G переменных b, c, d оператор вывода станет таким:

Закрытие потока осуществляется с помощью оператора:

F.close();

В качестве примера рассмотрим следующую задачу.

Задача 1

Создать текстовый файл D:\\sites\\accounts.txt и записать в него n вещественных чисел.

Решение

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

Чтение информации из текстового файла

Для того чтобы прочитать информацию из текстового файла, необходимо описать переменную типа ifstream. После этого нужно открыть файл для чтения с помощью оператора open. Если переменную назвать F, то первые два оператора будут такими:

После открытия файла в режиме чтения из него можно считывать информацию точно так же, как и с клавиатуры, только вместо cin нужно указать имя потока, из которого будет происходить чтение данных.

Например, для чтения данных из потока F в переменную a, оператор ввода будет выглядеть так:

Два числа в текстовом редакторе считаются разделенными, если между ними есть хотя бы один из символов: пробел, табуляция, символ конца строки. Хорошо, когда программисту заранее известно, сколько и какие значения хранятся в текстовом файле. Однако часто известен лишь тип значений, хранящихся в файле, при этом их количество может быть различным. Для решения данной проблемы необходимо считывать значения из файла поочередно, а перед каждым считыванием проверять, достигнут ли конец файла. А поможет сделать это функция F.eof(). Здесь F — имя потока функция возвращает логическое значение: true или false, в зависимости от того достигнут ли конец файла.

Следовательно, цикл для чтения содержимого всего файла можно записать так:

//организуем для чтения значений из файла, выполнение
//цикла прервется, когда достигнем конец файла,
//в этом случае F.eof() вернет истину
while ( ! F. eof ( ) )
<
//чтение очередного значения из потока F в переменную a
F >> a ;
//далее идет обработка значения переменной a
>

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

Задача 2

В текстовом файле D:\\game\\accounts.txt хранятся вещественные числа, вывести их на экран и вычислить их количество.

Решение

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

На этом относительно объемный урок по текстовым файлам закончен. В следующей статье будут рассмотрены методы манипуляции, при помощи которых в C++ обрабатываются двоичные файлы.

Чтобы указать конкретное имя файла и открыть его необходимо выполнить следующее действие с данной ссылкой - myfile .

1) Если файл будет находиться в той же директории что и программа то задаем имя командой

2) Если файл будет находиться например на диске то задаем имя файла следующим образом:

a) можно использовать символ / (обратный слэшь) для задания пути

myfile .open (" E: / DEVELOP / MyCodingSite / C++ / IO / WriteRead / Win32 / Debug / Mytext.txt ");

б) чтобы использовать стандартный символ \ его нужно удваивать ( \\) иначе система не распознает данный символ.

myfile .open (" E: \\ DEVELOP \\ MyCodingSite \\ C++ \\ IO \\ WriteRead \\ Win32 \\ Debug \\ Mytext.txt ");

Указывая имя файла или полный путь к файлу мы связываем его с файловой системой. Если файла не существует то операционная система его создаст сама если файл существует то он будет открыт.

Функция Open встроенная в тип данных fstream содержит набор флагов позволяющих открывать файлы в разных режимах доступа. Чтобы задать один из режимов необходимо явно указать флаг доступа к файлу.

myfile .open (" Имя файла " , флаг доступа к файлу );

Если флаг не указан то система открывает файл с полным доступом по умолчанию.

Когда мы связались с файловой системой и указали имя файла которое нужно использовать. Нам открывается возможность выполнять различные действия:

Для записи данных в файл мы нужно открыть его с флагом ios::app это сообщит файловой системе что мы просто будем дописывать в конец файла информацию. Если флаг опустить то файл будет перезаписан заново. Т.е. содержимое исчезнет и останется только наш текст.

записываем текст в файл myfile << "My Ferst Text in file";

Этот код создаст файл с именем Mytext.txt в той же директории где находиться наш скомпилированный проект и запишет в него строку My Ferst Text in file

Для чтения файла нужно открыть его с флагом ios::in это сообщит файловой системе что мы просто будем читать информацию но не сможем ее записывать

При открытии файла на чтении нужно проверить смогла ли ОС (операционная система выполнить данное действие).

а) Если нет то сообщим что нет такого файла.

б) Если да будем пробовать читать содержимое файла.

Для проверки открылся файл или нет нужно использовать встроенную в функцию is_open() она встроена в тип данных ofstream.

Если файл открылся то функция вернет true (правду 1) если нет то false (ложь 0)

Хедер fstream предоставляет функционал для считывания данных из файла и для записи в файл. В целом он очень похож на хедер iostream , который работает с консолью, поскольку консоль это тоже файл. Поэтому все основные операции такие же, за мелкими отличиями, как в предыдущей теме по iostream.

Наиболее частые операции следующее:

1. Методы проверки открыт ли файл is_open() и достигнут ли конец файла eof()
1. 1. Настройка форматированного вывода для >> с помощью width() и precision()
  1. Операции позиционирования tellg(), tellp() и seekg(), seekp()
  Это не все возможности, которые предоставляет библиотека fstream. Рассматривать все сейчас мы не будем, поскольку их круг применения достаточно узок. Познакомимся с вышеперечисленными. Начнем с класса чтения.
  
  Класс ifstream
  
  Открытие файла в конструкторе выглядит так:
  ifstream file ( "d:\\1\\файл.txt" ) ; // открываем файл в конструкторе
  Так мы просим открыть файл txt с именем файл.txt, который лежит в папке с названием 1, а папка находится на диске d.
  
  Использование метода open() удобно, если программист не хочет сразу привязываться к файлу. Вдруг нужно свойство класса или глобальную переменную, ну а открывать файл уже потом. Если же нужно открыть файл внутри некой функции, поработать с ним и закрыть, то можно прописать путь к файлу прямо в конструкторе. В общем зависит от ситуации.
  
  Так все отработает нормально и файл откроется:
  
  Второй вариант проверки с использованием метода is_open() :
  
  Метод is_open() вернет 1, если файл найден и успешно открыт. Иначе вернет 0 и сработает код прописанный в блоке else .
  
  Если файл успешно открыт, из него можно производить чтение.
  
  Оператор считывания >>
  
  Так же как и в iostream считывание можно организовать оператором >> , который указывает в какую переменную будет произведено считывание:
  
  Считает вещественное, целое и строку. Считывание строки закончится, если появится пробел или конец строки. Стоит отметить, что оператор >> применяется к текстовым файлам. Считывание из бинарного файла производить лучше всего с помощью метода read().
  
  Кстати этот оператор достаточно удобен, если стоит задача разделить файл на слова:
  
  Методы getline() и get()
  
  Считывание целой строки до перевода каретки производится так же как и в iostream методом getline(). Причем рекомендуется использовать его переопределеную версию в виде функции, если считывается строка типа string:
  
  Если же читать нужно в массив символов char[], то либо get() либо getline() именно как методы:
  
  Принцип в общем тот же, что и в аналогах из iostream: Указывается в параметрах буфер (переменная, куда будет производиться чтение), или точнее указатель на блок памяти (если переменная объявлена статически: char buffer[255] к примеру, то пишется в параметры &buffer), указывается максимальное количество считываемого (в примере это n), дабы не произошло переполнение и выход за пределы буфера и по необходимости символ-разделитель, до которого будет считка (в примере это пробел). Надеюсь я не больно наступлю на хобот фанатикам Си, если сажу что эти две функции на 99% взаимозаменяемы, и на 95% могут быть заменены методом read() .
  
  Метод read()
  
  Похож на предыдущий пример?
  
  Метод close()
  
  Метод eof()
  
  Проверяет не достигнут ли конец файла. Т.е. можно ли из него продолжать чтение. Выше пример с считкой слов оператором >> как раз использует такую проверку.
  
  Метод seekg()
  
  Производит установку текущей позиции в нужную, указываемую числом. В этот метод так же передается способ позиционирования:
  
  Читайте также: