Grafos_Parte1_DFSR_final

Prévia do material em texto

Recursividade em Grafos
Deep First Search
Prof. Neilor Tonin
Grafos – Definiçöes básicas
Grafo nao direcionado. G = (V, E)
V = Vértices (nodos) .
E = edges (arestas) entre par de nodos.
Captura a relação entre objetos.
Parâmetros de tamanho do grafo: n = |V|, m = |E|.
V = { 1, 2, 3, 4, 5, 6, 7, 8 }
E = { 1-2, 1-3, 2-3, 2-4, 2-5, 3-5, 3-7, 3-8, 4-5, 5-6 }
n = 8
m = 11
Digrafos
 Um digrafo (directed graph) consiste de umconjunto de 
vértices (bolas) e um conjunto de arestas
Alguns exemplos de digrafos:
Grafos
Grafo 
A
Grafo B
transporte
Grafo
Intersecção de ruas
Nodos Edges (arestas)
rodovias
communicaçao computadores Cabos de fibra ótica
World Wide Web web pages hyperlinks
social pessoas relações
Cadeia alimentar espécies predador-presa
software systems funções Chamadas de funções
agenda tarefas Restrições de precedencia
circuitos Portas lógicas linhas
 Algumas aplicaçoes de grafos:
World Wide Web
Web graph.
Nodo: web page.
Aresta: hyperlink de uma página para outra.
cnn.com
cnnsi.comnovell.comnetscape.com timewarner.com
hbo.com
sorpranos.com
Rede de Terrorismo
Grafo de rede social
Nodo: pessoas.
Edge(aresta): relacionamento entre 2 pessoas.
Referência: Valdis Krebs, http://www.firstmonday.org/issues/issue7_4/krebs
Ecological Food Web
Grafo de cadeia alimentar
Nodo = espécies. 
Aresta = da presa ao predador.
Referencia: http://www.twingroves.district96.k12.il.us/Wetlands/Salamander/SalGraphics/salfoodweb.giff
Grafos
 Outras definições importantes:
• Digrafo completo: todo par ordenado de vértices 
distinto equivale a uma aresta
• Digrafo denso: tem “muitos”, muitos arcos
• Digrafo esparso: tem “poucos” arcos
 Grau de um nodo: a tem grau 3, d tem grau 4 
Grafo 
A
Grafo 
B
a
b
c
d
e
Grafos
 Representações:
• As duas principais representações são através de:
• Matriz de adjacência
• Lista de Adjacência (que pode ser de formas 
diferentes)
• Lista de elementos com origem, destino e 
peso
• Vetor de lista de adjacência ou lista ligada
• etc.
Grafo 
A
Grafo 
B
Matriz de adjacência de digrafo
Grafo 
A
Grafo 
B
Checking if (u, v) is an edge takes (1) time. 
Identifying all edges takes (n2) time.
Matriz de adjacência de digrafo
Grafo 
A
Grafo 
B
Matriz de adjacência de digrafo
Grafo 
A
Grafo 
B
 A Estrutura digraph representa um digrafo:
• V contém o número de vértices
• A contém o número de arcos do digrafo
• adj é um ponteiro para a matriz de adjacência
struct digraph {
 int V;
 int A;
 int adj[100][100];
};
// Um objeto tipo Digraph contém o endereço de um
digraph.
typedef struct digraph *Digraph;
Matriz de adjacência de digrafo
Grafo 
A
Grafo 
B
 A Estrutura digraph é mencionada aqui pois é 
apresentada em muitos livros e transparências 
sobre grafos.
 Uma forma mais simples de utilizaçao seria sem o 
uso de ponteiros, simplesmente: 
using namespace std;
int V;
int A;
int adj[100][100];
...
Matriz de adjacência de digrafo
Grafo 
A
Grafo 
B
Matriz de adjacência de digrafo
Grafo 
A
Grafo 
B
*Representação utilizada 
por Sedgewick e outros 
autores (simplificaremos)
Lista de adjacência
Grafo 
A
Grafo 
B
 Lista de Adjacência com origem, destino e peso:
typedef struct {
 int origem;
 int destino;
 int peso;
} TipoAresta;
.
.
.
int main() {
 TipoAresta arestas[100];
 ...
Segunda forma de Lista de adjacência
Grafo 
A
Grafo 
B
Lista de Adjacência (Node indexed array of lists)
Duas representações de cada aresta (ida e volta).
Espaço proporcional a m + n.
Checando se (u, v) é uma aresta toma tempo O(deg(u)). 
Identificar todas as arestas (edges) toma tempo (m + n).
degree = number of neighbors of u
1 2 3
2
3
4 2 5
5
6
7 3 8
8
1 3 4 5
1 2 5 87
2 3 4 6
5
3 7
Caminhos e Conectividade
Def. Um caminho em um grafo nao orientado G = (V, E) 
é uma sequencia P de nodos v1, v2, …, vk-1, vk com a 
propriedade que cada par consecutivovi, vi+1 é unido por uma 
aresta em E.
Def. Um caminho é simples se todos nodos sao distintos.
Def. Um grafo näo orientado é conectado se para cada 
par de nodos u e v existe um caminho entre u e v.
Caminhos e Conectividade
• Procurando um caminho:
- Problema: dados um digrafo G e dois vértices s e t
decidir se existe um caminho de s a t
Exemplo: para s = 0 e t = 1 a resposta é SIM
Caminhos e Conectividade
• Procurando um caminho:
- Problema: dados um digrafo G e dois vértices s e t
decidir se existe um caminho de s a t
Exemplo: para s = 5 e t = 4 a resposta é NAO
DigraphPath
• Recebe um digrafo G e vértices s e t e devolve 1
se existe um caminho de s a t ou devolve 0 em 
caso contrário
• Supõe que o digrafo tem no máximo maxV
vértices.
• Utiliza Vertex para denominar vértices 
(Sedgewick)
int DIGRAPHpath (Digraph G, Vertex s, Vertex t)
DigraphPath
0
3
1
4
5
2
DIGRAPHpath(G,0,1)
DigraphPath
0
3
1
4
5
2
pathR(G,0)
DigraphPath
0
3
1
4
5
2
pathR(G,0)
DigraphPath
0
3
1
4
5
2
pathR(G,2)
DigraphPath
0
3
1
4
5
2
pathR(G,2)
DigraphPath
0
3
1
4
5
2
pathR(G,1)
DigraphPath
0
3
1
4
5
2
pathR(G,2)
DigraphPath
0
3
1
4
5
2
pathR(G,2)
DigraphPath
0
3
1
4
5
2
pathR(G,4)
DigraphPath
0
3
1
4
5
2
pathR(G,4)
DigraphPath
0
3
1
4
5
2
pathR(G,4)
DigraphPath
0
3
1
4
5
2
pathR(G,5)
DigraphPath
0
3
1
4
5
2
pathR(G,5)
DigraphPath
0
3
1
4
5
2
pathR(G,5)
DigraphPath
0
3
1
4
5
2
pathR(G,4)
DigraphPath
0
3
1
4
5
2
pathR(G,2)
DigraphPath
0
3
1
4
5
2
pathR(G,0)
DigraphPath
0
3
1
4
5
2
pathR(G,0)
DigraphPath
0
3
1
4
5
2
pathR(G,3)
DigraphPath
0
3
1
4
5
2
pathR(G,3)
DigraphPath
0
3
1
4
5
2
pathR(G,3)
DigraphPath
0
3
1
4
5
2
pathR(G,3)
DigraphPath
0
3
1
4
5
2
pathR(G,0)
DigraphPath
0
3
1
4
5
2
pathR(G,0)
DigraphPath
0
3
1
4
5
2
pathR(G,0)
DigraphPath
0
3
1
4
5
2
DIGRAPHpath(G,0,1)
DIGRAPHpath
Grafo 
A
Grafo 
B
…
#define Vertex int
using namespace std;
int cnt, lbl[maxV];
…
int DIGRAPHpath (Digraph G, Vertex s, Vertex t) {
 int v;
 for (v = 0; v < G->V; v++) {
 lbl[v] = -1;
 }
 pathR (G,s);
 if (lbl[t] == -1) {
 return 0;
 }
 return 1;
}
pathR
Grafo 
A
Grafo 
B
 Visita todos os vértices que podem ser atingidos 
à partir de v
void pathR (Digraph G, Vertex v) {
 int w;
 lbl[v] = cnt++; ///adaptado
 for (w = 0; w < G->V; w++) {
 if (G->adj[v][w] == 1) {
 if (lbl[w] == -1) {
 pathR(G, w);
 }
 }
 }
}
- No programa principal:
- Zera matriz de adjacencia
- Inclui arestas
- Chama DIGRAPHpath (0,1) ou Di…(G,0,1)
- Imprime vetor LBL
DigraphPath
0
3
1
4
5
2
DIGRAPHpath(G,0,1)
DigraphPath
DIGRAPHpath(G,2,3)
0
3
1
4
5
2
DigraphPath
pathR(G,2)
0
3
1
4
5
2
DigraphPath
pathR(G,2)
0
3
1
4
5
2
DigraphPath
pathR(G,1)
0
3
1
4
5
2
DigraphPath
pathR(G,2)
0
3
1
4
5
2
DigraphPath
pathR(G,2)
0
3
1
4
5
2
DigraphPath
pathR(G,4)
0
3
1
4
5
2
DigraphPath
pathR(G,4)
0
3
1
4
5
2
DigraphPath
pathR(G,4)
0
3
1
4
5
2
DigraphPath
pathR(G,5)
0
3
1
4
5
2
DigraphPath
pathR(G,5)
0
3
1
4
5
2
DigraphPath
pathR(G,5)
0
3
1
4
5
2
DigraphPath
pathR(G,4)
0
3
1
4
5
2
DigraphPath
pathR(G,2)
0
3
1
4
5
2
DigraphPath
0
3
1
4
5
2
DIGRAPHpath(G,2,3)
DIGRAPHpath
Grafo 
A
Grafo 
B
…
#define Vertex int
using namespace std;
int cnt, lbl[maxV];
…
int DIGRAPHpath (Digraph G, Vertex s, Vertex t) {
 int v;
 for (v = 0; v < G->V; v++) {
 lbl[v] = -1;
 }
 pathR (G,s);
 if (lbl[t] == -1) {
 return 0;
 }
 return 1;
}
pathR
Grafo 
A
Grafo 
B
 Visita todos os vértices que podem ser atingidos 
à partir de v
void pathR (Digraph G, Vertex v) {
 intw;
 lbl[v] = cnt++; ///adaptado
 for (w = 0; w < G->V; w++) {
 if (G->adj[v][w] == 1) {
 if (lbl[w] == -1) {
 pathR(G, w);
 }
 }
 }
}
DigraphPath
1
4
5
2
DIGRAPHpath(G,0,1)
0
3
DigraphPath
DIGRAPHpath(G,2,3)
0
3
1
4
5
2
dfsrPath.cpp
Grafo 
B
 Fonte dfsrPath.cpp:
– Busca um nodo y a partir de x e indica se é possível 
chegar em Y ou não.
– Mostra o vetor lbl no final
#include <iostream> 
#include <cstdio> 
 
#define maxV 10000 /// máximo de vértices 
#define vertice int 
 
using namespace std; 
 
int cnt, lbl[maxV]; 
int V; 
int A; 
 
int adj[100][100]; 
string espacos=""; 
 
void pathR (vertice v) { 
 vertice w; 
 lbl[v] = cnt++; 
 // espacos = espacos + " "; 
 for (w = 0; w < V; w++) { 
 if (adj[v][w] == 1) { 
 cout << endl << v << "-" << w ; 
 if (lbl[w] == -1) { // se nao percorreu ainda 
 cout << " pathR(G," << w <<")" ; 
 pathR(w); 
 } 
 } 
 } 
} 
 
int DIGRAPHpath (vertice s, vertice t) { 
 vertice v; 
 for (v = 0; v < V; v++) { 
 lbl[v] = -1; 
 } 
 pathR (s); 
 if (lbl[t] == -1) { 
 return 0; 
 } 
 return 1; 
} 
 
int main(void) { 
 freopen("dfsrPath.in","r",stdin); 
 int orig,dest; 
 cin >> V; ///Vertices 
 
 /// Zera a Matriz de Adjacência 
 for (int i=0; i<V; i++) { 
 for (int j=0; j<V; j++) { 
 adj[i][j]=0; 
 } 
 } 
 
 cin >> A; ///Arestas 
 for (int i=0; i<A; i++) { 
 cin >> orig >> dest; 
 adj[orig][dest]=1; 
 /// se for grafo (ao inves de digrafo (seta p ambas direcoes) 
 // D->adj[dest][orig]=1; 
 } 
 
 cout << "0 1" << endl; 
 if ( DIGRAPHpath (0,1) ) { 
 cout << endl << endl << "Possible" << endl; 
 } else { 
 cout << endl << endl << "Impossible" << endl; 
 } 
 
 cout << endl << "Vetor LBL: "; 
 for (int i=0; i<V; i++) { 
 cout << lbl[i] << " "; 
 } 
 
 cout << endl; 
 return(0); 
} 
Variações do programa
Grafo 
B
 Fonte dfsrpath_incrementado:
– Similar ao primeiro, que passa por todos os nodos. A diferença é 
que ele funciona para grafos desconexos, porque ao invés de chamar 
a rotina pathR apenas uma vez, a chama para cada elemento do 
vetor lbl que tem o valor -1. Também adiciona três espaços a cada 
novo nível em que entra.
DigraphPath
0
3
1
4
5
2
pathR(0)
7
6
8 11
0 4
0 2
2 1
2 4
4 1
3 5
3 6
5 6
3 7
5 7
7 3
0 1 2 3 4 5 6 7
0 1 1
1
2 1 1
3 1 1 1
4 1
5 1 1
6
7 1
lbl[8] = 0 -1 -1 -1 -1 -1 -1 -1
0 1 2 3 4 5 6 7
DigraphPath
0
3
1
4
5
2
7
6
8 11
0 4
0 2
2 1
2 4
4 1
3 5
3 6
5 6
3 7
5 7
7 3
0 1 2 3 4 5 6 7
0 1 1
1
2 1 1
3 1 1 1
4 1
5 1 1
6
7 1
lbl[8] = 0 2 1 -1 -1 -1 -1 -1
0 1 2 3 4 5 6 7
pathR(0)
DigraphPath
0
3
1
4
5
2
7
6
8 11
0 4
0 2
2 1
2 4
4 1
3 5
3 6
5 6
3 7
5 7
7 3
0 1 2 3 4 5 6 7
0 1 1
1
2 1 1
3 1 1 1
4 1
5 1 1
6
7 1
lbl[8] = 0 2 1 -1 -1 -1 -1 -1
0 1 2 3 4 5 6 7
pathR(0)
DigraphPath
0
3
1
4
5
2
7
6
8 11
0 4
0 2
2 1
2 4
4 1
3 5
3 6
5 6
3 7
5 7
7 3
0 1 2 3 4 5 6 7
0 1 1
1
2 1 1
3 1 1 1
4 1
5 1 1
6
7 1
lbl[8] = 0 2 1 -1 3 -1 -1 -1
0 1 2 3 4 5 6 7
pathR(0)
DigraphPath
0
3
1
4
5
2
7
6
8 11
0 4
0 2
2 1
2 4
4 1
3 5
3 6
5 6
3 7
5 7
7 3
0 1 2 3 4 5 6 7
0 1 1
1
2 1 1
3 1 1 1
4 1
5 1 1
6
7 1
lbl[8] = 0 2 1 -1 3 -1 -1 -1
0 1 2 3 4 5 6 7
pathR(0)
DigraphPath
0
3
1
4
5
2
7
6
8 11
0 4
0 2
2 1
2 4
4 1
3 5
3 6
5 6
3 7
5 7
7 3
0 1 2 3 4 5 6 7
0 1 1
1
2 1 1
3 1 1 1
4 1
5 1 1
6
7 1
lbl[8] = 0 2 1 -1 3 -1 -1 -1
0 1 2 3 4 5 6 7
pathR(0)
DigraphPath
0
3
1
4
5
2
7
6
8 11
0 4
0 2
2 1
2 4
4 1
3 5
3 6
5 6
3 7
5 7
7 3
0 1 2 3 4 5 6 7
0 1 1
1
2 1 1
3 1 1 1
4 1
5 1 1
6
7 1
lbl[8] = 0 2 1 -1 3 -1 -1 -1
0 1 2 3 4 5 6 7
pathR(0)
DigraphPath
0
3
1
4
5
2
7
6
8 11
0 4
0 2
2 1
2 4
4 1
3 5
3 6
5 6
3 7
5 7
7 3
0 1 2 3 4 5 6 7
0 1 1
1
2 1 1
3 1 1 1
4 1
5 1 1
6
7 1
lbl[8] = 0 2 1 -1 3 -1 -1 -1
0 1 2 3 4 5 6 7
pathR(0)
DigraphPath
0
3
1
4
5
2
7
6
8 11
0 4
0 2
2 1
2 4
4 1
3 5
3 6
5 6
3 7
5 7
7 3
0 1 2 3 4 5 6 7
0 1 1
1
2 1 1
3 1 1 1
4 1
5 1 1
6
7 1
lbl[8] = 0 2 1 -1 3 -1 -1 -1
0 1 2 3 4 5 6 7
pathR(0)
DigraphPath
0
3
1
4
5
2
7
6
8 11
0 4
0 2
2 1
2 4
4 1
3 5
3 6
5 6
3 7
5 7
7 3
0 1 2 3 4 5 6 7
0 1 1
1
2 1 1
3 1 1 1
4 1
5 1 1
6
7 1
lbl[8] = 0 2 1 -1 3 -1 -1 -1
0 1 2 3 4 5 6 7
pathR(0)
DigraphPath
0
3
1
4
5
2
pathR(3)
7
6
8 11
0 4
0 2
2 1
2 4
4 1
3 5
3 6
5 6
3 7
5 7
7 3
0 1 2 3 4 5 6 7
0 1 1
1
2 1 1
3 1 1 1
4 1
5 1 1
6
7 1
lbl[8] = 0 2 1 4 3 -1 -1 -1
0 1 2 3 4 5 6 7
DigraphPath
0
3
1
4
5
2
7
6
8 11
0 4
0 2
2 1
2 4
4 1
3 5
3 6
5 6
3 7
5 7
7 3
0 1 2 3 4 5 6 7
0 1 1
1
2 1 1
3 1 1 1
4 1
5 1 1
6
7 1
lbl[8] = 0 2 1 4 3 5 -1 -1
0 1 2 3 4 5 6 7
pathR(3)
DigraphPath
0
3
1
4
5
2
7
6
8 11
0 4
0 2
2 1
2 4
4 1
3 5
3 6
5 6
3 7
5 7
7 3
0 1 2 3 4 5 6 7
0 1 1
1
2 1 1
3 1 1 1
4 1
5 1 1
6
7 1
lbl[8] = 0 2 1 4 3 5 6 -1
0 1 2 3 4 5 6 7
pathR(3)
DigraphPath
0
3
1
4
5
2
7
6
8 11
0 4
0 2
2 1
2 4
4 1
3 5
3 6
5 6
3 7
5 7
7 3
0 1 2 3 4 5 6 7
0 1 1
1
2 1 1
3 1 1 1
4 1
5 1 1
6
7 1
lbl[8] = 0 2 1 4 3 5 6 -1
0 1 2 3 4 5 6 7
pathR(3)
DigraphPath
0
3
1
4
5
2
7
6
8 11
0 4
0 2
2 1
2 4
4 1
3 5
3 6
5 6
3 7
5 7
7 3
0 1 2 3 4 5 6 7
0 1 1
1
2 1 1
3 1 1 1
4 1
5 1 1
6
7 1
lbl[8] = 0 2 1 4 3 5 6 7
0 1 2 3 4 5 6 7
pathR(3)
DigraphPath
0
3
1
4
5
2
7
6
8 11
0 4
0 2
2 1
2 4
4 1
3 5
3 6
5 6
3 7
5 7
7 3
0 1 2 3 4 5 6 7
0 1 1
1
2 1 1
3 1 1 1
4 1
5 1 1
6
7 1
lbl[8] = 0 2 1 4 3 5 6 7
0 1 2 3 4 5 6 7
pathR(3)
DigraphPath
0
3
1
4
5
2
7
6
8 11
0 4
0 2
2 1
2 4
4 1
3 5
3 6
5 6
3 7
5 7
7 3
0 1 2 3 4 5 6 7
0 1 1
1
2 1 1
3 1 1 1
4 1
5 1 1
6
7 1
lbl[8] = 0 2 1 4 3 5 6 7
0 1 2 3 4 5 6 7
pathR(3)
DigraphPath
0
3
1
4
5
2
7
6
8 11
0 4
0 2
2 1
2 4
4 1
3 5
3 6
5 6
3 7
5 7
7 3
0 1 2 3 4 5 6 7
0 1 1
1
2 1 1
3 1 1 1
4 1
5 1 1
6
7 1
lbl[8] = 0 2 1 4 3 5 6 7
0 1 2 3 4 5 6 7
pathR(3)
DigraphPath
0
3
1
4
5
2
7
6
8 11
0 4
0 2
2 1
2 4
4 1
3 5
3 6
5 6
3 7
5 7
7 3
0 1 2 3 4 5 6 7
0 1 1
1
2 1 1
3 1 1 1
4 1
5 1 1
6
7 1
lbl[8] = 0 2 1 4 3 5 6 7
0 1 2 3 4 5 6 7
pathR(3)
DigraphPath
0
3
1
4
5
2
7
6
8 11
0 4
0 2
2 1
2 4
4 1
3 5
3 6
5 6
3 7
5 7
7 3
0 1 2 3 4 5 6 7
0 1 1
1
2 1 1
3 1 1 1
4 1
5 1 1
6
7 1
lbl[8] = 0 2 1 4 3 5 6 7
0 1 2 3 4 5 6 7
pathR(3)
Rotina
Grafo 
B
int cnt, lbl[maxV];
int V,A, adj[25][25];
string espacos="";
int entrou = 0;
void pathR (Vertex v,string espacos) {
Vertex w;
lbl[v] = cnt++;
espacos = espacos + " ";
for (w = 0; w < V; w++) {
if (adj[v][w] == 1) {
entrou = 1;
cout << espacos << v << "-" << w ;
if (lbl[w] == -1) { // se nao percorreu ainda
cout << " pathR(G," << w << ")" << endl;
pathR(w,espacos);
} else {
cout << endl;
}
}
}
}
int DIGRAPHpath (void) {
Vertex v;
for (v = 0; v < V; v++) {
lbl[v] = -1;
}
cnt = 0;
for (v = 0; v < V; v++) {
if (lbl[v] == -1) {
entrou=0;
/// segmento diferente
pathR (v,espacos); 
if (entrou) cout << endl;
}
}
}
Rotina
Grafo 
B
int main(void) {
freopen("dfsrPath.in","r",stdin);
int orig,dest;
cin >> V; ///Vertices
/// Zera a Matriz de Adjacência
for (int i=0; i<V; i++) {
for (int j=0; j<V; j++) {
adj[i][j]=0;
}
}
cin >> A; ///Arestas
for (int i=0; i<A; i++) {
cin >> orig >> dest;
adj[orig][dest]=1;
/// se for ida e volta (grafo ao inves de digrafo) 
/// (seta para ambas direcoes)
// D->adj[dest][orig]=1;
}
cout << "Caso 1:" << endl;
DIGRAPHpath ();
return(0);
}
Grafos
Referências:
http://paca.ime.usp.br/
Paulo Feofiloff�,
Livros:
Algoritmos para Grafos em C via Sedgewick
Robert Sedgewick,
Algorithms in C (part 5: Graph Algorithms)
Cormen-Leiserson-Rivest-Stein,Introductions to Algorithms
Links:
www.ime.usp.br/�pf/algoritmos_para_grafos/
www.ime.usp.br/~coelho/mac0328-2009/aulas
http://paca.ime.usp.br/
http://www.ime.usp.br/
http://www.ime.usp.br/