Въведение в графите.

Visual Basic, C#, C++, Python и др.
Потребителски аватар
[BG][SSA]Troll
Модератор
Мнения: 17
Регистриран: вт юли 10, 2018 9:35 pm
Баланс: Locked
Местоположение: Велико Търново

пет юли 13, 2018 4:17 pm

Тъпата дефиниция за граф е: Съвкупност от върхове и ребра, използваща се за представяне на обекти и техните връзки. След тази дефиниция много хора ще се отчаят от живота, но нека да го приемем само като кръгчета свързани с дъги. Та сега ще изникнат въпроси от сорта на, "Какво ще правя с тоя граф?". Веднага отговарям. С графи могат да се моделират и решат много практически задачи, като например най-къс път от точка А до точка Б. По колко различни начина мога да стигна от точка А до точка Б. Колко най-много неща мога да прекарам от точка А до точка Б ако всеки път има определена вместимост и т.н. Услуги като GPS навигацията и Google картите работят с графи. Ето един примерен граф с който ще си служа по долу:
Изображение
Така малко теория. Кръгчетата се наричат върхове, а дъгите, които ги свързват-ребра. Всяко ребро може да има свое тегло(Използва се за означаване на дължина на път между върховете или цена на пътя) и посока. Ако едно ребро няма посока, то се счита за двупосочно. Ако ребрата в графа имат посоки, то той е насочен. Ако имат тегло, то той е претеглен. Ако има път между всеки 2 върха в граф, то той се нарича пълен. Цифрата във всеки връх се нарича тегло на връх. Едно ребро се представя със двойка върхове a и b и това ребро се казва, че е инцидентно на a и b. Например реброто 1-2 е инцидентно на върхове 1 и 2. Двойка ребра са инцидентни, ако имат общ връх. Например ребро 1-2 е инцидентно на ребро 2-4 и ребро 3-2. Не е трудно нали. Обаче някой хора веднага ще попитат. "Как това ще го предам на компютъра. Немога просто на c++ да му предам ето тази картинка?". Веднага обяснявам. Граф може да се представи по 2 начина.

Първият начин е чрез матрица на съседство.

Какво представлява матрицата на съседство? Тя представлява квадратна матрица n*n, където n е броят на върховете.
Номерът на реда съответства на първия връх, определящ реброто, а номера на колоната - на втория. По подразбиране матрицата е пълна с нули и за всяко ребро правите mat[v1][v2]=1. Където v1 е първият връх, а v2 - вторият. Ако графът не е насочен правите и mat[v2][v1]=1. И така означавате, че има път между тези ребра. Ето как изглежда това на код:

Код: Трябва да си влязъл в системата, за да можеш да виждаш линковете

#include <iostream>

using namespace std;

int mat[501][501];//da kajem che imame max 500 vurha :) 

int main()
{
	int n,m;//n vurha,m rebra
	cin>>n>>m;
	int a,b;//vruh a i vruh b na rebroto
	for(int i=0;i<m;i++)
	{
	cin>>a>>b;
	mat[a][b]=1;
	mat[b][a]=1;
	} 
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cout<<mat[i][j]<<" ";
		}
		cout<<endl;
	}
}
Интересен факт е, че матрицата на съседство на ненасочен граф е симетрична спрямо главния диагонал.

Вторият начин е чрез списък на съседство.

Какво представлява списъкът на съседство? Той представлава масив от n вектора, където n е броят върхове в графа. Всеки вектор отговаря за един връх. Във вектора на върха се записват съседите му, ако графът не е насочен, то и във вектора на съседите му се записва дадения връх. Ето реализацията на код на списъците на съседство.

Код: Трябва да си влязъл в системата, за да можеш да виждаш линковете

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n,m;
	cin>>n>>m;
	vector<int>gr[501];
	int a,b;
	for(int i=0;i<m;i++)
	{
		cin>>a>>b;
		gr[a].push_back(b);
		gr[b].push_back(a);
	}
	for(int i=1;i<=n;i++)
	{
		cout<<"Susedi na "<<i<<": ";
		for(int j=0;j<gr[i].size();j++)
		{
			cout<<gr[i][j]<<" ";
		}
		cout<<endl;
	}
}
Надявам се урокът да ви е бил полезен и интересен. Ако имате въпроси пишете ми на ЛС.
Последна промяна от [BG][SSA]Troll на пет юли 13, 2018 5:48 pm, променено общо 1 път.

Потребителски аватар
MADNESS
Администратор
Администратор
Мнения: 23
Регистриран: пон юли 09, 2018 12:56 am
Баланс: Locked
Местоположение: Sofia
Контакти:

пет юли 13, 2018 4:26 pm

Едно голямо БРАВО урока е супер и ще е от полза на хората които се интересуват.
продължавай в същия дух ;)

Отговори

Върни се в “Системно Програмиране”

  • Информация
  • Кой е на линия

    Потребители, разглеждащи този форум: Няма регистрирани потребители и 0 госта