лабораторная Графы. Отчет по лабораторной работе 2 по дисциплине Структуры и алгоритмы обработки данных в эвм
 Скачать 243.52 Kb.
|
|
Министерство образования и науки Российской Федерации Федеральное государственное образовательное учреждение высшего профессионального образования «ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ» (ТУСУР) Кафедра автоматизированных систем управления (АСУ) Графы Отчет по лабораторной работе №2 по дисциплине «Структуры и алгоритмы обработки данных в ЭВМ» Выполнил студент: Тарасов Евгений Максимович специальности 09.03.01 гр. з-430П10-1 «24» октября 2022г. Проверил: « » 2022г. 2022г. СОДЕРЖАНИЕ 1. Тема работы…...…………………………………………………….……3 2. Цель работы..………………………………………………………......…3 3. Индивидуальное задание………………………………….…...………...3 4. Алгоритм решения задачи………………………………………………3 5. Результаты работы программы...………………………...……...………6 6. Выводы………………...………………………………….………...……7 Приложение А. Листинг программы…………………………………...…8 Тема работы: «Графы». Цель работы: получить практические навыки представления графов в памяти ЭВМ, реализовать на языке программирования C/C++ алгоритмы работы с графами. Индивидуальное задание: Вариант № 3 Используя метод поиска в ширину, в неориентированном графе, найти и вывести все вершины, достижимые из заданной. Номер начальной вершины ввести с клавиатуры. Граф задан в текстовом файле матрицей смежности. Достижимые вершины выводить в порядке их посещения. Алгоритм решения задачи: Мы используем неориентированный граф с 5 вершинами.  Мы начнем с вершины 0, алгоритм BFS начинается с помещения его в список посещенных и размещения всех смежных вершин в стеке. (BFS- поиск в ширину)  Затем мы посещаем элемент в начале очереди, то есть 1, и переходим к соседним узлам. Так как 0 уже был посещен, мы посещаем 2.  У вершины 2 есть соседняя не посещенная вершина 4, поэтому мы добавляем ее в конец очереди и посещаем 3, которая находится в начале очереди.  В очереди остается только 4, поскольку единственный соседний узел с 3, то есть 0, уже посещен. Мы посещаем вершину 4.  Поскольку очередь пуста, мы завершили обход в ширину графика. BFS псевдокод create a queue Q mark v as visited and put v into Q while Q is non-empty remove the head u of Q mark and enqueue all (unvisited) neighbours of u Результаты работы программы:  Вывод: В ходе данной лабораторной работы, я получил практические навыки представления графов в памяти ЭВМ, затем реализовал на языке программирования C/C++ алгоритм работы с графами. Приложение А. Листинг программы. Язык программирования С. #include <stdio.h> #include #define SIZE 40 struct queue { int items[SIZE]; int front; int rear; }; struct queue* createQueue(); void enqueue(struct queue* q, int); int dequeue(struct queue* q); void display(struct queue* q); int isEmpty(struct queue* q); void printQueue(struct queue* q); struct node { int vertex; struct node* next; }; struct node* createNode(int); struct Graph { int numVertices; struct node** adjLists; int* visited; }; struct Graph* createGraph(int vertices); void addEdge(struct Graph* graph, int src, int dest); void printGraph(struct Graph* graph); void bfs(struct Graph* graph, int startVertex); int main() { struct Graph* graph = createGraph(6); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 1, 2); addEdge(graph, 1, 4); addEdge(graph, 1, 3); addEdge(graph, 2, 4); addEdge(graph, 3, 4); bfs(graph, 0); return 0; } void bfs(struct Graph* graph, int startVertex) { struct queue* q = createQueue(); graph->visited[startVertex] = 1; enqueue(q, startVertex); while(!isEmpty(q)){ printQueue(q); int currentVertex = dequeue(q); printf("Visited %d\n", currentVertex); struct node* temp = graph->adjLists[currentVertex]; while(temp) { int adjVertex = temp->vertex; if(graph->visited[adjVertex] == 0){ graph->visited[adjVertex] = 1; enqueue(q, adjVertex); } temp = temp->next; } } } struct node* createNode(int v) { struct node* newNode = malloc(sizeof(struct node)); newNode->vertex = v; newNode->next = NULL; return newNode; } struct Graph* createGraph(int vertices) { struct Graph* graph = malloc(sizeof(struct Graph)); graph->numVertices = vertices; graph->adjLists = malloc(vertices * sizeof(struct node*)); graph->visited = malloc(vertices * sizeof(int)); int i; for (i = 0; i < vertices; i++) { graph->adjLists[i] = NULL; graph->visited[i] = 0; } return graph; } void addEdge(struct Graph* graph, int src, int dest) { // Add edge from src to dest struct node* newNode = createNode(dest); newNode->next = graph->adjLists[src]; graph->adjLists[src] = newNode; // Add edge from dest to src newNode = createNode(src); newNode->next = graph->adjLists[dest]; graph->adjLists[dest] = newNode; } struct queue* createQueue() { struct queue* q = malloc(sizeof(struct queue)); q->front = -1; q->rear = -1; return q; } int isEmpty(struct queue* q) { if(q->rear == -1) return 1; else return 0; } void enqueue(struct queue* q, int value){ if(q->rear == SIZE-1) printf("\nQueue is Full!!"); else { if(q->front == -1) q->front = 0; q->rear++; q->items[q->rear] = value; } } int dequeue(struct queue* q){ int item; if(isEmpty(q)){ printf("Queue is empty"); item = -1; } else{ item = q->items[q->front]; q->front++; if(q->front > q->rear){ printf("Resetting queue"); q->front = q->rear = -1; } } return item; } void printQueue(struct queue *q) { int i = q->front; if(isEmpty(q)) { printf("Queue is empty"); } else { printf("\nQueue contains \n"); for(i = q->front; i < q->rear + 1; i++) { printf("%d ", q->items[i]); } } } |