Поиск всех вершин орграфа, от которых существует путь заданной длины к выделенной вершине

Министерство образования и науки Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

КАФЕДРА ПРИКЛАДНОЙ МАТЕМАТИКИ

Курсовая работа

по практикуму на ЭВМ: структуры данных и алгоритмы

Факультет              ПМИ

Группа                    ПМ-93

Студент                  Трубников А.И.

Преподаватель    Хиценко В.П.

Новосибирск 2010

1.  Условие задачи

Найти все вершины орграфа, от которых существует путь заданной длины к выделенной вершине.

2.  Анализ задачи

2.1 Дано:

Входной файл “D:\in.txt”, из которого читается граф.

<Граф>

<Граф>:= <Список вершин> {<Список дуг>}

<Список вершин>:=<Название вершины> {<,>  <Название вершины>}

<Список дуг>:=<Дуга> {<Дуга>}

<Название вершины>:=<Символ>{<Символ>}

<Символ>:=<a> || <b> || … || <z> || <0> || <1> || … || <9> || < > || <A> || <B> || … || <Z>

<Дуга>:=<\n> <Название вершины> <-> <Название вершины>

2.2 Результат:

Выходной файл “D:\out.txt” , в который записывается результат.

<Подмножество вершин>

<Подмножество вершин>:=<Название вершины> <,>{<Название вершины> < >}

<Название вершины>:=<Символ>{<Символ>}

<Символ>:=<a> || <b> || … || <z> || <0> || <1> || … || <9> || < > || <A> || <B> || … || <Z>

2.3 Решение:

Понятия теории графов, использованной в данной задаче

Пусть V – непустое множество, V⁽²⁾ – множество всех его двухэлементных подмножеств. Пара (V,E), где E – произвольное подмножество множества V⁽²⁾, называется графом. Элементы множества V называются вершинами графа, а элементы множества E – ребрами. Итак, граф – это конечное множество V вершин и множество E ребер, EV⁽²⁾.

Ориентированный граф (или орграф) – это пара (V, A), где V – множество вершин, A – множество ориентированных ребер, которые называются дугами, AV⁽²⁾.

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

              Взвешенным графом называют граф, каждому ребру или(и) каждой вершине которого ставится в соответствие некоторая информация, характерная для данного ребра или данной вершины (эта информация называется весом) (вес вершины – это не метка вершины).

Формальная постановка задачи

В ориентированном взвешенном помеченном графе найти все вершины, из которых достижима заданная вершина при заданной длине.

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

3.  Структура основных входных и выходных данных

4.  Укрупненный алгоритм решения задачи

5.  Взаимодействие и взаимосвязь подпрограмм

Текст программы разбит на два модуля.

Модуль 1 содержит функции решения основных подзадач и определения входных и выходных данных.

Модуль 2 содержит вспомогательные функции, реализующие абстрактное представление графа.

5.1 Состав модуля 1

Главная функция main:

- назначение:

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

- прототип функции:

 int main (int argc, char **argv)

 - параметры:

argc -  (входной параметр) количество параметров, которые передаем из командной строки;

argv - (входной параметр) параметры, в argv[0] - имя запускаемой программы, argv[1] - название файла откуда берется граф,  argv[2] - вершина, в которую нужно попасть,

argv[3] - необходимая длина пути.

5.2  Состав модуля 2

Функция ReadGraph:

- назначение:

чтение графа и весов дуг.

- прототип:

void ReadGraph (FILE *file, int *num, int **G, int **weight)

- параметры:

file – (входной параметр) файл откуда читаем граф;

num – (входной параметр) количество вершин в графе;

G – (входной параметр) массив ребер: 1 – есть ребро, 0 – нет ребра;

weight – (входной параметр) веса ребер.

Функция FindVertexs:

- назначение:

поиск необходимых вершин в графе.

- прототип:

void FindVertexs(int*G, int *weight, int vertex, int num, int len, int path, int *IsVis, int *res, int curV, int start)

- параметры:

 G – (входной параметр) массив ребер: 1 – есть ребро, 0 – нет ребра;

weight – (входной параметр) веса ребер;

vertex - (входной параметр) вершина, которая имеется из условия задачи;

num - (входной параметр) количество вершин в графе;

len - (входной параметр) длина пути;

path - (входной параметр) путь;

IsVis - (входной параметр) массив посещенных вершин;

res - (входной параметр) массив достижимых вершин;

curV - (входной параметр) ;

start - (входной параметр) ;

          5.3 Структура программы по управлению

 

6.  Текст программы

Библиотека с функциями:

#ifndef __FUNCTIONS__

#define __FUNCTIONS__

#include <stdlib.h>

#include <stdio.h>

#include <limits.h>

#define STR_SIZE 1024

void ReadGraph(FILE *file, int *num, int **G, int **weight);