Текст программы
Файл 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
