Частина І Способи обходу графів: DFS та BFS алгоритми
Теоретичні відомості
Вільним деревом називають дерево, в якому невизначений корінь або ж (що те саме)
ациклічний зв’язний граф.
Каркасним деревом графа G називається вільне дерево, яке містить всі вершини даного графа.
В процесі обходу графа методом пошуку в глибину будується каркасне дерево, яке
називають глибинним каркасним деревом (лісом).
Для простих графів:
- ребра, які ведуть до вершин, що раніше не відвідувалися, називають ребрами
глибинного дерева;
- зворотні ребра – ребра («штрихові»), які ведуть до вершин, що вже відвідувалися.
Для орграфів:
- дуги глибинного дерева – дуги, які в каркасному дереві ведуть від предків до
нащадків;
- прямі дуги – дуги, які йдуть від предків до істинних нащадків, але не є дугами
каркасного дерева («штрихові»);
- зворотні дуги – дуги, ведуть від нащадків до предків глибинного каркасного
дерева («штрихові»). Дуга, яка веде із вершини в саму себе, теж називається зворо-
тньою;
- поперечні дуги – дуги, які пов’язують вершини, що не є ні предками, ні нащад-
ками одна одної («штрихові»).
Пошук в глибину у простому зв’язному графі або DFS-метод (Dipth First
Search)
Нехай G=(V, E) – простий зв’язний граф, усі вершини якого позначені попарно різними символами. У процесі пошуку вглиб вершинам надають DFS - номери та певним чином помічають ребра
Крок 1. Почати з довільної вершини vs. Покласти DFS(vs)=1. Включити цю вершину у стек.
Крок 2. Розглянути вершину, яка знаходиться у верхівці стека. Нехай це буде вершина x. Якщо всі ребра, інцидентні цій вершині, позначені, то перейти до кроку 4, інакше
– до кроку 3.
Крок 3. Нехай {x, y} – непозначене ребро. Якщо DFS(y) уже визначений, то це ребро позначити штриховою лінією і перейти до кроку 2. Якщо DFS(y) не визначений, то дане
ребро позначити суцільною лінією, визначити DFS(y) як черговий DFS-номер, включити цю вершину до стека і перейти до кроку 2.
Крок 4. Виключити вершину x зі стека. Якщо стек порожній, то зупинитись, інакше – перейти до кроку 2.
Для однозначності вибору номерів доцільно домовитись, що аналіз вершин, суміж-
них з вершиною, яка вже отримала DFS-номер, здійснюють за зростанням їх порядкового номера (або ж у алфавітному порядку) .
Динаміку DFS-обходу відображають за допомогою таблиці з трьома стовпцями: вер-
шина, DFS-номер, вміст стека. Цю таблицю називають DFS-протоколом.
Пошук в ширину або BFS-метод (Breadth First Search)
Нехай G=(V, E) – простий зв’язний граф, усі вершини якого позначені попарно різними символами. У процесі пошуку вглиб вершинам надають DFS - номери та певним
чином помічають ребра.
Крок 1. Почати з довільної вершини vs. Покласти BFS(vs)=1. Включити цю вершину у чергу.
Крок 2. Розглянути вершину, яка знаходиться на початку черги: нехай це буде вершина x. Якщо для всіх вершин, мімічних з нею , вже визначені BFS-номери, то перейти
до кроку 4, інакше – до кроку 3.
Крок 3. Нехай y –вершина, для якої ще не визначений DFS-номер. Ребро {x,y} позначити суцільною лінією, визначити BFS(y) як черговий BFS-номер, включити цю вер-
шину до черги і перейти до кроку 2.
Крок 4. Виключити вершину x з черги. Якщо черга порожня, то зупинитись, інакше – перейти до кроку 2.
Аналогічно, як і для DFS-обходу, для однозначності вибору номерів доцільно домовитись, що аналіз вершин, суміжних з вершиною, яка вже отримала BFS-номер, здійснюють за зростанням їх порядкового номера (або ж у алфавітному порядку) .
Динаміку BFS-обходу відображають за допомогою таблиці з трьома стовпцями: вер-
шина, BFS-номер, вміст черги. Цю таблицю називають BFS-протоколом
Розглянемо приклад (зразок графа дивись в минулому алгоритмі пошуку)
Результат BFS-обходу, починаючи з вершини v1: v1 -> v2 -> v5 -> v3 -> v4
1 Виконати обходи в глибину та в ширину графів зі своїх варіантів (беремо їх з
практичної роботи No6), оформивши результати, як показано вище. Номер варіанту
вибирати згідно номера по журналу.
код:
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <list>
#include <iomanip>
using namespace std;
int n = 6, e = 0; // n - вершини e - ребра
struct Graph {
	vector<vector<int> > adjMatrix;
	vector<vector<int> > incidenceMatrix;
	//map<int, list<int> > adjList;
	//map<int, list<int> > incidenceList;
	Graph(int n) : adjMatrix(n, vector<int>(n, 0)) {}
	void clearInc() {
		incidenceMatrix.clear();
	}
	void resizeInc(int edges) {
		incidenceMatrix.resize(n, vector<int>(edges, 0));
	}
	void addEdgeAdj(int u, int v)
	{
		adjMatrix[u][v] = 1;
		adjMatrix[v][u] = 1;
	}
	void addEdgeAdjDirected(int u, int v)
	{
		adjMatrix[u][v] = 1;
	}
	void addEdgeInc(int vertex1, int vertex2, int edgeIndex)
	{
		if (vertex1 >= 0 && vertex1 < n && vertex2 >= 0
			&& vertex2 < n && edgeIndex >= 0
			&& edgeIndex < e) {
			incidenceMatrix[vertex1][edgeIndex] = 1;
			incidenceMatrix[vertex2][edgeIndex] = 1;
		}
	}
	void addEdgeIncDirected(int vertex1, int vertex2, int edgeIndex)
	{
		if (vertex1 >= 0 && vertex1 < n && vertex2 >= 0
			&& vertex2 < n && edgeIndex >= 0
			&& edgeIndex < e) {
			incidenceMatrix[vertex1][edgeIndex] = 1;
			incidenceMatrix[vertex2][edgeIndex] = -1;
		}
	}
	void printAndSaveInFile(ofstream& file, string header, char* labels[], bool isAdjMatrix)
	{
		cout << header;
		file << header;
		int size = isAdjMatrix ? adjMatrix.size() : incidenceMatrix.size();
		if (isAdjMatrix) {
			for (int i = 0; i < size; i++) {
				cout << labels[i] << " ";
				file << labels[i] << " ";
				for (int j = 0; j < size; j++) {
					file << adjMatrix[i][j] << " ";
					cout << adjMatrix[i][j] << " ";
				}
				cout << endl;
				file << endl;
			}
		}
		else {
			for (int i = 0; i < size; i++) {
				cout << labels[i] << " ";
				file << labels[i] << " ";
				for (int j = 0; j < e; j++) {
					file << setw(2) << incidenceMatrix[i][j] << " ";
					cout << setw(2) << incidenceMatrix[i][j] << " ";
				}
				cout << endl;
				file << endl;
			}
		}
	}
	void printListEdges(ofstream& file, string header, char* labels[]) {
		file << header;
		cout << header;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (adjMatrix[i][j] == 1) {
					file << labels[i] << " -> " << labels[j] << "\n";
					cout << labels[i] << " -> " << labels[j] << "\n";
				}
			}
		}
	}
	void printListAdj(ofstream& file, string header, char* labels[]) {
		file << header;
		cout << header;
		for (int i = 0; i < n; i++) {
			file << labels[i] << ": ";
			cout << labels[i] << ": ";
			for (int j = 0; j < n; j++) {
				if (adjMatrix[i][j] == 1) {
					file << labels[i] << " -> " << labels[j] << ' ';
					cout << labels[i] << " -> " << labels[j] << ' ';
				}
			}
			file << "\n";
			cout << "\n";
		}
	}
};
// 2 завдання
void buildEdgeList(const vector<vector<int>>& incidenceMatrix, bool isDirected, char* labels[], ofstream& file) {
	int vertices = incidenceMatrix.size();
	int edges = incidenceMatrix[0].size();
	cout << "Список ребер:\n";
	file << "Список ребер:\n";
	for (int e = 0; e < edges; e++) {
		int vertex1 = -1, vertex2 = -1;
		for (int v = 0; v < vertices; v++) {
			if (isDirected) {
				if (incidenceMatrix[v][e] == 1) vertex1 = v;
				if (incidenceMatrix[v][e] == -1) vertex2 = v;
			}
			else {
				if (incidenceMatrix[v][e] == 1) {
					if (vertex1 == -1) vertex1 = v;
					else vertex2 = v;
				}
			}
		}
		if (vertex1 != -1 && vertex2 != -1) {
			cout << labels[vertex1] << " -> " << labels[vertex2] << "\n";
			file << labels[vertex1] << " -> " << labels[vertex2] << "\n";
		}
	}
}
vector<vector<int>> buildAdjacencyMatrix(const vector<vector<int>>& incidenceMatrix, bool isDirected, ofstream& file, char* labels[]) {
	int vertices = incidenceMatrix.size();
	int edges = incidenceMatrix[0].size();
	vector<vector<int>> adjacencyMatrix(vertices, vector<int>(vertices, 0));
	for (int e = 0; e < edges; e++) {
		int vertex1 = -1, vertex2 = -1;
		for (int v = 0; v < vertices; v++) {
			if (isDirected) {
				if (incidenceMatrix[v][e] == 1) vertex1 = v;
				if (incidenceMatrix[v][e] == -1) vertex2 = v;
			}
			else {
				if (incidenceMatrix[v][e] == 1) {
					if (vertex1 == -1) vertex1 = v;
					else vertex2 = v;
				}
			}
		}
		if (vertex1 != -1 && vertex2 != -1) {
			adjacencyMatrix[vertex1][vertex2] = 1;
			if (!isDirected) {
				adjacencyMatrix[vertex2][vertex1] = 1;
			}
		}
	}
	cout << "Матриця суміжності:\n";
	file << "Матриця суміжності:\n";
	for (int i = 0; i < vertices; i++) {
		cout << labels[i] << ": ";
		file << labels[i] << ": ";
		for (int j = 0; j < vertices; j++) {
			cout << adjacencyMatrix[i][j] << " ";
			file << adjacencyMatrix[i][j] << " ";
		}
		cout << endl;
		file << endl;
	}
	return adjacencyMatrix;
}
void buildAdjacencyList(const vector<vector<int>>& incidenceMatrix, bool isDirected, char* labels[], ofstream& file) {
	int vertices = incidenceMatrix.size();
	int edges = incidenceMatrix[0].size();
	vector<vector<int>> adjacencyList(vertices);
	for (int e = 0; e < edges; e++) {
		int vertex1 = -1, vertex2 = -1;
		for (int v = 0; v < vertices; v++) {
			if (isDirected) {
				if (incidenceMatrix[v][e] == 1) vertex1 = v;
				if (incidenceMatrix[v][e] == -1) vertex2 = v;
			}
			else {
				if (incidenceMatrix[v][e] == 1) {
					if (vertex1 == -1) vertex1 = v;
					else vertex2 = v;
				}
			}
		}
		if (vertex1 != -1 && vertex2 != -1) {
			adjacencyList[vertex1].push_back(vertex2);
			if (!isDirected) {
				adjacencyList[vertex2].push_back(vertex1);
			}
		}
	}
	cout << "Список суміжності:\n";
	file << "Список суміжності:\n";
	for (int v = 0; v < vertices; v++) {
		cout << labels[v] << ": ";
		file << labels[v] << ": ";
		for (int adj : adjacencyList[v]) {
			cout << labels[v] << " -> " << labels[adj] << " ";
			file << labels[v] << " -> " << labels[adj] << " ";
		}
		cout << "\n";
		file << "\n";
	}
}
int main()
{
	ofstream file("graph.txt");
	Graph g(n);
	char** labels = new char* [n];
	for (int i = 0; i < n; i++) {
		labels[i] = new char[2];
		labels[i][0] = 'a' + i;
		labels[i][1] = '\0';
	}
	g.addEdgeAdj(0, 1); // 1
	g.addEdgeAdj(0, 3); // 2
	g.addEdgeAdj(1, 3); // 3
	g.addEdgeAdj(1, 4); // 4
	g.addEdgeAdj(1, 5); // 5
	g.addEdgeAdj(2, 2); // 6
	g.addEdgeAdj(2, 3); // 7
	g.addEdgeAdj(2, 4); // 8
	g.addEdgeAdj(2, 5); // 9
	e = 9;
	g.resizeInc(e);
	g.printAndSaveInFile(file,
		"Неорієнтований граф - Матриця суміжності:\n\
  a b c d e f\n", labels, true); // суміжність
	g.addEdgeInc(0, 1, 0); // ab
	g.addEdgeInc(0, 3, 1); // ad
	g.addEdgeInc(1, 3, 2); // bd
	g.addEdgeInc(1, 4, 3); // be
	g.addEdgeInc(1, 5, 4); // bf
	g.addEdgeInc(2, 2, 5); // cc
	g.addEdgeInc(2, 3, 6); // cd
	g.addEdgeInc(2, 4, 7); // ce
	g.addEdgeInc(2, 5, 8); // cf
	g.printAndSaveInFile(file,
		"Неорієнтований граф - Матриця інцидентності:\n\
  ab ad bd be bf cc cd ce cf\n", labels, false); // інцидентність
	g.printListEdges(file, "Неорієнтований граф - Список ребер:\n", labels);
	g.printListAdj(file, "Неорієнтований граф - Список суміжності:\n", labels);
	Graph g2(n);
	g2.addEdgeAdjDirected(0, 1); // 1
	g2.addEdgeAdjDirected(0, 3); // 2
	g2.addEdgeAdjDirected(0, 4); // 3
	g2.addEdgeAdjDirected(1, 2); // 4
	g2.addEdgeAdjDirected(1, 3); // 5
	g2.addEdgeAdjDirected(1, 5); // 6
	g2.addEdgeAdjDirected(2, 4); // 7
	g2.addEdgeAdjDirected(2, 5); // 8
	g2.addEdgeAdjDirected(3, 2); // 9
	g2.addEdgeAdjDirected(3, 4); // 10
	g2.addEdgeAdjDirected(4, 5); // 11
	e = 11;
	g2.resizeInc(e);
	g2.printAndSaveInFile(file,
		"Орієнтований граф - Матриця суміжності:\n\
  a b c d e f\n", labels, true); // суміжність
	g2.addEdgeIncDirected(0, 1, 0);  // ab
	g2.addEdgeIncDirected(0, 3, 1);  // ad
	g2.addEdgeIncDirected(0, 4, 2);  // ae
	g2.addEdgeIncDirected(1, 2, 3);  // bc
	g2.addEdgeIncDirected(1, 3, 4);  // bd
	g2.addEdgeIncDirected(1, 5, 5);  // bf
	g2.addEdgeIncDirected(2, 4, 6);  // ce
	g2.addEdgeIncDirected(2, 5, 7);  // cf
	g2.addEdgeIncDirected(3, 2, 8);  // dc
	g2.addEdgeIncDirected(3, 4, 9);  // de
	g2.addEdgeIncDirected(4, 5, 10); // ef
	g2.printAndSaveInFile(file,
		"Орієнтований граф - Матриця інцидентності:\n\
   ab ad ae bc bd be bf ce cf dc de\n", labels, false); // інцидентність
	g2.printListEdges(file, "Орієнтований граф - Список ребер:\n", labels);
	g2.printListAdj(file, "Орієнтований граф - Список суміжності:\n", labels);
	// 2 завдання
	vector<vector<int>> undirectedIncMatrix = {
		//  ab  ac  bc  cd  de  ce
			{1,  1,  0,  0,  0,  0},  // a
			{1,  0,  1,  0,  0,  0},  // b
			{0,  1,  1,  1,  0,  1},  // c
			{0,  0,  0,  1,  1,  0},  // d
			{0,  0,  0,  0,  1,  1}   // e
	};
	cout << "\n=== Неорієнтований граф ===\n";
	file << "\n=== Неорієнтований граф ===\n";
	cout << "\nМатриця інцидентності:\n";
	file << "\nМатриця інцидентності:\n";
	for (int i = 0; i < 5; i++) {
		cout << labels[i] << ": ";
		file << labels[i] << ": ";
		for (int j = 0; j < 6; j++) {
			cout << undirectedIncMatrix[i][j] << " ";
			file << undirectedIncMatrix[i][j] << " ";
		}
		cout << endl;
		file << endl;
	}
	buildEdgeList(undirectedIncMatrix, false, labels, file);
	vector<vector<int>> undirectedAdjMatrix = buildAdjacencyMatrix(undirectedIncMatrix, false, file, labels);
	buildAdjacencyList(undirectedIncMatrix, false, labels, file);
	// Орієнтований граф
	vector<vector<int>> directedIncMatrix = {
		//   ab   ac   bd   cd   de   ec   ea
			{1,   1,   0,   0,   0,   0,   -1},  // a
			{-1,  0,   1,   0,   0,   0,   0},   // b
			{0,   -1,  0,   1,   0,   -1,  0},   // c
			{0,   0,   -1,  -1,  1,   0,   0},   // d
			{0,   0,   0,   0,   -1,  1,   1}    // e
	};
	cout << "\n=== Орієнтований граф ===\n";
	file << "\n=== Орієнтований граф ===\n";
	cout << "\nМатриця інцидентності:\n";
	file << "\nМатриця інцидентності:\n";
	for (int i = 0; i < 5; i++) {
		cout << labels[i] << ": ";
		file << labels[i] << ": ";
		for (int j = 0; j < 7; j++) {
			cout << setw(2) << directedIncMatrix[i][j] << " ";
			file << setw(2) << directedIncMatrix[i][j] << " ";
		}
		cout << endl;
		file << endl;
	}
	buildEdgeList(directedIncMatrix, true, labels, file);
	vector<vector<int>> directedAdjMatrix = buildAdjacencyMatrix(directedIncMatrix, true, file, labels);
	buildAdjacencyList(directedIncMatrix, true, labels, file);
	for (int i = 0; i < n; i++) {
		delete[] labels[i];
	}
	delete[] labels;
	file.close();
	return 0;
}