---
# System prepended metadata

title: 'Graph terminology:'

---

# Graph terminology:
* 	**Vertex** (Node) - grafning uchi
*	**Edge** - grafning ikki uchini bog'lovchi qirra
*	**Undirected graph** - Yo'naltirilmagan graf
*	**Directed graph** - Yo'naltirilgan graf
*	**Neighbor/adjacent vertex/node** - orasida **edge** bo'lgan ikkita qo'shni **vertex**
*	**Weighted graph** - har bir **edge** o'zining qiymatiga/vazniga ega bo'ladi
*	**Path** - A uchdan B uchga borish yo'li: A -> D -> C -> B
*	**Length of path** - **path**dagi **edge**lar soni
*	**Cycle** - Bitta **vertex**dan boshlanib, yana o'sha **vertex**da tugaydigan **path**: 1 -> 2 -> 3 -> 1
*	**Simple path** - **path** simple hisoblanadi, agar **path**da har bir **vertex** ko'pi bilan 1 marta qatnashsa.
*	**Connected graph** - istalgan ikkita **vertex**idan bir-biriga **path** mavjud bo'lgan **graph**
*	**Componenta** - bog'langan **vertex**lar to'plami
*	**Tree** - **cycle**larsiz **connected graph**
*	**Full graph** - mumkin bo'lgan hamma **edge**lar o'tkazilgan **graph**. 
*	**Vertex**lar soni N ta bo'lgan **full graph**da N*(N-1)/2 ta **edge** bo'ladi.
	
# Graph representation:
* **Adjacency list representation** - qo'shnilik ro'yxati: O(n)
    * **Pseudo**:\
		1 -> 3,5,6 \
		2 -> 3\
		3 -> 1,2,4\
		4 -> 3\
		5 -> 1\
		6 -> 1
	* C++:
	```cpp
		vector<vector<int>> vc;
		vc.resize(7);
		vc[1]={3,5,6};
		vc[2]={3};
		vc[3]={1,2,4};
		vc[4]={3};
		vc[5]={1};
		vc[6]={1};
	```
    
	* For weighted graphs:\
		1 -> {3,3},{5,1},{6,8}\
		2 -> {3,2}\
		3 -> {1,3},{2,2},{4,5}\
		4 -> {3,5}\
		5 -> {1,1}\
		6 -> {1,8}
	* Weighted in C++:
	```cpp
		vector<vector<pair<int,int>>> vc;
		vc.resize(7);
		vc[1]={{3,3},{5,1},{6,8}};
		vc[2]={{3,2}};
		vc[3]={{1,3},{2,2},{4,5}};
		vc[4]={{3,5}};
		vc[5]={{1,1}};
		vc[6]={{1,8}};
	
	```
* **Adjacency matrix representation** - qo'shnilik matritsasi: O(n^2)

	|       | 1 | 2 | 3 | 4 | 5 | 6 |
    | ----- | - | - | - | - | - | - |
	| **1** | 0 | 0 | 1 | 0 | 1 | 1 |
	| **2** | 0 | 0 | 1 | 0 | 0 | 0 |
	| **3** | 1 | 1 | 0 | 1 | 0 | 0 |
	| **4** | 0 | 0 | 1 | 0 | 0 | 0 |
	| **5** | 1 | 0 | 0 | 0 | 0 | 0 |
	| **6** | 1 | 0 | 0 | 0 | 0 | 0 |

	
	* For weighted graphs:
		
	|       | 1 | 2 | 3 | 4 | 5 | 6 |
    | ----- | - | - | - | - | - | - |
	| **1** | 0 | 0 | 3 | 0 | 1 | 8 |
	| **2** | 0 | 0 | 2 | 0 | 0 | 0 |
	| **3** | 3 | 2 | 0 | 5 | 0 | 0 |
	| **4** | 0 | 0 | 5 | 0 | 0 | 0 |
	| **5** | 1 | 0 | 0 | 0 | 0 | 0 |
	| **6** | 8 | 0 | 0 | 0 | 0 | 0 |
	
	
* **Edge list representation** - qirralar ro'yxati: O(n)
	```cpp
	[{1,3},{1,5},{1,6},{2,3},{3,4}]
	vector<pair<int,int>> vc;
	```
	* For weighted graphs:
	```cpp
	[{1,3,3},{1,5,1},{1,6,8},{2,3,2},{3,4,5}]
	vector<tuple<int,int,int>> vc;
    ```

# Yo'naltirilgan grafni 'Edge list representation' ko'rinishidan 'Adjacency list representation' ko'rinishiga o'tkazish
```cpp=
#include <iostream>
#include <vector>

using namespace std;

const int N=111;

int main(){
 int n, m;
 vector<vector<int>> vc;
 
 cin >> n >> m;
 
 vc.resize(n+1);
 
 for (int i=0; i<m; ++i){
  int u, v;
  
  cin >> u >> v;
  
  vc[u].push_back(v);
 }
 
 cout << n << '\n';
 for (int i=1; i<=n; ++i){
  cout << vc[i].size() << " ";
  for (int j=0; j<vc[i].size(); ++j){
   cout << vc[i][j] << " ";
  }
  cout << '\n';
 }
}
```