{%hackmd theme-dark %}

# Grafos I

###### tags: `conteudo` `grafo` `ps2020` `dfs` `toposort`

## Definição
Um grafo é um par ordenado G(V, E), onde:
* V é um conjunto finito não vazio de vértices.
* E é um conjunto de pares de vértices

G1: V = {v1, v2, v3}, E = {v1v2, v2v3}


## Tipos de grafos




## Representação

4 4 (n m (nº de vértices e nº de arestas)

1 2
1 3
2 3
3 4
4 3

* Matriz de adjacência


0 1 1 0
0 0 1 0
0 0 0 1
0 0 1 0

const int N = 1e3;

int n, m;
int adj[N][N];
int main() {
  scanf("%d%d", &n, &m);
  
  for(int i = 0; i < n=m; i++) {
    int a, b;
    scanf("%d%d%d", &a, &b);
    adj[a][b] = 1;
  }
}


0 5 3 0
5 0 1 0
3 1 0 4
0 0 4 0

const int N = 1e5;

int n, m;
int adj[N][N];
int main() {
  scanf("%d%d", &n, &m);
  
  for(int i = 0; i < n=m; i++) {
    int a, b, c;
    scanf("%d%d", &a, &b, &c);
    adj[a][b] = c;
    adj[b][a] = c;
  }
}

* Lista de adjacência


1: 2, 3
2: 3
3: 3
4: 3

int n, m;
vector<int> adj[N];

int main() {
  scanf("%d%d", &n, &m);
  
  for(int i = 0; i < n=m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    adj[a].push_back(b);
  }
}


int n, m;
vector<pair<int, int>> adj[N];

int main() {
  scanf("%d%d", &n, &m);
  
  for(int i = 0; i < n=m; i++) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    
    adj[a].push_back({b, c});
    adj[b].push_back({a, c});
  }
}

## Percurso em grafo
* DFS (Depth First Search)


  vector<int> adj[N];
  int vis[N];
  
  void dint uf {
    if(vis[u]) return;
    vis[u] = 1;
    
    for(int v: adj[u]) {
      dfs(v);
    }
    /*
    for(int i = 0; i < adj[u].size(); i++) {
      dfs(adj[u]);
    }
    */
   

* BFS (Breadth First Search)


int vis[N];

void bfs() {
  queue<int> q;
  
  q.push(1);
  vis[1] = 1;
  
  while(!q.empty()) {
    int u = q; 
    q.pop();
    
    for(int v: adj[u]) {
      if(!vis[v]) {
        q.push(v);
        vis[v] = vis[u] + 1;
      }
 

## Propriedades do Grafo
* Excentricidade de um nó
Maior distância entre esse nó e qualquer outro
* Diâmetro do grafo
Maior excentricidade em um grafo
* Raio do grafo
Menor excentricidade em um grafo
* Centro do grafo
Subconjunto dos nós que possuem a menor excentricidade

## Árvores

* Grafo acíclico conectado
* e = v - 1
* Uma ou mais árvores formam um floresta

### Centróide
* Nó que se removido de uma árvore gerará uma floresta tal que todas as árvores têm no máximo n/2 vértices
* Toda árvore tem 1 ou 2 centróides

## DAG (Directed Aciclic Graph)


### Topogical sort

F E C D B G A

#### DFS

vector<int> ord;
void toposort(int u) {
  if(vis[u]) return;
  vis[u] = 1;
  
  for(int v: adj[u]) {
    toposort(v);
  }
  ord.push_back(u);
}

#### Algoritimo de Kahn

ndep[A] = 1
ndep[B] = 3
...

adj[u] = lista de dependências de u
adjrev[u] = lista de nós que dependem de u

int ndep[N];
vector<int> adjrev[N], adj[N];
vector<int> ord;

queue<int> process;

int main() {
 
  ....
  for(int i = 0; i < n; i++) if(ndep[u] == 0) process.push[u];

  while(!q.empty()) {
    int u = q.front();
    q.pop();
    ord.push_back(u);
    
    for(int v: revadj[u]) {
      ndep[v]--;

      if(ndep[v] == 0) q.push(v);
    }
  }
}