 |
Результаты работы программы
|
|
|
|
Условие задачи
Найти все вершины заданного графа, недостижимые от заданной его вершины.
Анализ задачи
Исходные данные:
множество рёбер графа. 
заданная вершина. 
Результат:
множество всех вершин, недостижимых из вершины 
Формальная постановка задачи:
В ориентированном невзвешенном графе найти все вершины, до которых не существует пути из указанной вершины.
Решение задачи сводится к тому, что нужно применить любой из обходов графа и просмотреть по окончанию обхода информацию о том, какие вершины были пройдены, а какие нет, эту информацию можно извлечь, например, из массива, который отвечает за раскраску вершин во время обхода.
Основные подзадачи для решения общей задачи:
1) Ввод графа
2) Осуществление обхода графа (был выбран обход в ширину)
3) Просмотр массива с данными о раскрашенных вершинах.
Структуры данных, используемые для представления исходных данных и результатов задачи
Входные данные:
Внешнее представление:
<информация о графе>::= <список ребер>
<список ребер>::= <пара вершин> | <список ребер>
<Пара вершин>::= <вершина> пробел <вершина>
<вершина>::= натуральное число, строго меньшее количества вершин в графе.
Внутреннее представление:
Используется списки смежности.
struct AdjacencyList {
int vertexNumber;
AdjacencyList *next;
};
struct Node {
int vertexNumber;
AdjacencyList *adjList;
Node *next, *prev;
};
struct Graph {
Node *listOfAdjacency;
int amountVertices;
};
Выходные данные:
Внешнее представление:
<список вершин>::= <вершина> | <список вершин>
<вершина>::= натуральное число, строго меньшее количества вершин.
Внутреннее представление:
В программе нет представления выходного списка вершин.
|
|
|
Укрупненный алгоритм решения задачи
Укрупненный алгоритм решения задачи:
{
Ввод информации о графе и составление по введенным данным списков смежности.
Ввод 
.
Осуществление обхода графа в ширину и возвращение информации о раскрашенных вершинах в виде массива 
.
{
{
Вывести номер вершины 
.
}
}
вывести, что недостижимых вершин нет.
}
Алгоритм обхода графа в ширину:
{
{
}
}
Укрупненный алгоритм ввода графа:
{
}
Структура программы
Текст программы разбит на 3 модуля: source.cpp, graph.h, queue.h
Модуль graph.h содержит описание графа и функции, реализующие операции над графом.
Модуль queue.h содержит описание такого типа данных, как очередь, а также функции, которые реализуют операции над очередью.
source.cpp содержит основную функцию, которая вызывает все остальные необходимые функции и в которой происходит диалог с пользователем.
Описание модуля graph.h
Graph* createEmptyGraph()
Назначение – создание пустого графа.
Результатом является указатель на область памяти, где содержится граф.
void deleteGraph(Graph **G)
Назначение – удаление графа из памяти.
Аргументом является адрес указателя, который содержит адрес области памяти, в которой хранится граф.
Graph* readGraphFromFile(char *pathToFile)
Назначение – чтение графа из файла.
Аргументом является строка, которая содержит путь до файла, в котором хранятся данные о графе.
Результатом является указатель на область памяти, где содержится граф.
void printGraph(Graph *G)
Назначение – вывод графа в консоль.
Аргументом является указатель на область памяти, где содержится граф.
int* BFS(Graph *G, int startVertex)
Назначение – обход графа в ширину.
Первым аргументом является указатель на область памяти, где содержится граф.
Вторым аргументом является номер вершины, с которой необходимо начать обход.
Результатом является указатель на начало массива, в котором хранится информация о раскраске графа после обхода.
|
|
|
void addEdge(Graph *G, int u, int v)
Назначение – добавление ребра в граф.
Первым аргументом является указатель на область памяти, где содержится граф.
Вторым и третьим аргументом являются соответственно начало и конец ребра (номера вершин).
Node* addNode(Node *head, int numberOfVertex)
Назначение – добавление нового элемента в список вершин.
Первым аргументом является указатель на первый элемент списка.
Вторым аргументом является номер добавляемой вершины.
Результатом является указатель на элемент списка, который был создан и добавлен в список вершин.
Node* findNode(Graph *G, int numberOfVertex)
Назначение – нахождение вершины с заданным номером.
Первым аргументом является указатель на граф.
Вторым аргументом является номер вершины, которую надо найти в списке вершин.
Результатом является либо указатель на элемент списка (в случае успеха), либо нулевой указатель (в случае неудачи).
void deleteNodeList(Node **L)
Назначение – удаление списка вершин.
Аргументом является адрес указателя, который указывает на первый элемент списка.
void addAdjacencyNode(AdjacencyList **L, int numberOfAdjVertex)
Назначение – добавление вершины в список смежности.
Первым аргументом является адрес указателя, который указывает на первый элемент списка.
Вторым аргументом является номер вершины, которую необходимо добавить.
AdjacencyList* findAdjacencyNode(Node *L, int numberOfAdjVertex)
Назначение – нахождение смежной вершины с заданным номером.
Первым аргументом является адрес на элемент в списке вершин, в котором будет просматриваться список смежности.
Вторым аргументом является номер вершины, которую необходимо найти.
Результатом является либо указатель на элемент списка смежности (в случае успеха), либо на нулевой указатель (в случае неудачи).
Описание модуля queue.h
Queue* createQueue()
Назначение – создать пустую очередь.
Результатом является указатель на область памяти, в которой содержится очередь.
int isEmpty(Queue *Q)
Назначение – проверка очередь на наличие элементов в ней.
Аргументом является указатель на область памяти, в которой содержится очередь.
Результатом является единица, если очередь пуста, или нуль, если очередь не пуста.
|
|
|
int pop(Queue *Q, int *val)
Назначение – получить элемент из очереди.
Первым аргументом является указатель на область памяти, в которой содержится очередь.
Вторым аргументом является адрес переменной, в которую нужно поместить значение из очереди.
Результатом является единица, если элемент был успешно извлечен, или нуль, если в очереди нет элементов.
void push(Queue *Q, int val)
Назначение – добавить элемент в очередь.
Первым аргументом является указатель на область памяти, в которой содержится очередь.
Вторым аргументом является значение, которое необходимо добавить в очередь.
Структура программы по управлению:
Текст программы
Файл source.cpp
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <conio.h>
#include "Graph.h"
int main(int argc, char *argv[]) {
char inputFileName[100];
int vertexNumber;
printf("Enter the path to file with data about graph: ");
scanf("%s", inputFileName);
printf("Enter the vertex number for which you want to find unattainable summit: ");
scanf("%d", &vertexNumber);
Graph *G = readGraphFromFile(inputFileName);
printGraph(G);
int *colors = BFS(G, vertexNumber);
int flag = 0;
printf("Unreachable vertices: ");
for (int i = 0; i < G->amountVertices; i++) {
if (colors[i] == WHITE) {
printf("%d ", i);
flag = 1;
}
}
if (flag == 0) printf("There are no vertices.");
delete[] colors;
deleteGraph(&G);
_getch();
return 0;
}
Файл graph.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include "Queue.h"
#define WHITE 0
#define GRAY 1
#define BLACK 2
struct AdjacencyList {
int vertexNumber;
AdjacencyList *next;
};
struct Node {
int vertexNumber;
AdjacencyList *adjList;
Node *next, *prev;
};
struct Graph {
Node *listOfAdjacency;
int amountVertices;
};
AdjacencyList* findAdjacencyNode(Node *L, int numberOfAdjVertex) {
AdjacencyList *head = L->adjList;
while (head!= NULL) {
if (head->vertexNumber == numberOfAdjVertex) return head;
head = head->next;
}
return NULL;
}
void deleteAdjacencyList(AdjacencyList **L) {
AdjacencyList *header = *L;
AdjacencyList *tmp;
while (header!= NULL) {
tmp = header;
header = header->next;
delete tmp;
}
*L = NULL;
}
void addAdjacencyNode(AdjacencyList **L, int numberOfAdjVertex) {
AdjacencyList *tmp = new AdjacencyList;
tmp->vertexNumber = numberOfAdjVertex;
tmp->next = *L;
*L = tmp;
}
void deleteNodeList(Node **L) {
Node *header = *L;
header = header->next;
Node *tmp;
while (header!= *L) {
tmp = header;
header = header->next;
deleteAdjacencyList(&tmp->adjList);
delete tmp;
}
*L = NULL;
}
Node* findNode(Graph *G, int numberOfVertex) {
|
|
|
Node *tmp = G->listOfAdjacency->next;
while (tmp!= G->listOfAdjacency) {
if (tmp->vertexNumber == numberOfVertex) return tmp;
tmp = tmp->next;
}
return NULL;
}
Node* addNode(Node *head, int numberOfVertex) {
Node *tmp = new Node;
tmp->adjList = NULL;
tmp->vertexNumber = numberOfVertex;
head->prev->next = tmp;
tmp->prev = head->prev;
tmp->next = head;
head->prev = tmp;
return tmp;
}
void addEdge(Graph *G, int u, int v) {
AdjacencyList *adjTmp;
Node *nodeTmp;
nodeTmp = findNode(G, u);
if (nodeTmp == NULL) {
G->amountVertices++;
nodeTmp = addNode(G->listOfAdjacency, u);
addAdjacencyNode(&nodeTmp->adjList, v);
}
else {
adjTmp = findAdjacencyNode(nodeTmp, v);
if (adjTmp == NULL) addAdjacencyNode(&nodeTmp->adjList, v);
}
nodeTmp = findNode(G, v);
if (nodeTmp == NULL) {
G->amountVertices++;
addNode(G->listOfAdjacency, v);
}
}
Graph* createEmptyGraph() {
Graph *G = new Graph;
G->amountVertices = 0;
G->listOfAdjacency = new Node;
G->listOfAdjacency->vertexNumber = -1;
G->listOfAdjacency->adjList = NULL;
G->listOfAdjacency->prev = G->listOfAdjacency;
G->listOfAdjacency->next = G->listOfAdjacency;
return G;
}
void deleteGraph(Graph **G) {
deleteNodeList(&(*G)->listOfAdjacency);
delete *G;
*G = NULL;
}
Graph* readGraphFromFile(char *pathToFile) {
Graph *G = createEmptyGraph();
FILE *inputFile = fopen(pathToFile, "r");
if (inputFile == NULL) {
printf("Unable to open file\"%s\" \n", pathToFile);
deleteGraph(&G);
return G;
}
int u, v;
while (!feof(inputFile)) {
fscanf(inputFile, "%d%d", &u, &v);
addEdge(G, u, v);
}
return G;
}
void printGraph(Graph *G) {
Node *nodeTmp = G->listOfAdjacency->next;
AdjacencyList *adjTmp;
while (nodeTmp!= G->listOfAdjacency) {
printf("[%d]-->", nodeTmp->vertexNumber);
adjTmp = nodeTmp->adjList;
while (adjTmp!= NULL) {
printf("{%d}-->", adjTmp->vertexNumber);
adjTmp = adjTmp->next;
}
printf("NULL\n");
nodeTmp = nodeTmp->next;
}
printf("\n\n");
}
int* BFS(Graph *G, int startVertex) {
int *colors = new int[G->amountVertices];
for (int i = 0; i < G->amountVertices; i++) colors[i] = WHITE;
colors[startVertex] = GRAY;
Queue *Q = createQueue();
push(Q, startVertex);
int u;
while (!isEmpty(Q)) {
pop(Q, &u);
Node *currentVertex = findNode(G, u);
AdjacencyList *tmp = currentVertex->adjList;
while (tmp!= NULL) {
int v = tmp->vertexNumber;
if (colors[v] == WHITE) {
colors[v] = GRAY;
push(Q, v);
}
tmp = tmp->next;
}
colors[u] = BLACK;
}
return colors;
}
Файл Queue.h
#pragma once
struct Queue {
int value;
Queue *next, *prev;
};
int isEmpty(Queue *Q) {
if (Q == Q->next) return 1;
else return 0;
}
Queue* createQueue() {
Queue *Q = new Queue;
Q->next = Q;
Q->prev = Q;
Q->value = -1;
return Q;
}
int pop(Queue *Q, int *val) {
if (isEmpty(Q)) return 0;
Queue *tmp = Q->next;
Q->next = tmp->next;
tmp->next->prev = Q;
*val = tmp->value;
delete tmp;
return 1;
}
void push(Queue *Q, int val) {
Queue *tmp = new Queue;
tmp->value = val;
Q->prev->next = tmp;
tmp->prev = Q->prev;
tmp->next = Q;
Q->prev = tmp;
}
Тесты
Тест 1
Назначение: протестировать ситуацию, когда граф пустой.
Результат:
Enter the path to file with data about graph: test1.txt
Enter the vertex number for which you want to find unattainable summit: 0
Graph is empty.
Graph is empty.
Тест 2
Назначение: проверить ситуацию, когда все вершины достижимы.
Входные данные:
0 5
0 6
0 7
0 1
1 4
2 0
2 4
3 2
4 2
4 3
5 1
7 6
Результат:
Enter the path to file with data about graph: test2.txt
Enter the vertex number for which you want to find unattainable summit: 0
|
|
|
[0]-->{1}-->{7}-->{6}-->{5}-->NULL
[5]-->{1}-->NULL
[6]-->NULL
[7]-->{6}-->NULL
[1]-->{4}-->NULL
[4]-->{3}-->{2}-->NULL
[2]-->{4}-->{0}-->NULL
[3]-->{2}-->NULL
Unreachable vertices: There are no vertices.
Тест 3
Назначение: проверить ситуацию, когда есть недостижимые вершины.
Входные данные:
0 5
0 6
0 7
0 1
1 4
2 0
2 4
3 2
4 2
4 3
5 1
7 6
Результат:
Enter the path to file with data about graph: test3.txt
Enter the vertex number for which you want to find unattainable summit: 7
[0]-->{1}-->{7}-->{6}-->{5}-->NULL
[5]-->{1}-->NULL
[6]-->NULL
[7]-->{6}-->NULL
[1]-->{4}-->NULL
[4]-->{3}-->{2}-->NULL
[2]-->{4}-->{0}-->NULL
[3]-->{2}-->NULL
Unreachable vertices: 0 1 2 3 4 5
Тест 4
Назначение: проверить программу на достаточно большом графе.
Входные данные:
0 11
0 1
1 2
2 3
3 12
3 14
3 15
3 16
3 4
4 17
5 4
5 6
7 6
8 19
9 20
10 9
10 21
11 12
12 22
13 22
13 14
15 25
16 23
17 6
18 6
18 8
19 18
19 44
19 21
20 19
22 23
23 34
23 35
23 13
25 35
25 26
26 37
26 38
27 26
27 17
27 38
28 39
28 18
29 39
29 18
29 30
30 41
31 30
32 31
33 22
33 34
34 24
36 26
38 39
39 40
40 30
42 31
42 41
43 30
43 32
44 30
Выходные данные:
Enter the path to file with data about graph: test4.txt
Enter the vertex number for which you want to find unattainable summit: 0
[0]-->{1}-->{11}-->NULL
[11]-->{12}-->NULL
[1]-->{2}-->NULL
[2]-->{3}-->NULL
[3]-->{4}-->{16}-->{15}-->{14}-->{12}-->NULL
[12]-->{22}-->NULL
[14]-->NULL
[15]-->{25}-->NULL
[16]-->{23}-->NULL
[4]-->{17}-->NULL
[17]-->{6}-->NULL
[5]-->{6}-->{4}-->NULL
[6]-->NULL
[7]-->{6}-->NULL
[8]-->{19}-->NULL
[19]-->{21}-->{44}-->{18}-->NULL
[9]-->{20}-->NULL
[20]-->{19}-->NULL
[10]-->{21}-->{9}-->NULL
[21]-->NULL
[22]-->{23}-->NULL
[13]-->{14}-->{22}-->NULL
[25]-->{26}-->{35}-->NULL
[23]-->{13}-->{35}-->{34}-->NULL
[18]-->{8}-->{6}-->NULL
[44]-->{30}-->NULL
[34]-->{24}-->NULL
[35]-->NULL
[26]-->{38}-->{37}-->NULL
[37]-->NULL
[38]-->{39}-->NULL
[27]-->{38}-->{17}-->{26}-->NULL
[28]-->{18}-->{39}-->NULL
[39]-->{40}-->NULL
[29]-->{30}-->{18}-->{39}-->NULL
[30]-->{41}-->NULL
[41]-->NULL
[31]-->{30}-->NULL
[32]-->{31}-->NULL
[33]-->{34}-->{22}-->NULL
[24]-->NULL
[36]-->{26}-->NULL
[40]-->{30}-->NULL
[42]-->{41}-->{31}-->NULL
[43]-->{32}-->{30}-->NULL
Unreachable vertices: 5 7 8 9 10 18 19 20 21 27 28 29 31 32 33 36 42 43 44
Результаты работы программы
Программа работает корректно при различных входных данных, что подтверждено тестами.
|
|
|
