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);
    }
  }
}