Estructuras de Datos Clase 15 – Grafos (Primera Parte) Dr. Sergio A. Gómez http://cs.uns.edu.ar/~sag Departamento de Ciencias e Ingeniería de la Computación Universidad Nacional del Sur Bahía Blanca, Argentina

Definición • Un grafo G=(V,E) es un conjunto V de vértices (o nodos) y un conjunto E ⊆ V×V de aristas (o arcos). • Intuitivamente E permite representar una relación entre elementos de V. b

c

V = { a, b, c, d, e, f, g } E = { (a,b), (b,c), (c,d), (d,g), (e,g), (e,f), (f,g), (a,e), (b,g) }

a g d e

f Estructuras de datos - Dr. Sergio A. Gómez

2

Definiciones • Un arco (u,v) puede ser: – Dirigido: (u,v) es un par ordenado, o, – No dirigido: (u,v) en realidad es {u,v} y (u,v) es lo mismo que (v,u). • Grafo dirigido o digrafo: Sus arcos son dirigidos. • Ejemplo: Grafo de herencia de interfaces en Java. • Ejemplo: Grafo donde los nodos son esquinas de una ciudad y los arcos son cuadras de una mano. • Grafo no dirigido o simplemente grafo: Sus arcos son no dirigidos. • Ejemplo: Grafo de colaboración entre coautores científicos. • Ejemplo: Grafo donde los nodos son esquinas de un pueblo chico y los arcos son calles doble mano. Estructuras de datos - Dr. Sergio A. Gómez

3

Definiciones • Arcos que inciden en un vértice v = { (x,y) in E : y=v } • Arcos que emergen de un vértice v = {(x,y) in E : x=v } • Grado de incidencia/entrada de un vértice v: indegree(v) = cantidad de arcos que inciden en v • Grado de emergencia/salida de un vértice v: outdegree(v) = cantidad de arcos que emergen de v Estructuras de datos - Dr. Sergio A. Gómez

4

Definiciones • Grafo pesado: Grafo donde las aristas contienen una etiqueta (o peso cuando las etiquetas son numéricas). • Ejemplo: Digrafo donde los vértices son aeropuertos y los arcos representan vuelos (distancias entre aeropuertos si los pesos son números). • Multi(di)grafo: (Di)grafo donde el conjunto de arcos es una colección. Es decir puede haber más de un arco entre cada par de vértices (se llaman “arcos paralelos”) • Grafo simple: Grafo que no es multigrafo. • Ejemplo: Digrafo donde los vértices representan aeropuertos, los arcos son vuelos y puede haber más de un vuelo entre dos aeropuertos. Estructuras de datos - Dr. Sergio A. Gómez

5

Definiciones • Camino: Un camino es una secuencia alternante de vértices y arcos tales que empieza en un vértice y termina en otro y cada arco es incidente en sus vértices predecesor y sucesor. • Ciclo (simple): Un camino que comienza y termina en el mismo vértice (sin repetir arcos). • Ciclo (camino) dirigido: Un ciclo (camino) donde las aristas tienen dirección y son recorridas en su dirección. Estructuras de datos - Dr. Sergio A. Gómez

6

Definiciones • Subgrafo: Un subgrafo H de un grafo G es un grafo donde los vértices de H son un subconjunto de los vértices de G y los arcos de H son un subconjunto de los vértices de G. • Grafo abarcador (spanning subgraph): Es un subgrafo de G que contiene todos los vértices de G. • Grafo conexo: Un grafo G es conexo si para dos vértices cualquiera de G hay un camino entre ellos. • Componentes conexas: Si un grafo no es conexo, sus subgrafos maximales conexos se llaman componentes conexas.

Estructuras de datos - Dr. Sergio A. Gómez

7

Definiciones • Bosque: Un bosque es un grafo sin ciclos. • Árbol: Un árbol es un bosque conexo (i.e. un grafo conexo sin ciclos). • Nota: Los árboles de los temas anteriores se llaman árboles con raíz (rooted tree). • Nota: Los árboles de grafos se llaman árboles libres (free trees). • Árbol abarcador: Subgrafo abarcador que es un árbol libre. Estructuras de datos - Dr. Sergio A. Gómez

8

ADT Grafo El tipo de dato abstracto Grafo exporta tres sorts: • Graph: Un grafo pesado de vértices con rótulos de tipo V y arcos con rótulos de tipo E • Vertex: La posición de un vértice con rótulo de tipo V • Edge: La posición de un arco con rótulo de tipo E

Estructuras de datos - Dr. Sergio A. Gómez

9

ADT Grafo • vertices(): Retorna una colección iterable con todos los vértices del grafo. • edges(): Retorna una colección iterable con todos los arcos del grafo. • incidentEdges(v): Retorna una colección iterable con todos los arcos incidentes sobre un vértice v • emergentEdges(v): Retorna una colección iterable con todos los arcos emergentes de un vértice v (no está en GT, también le podemos decir successorEdges(v)) Estructuras de datos - Dr. Sergio A. Gómez

10

ADT Grafo • opposite(v,e): Retorna el otro vértice w del arco e=(v,w); ocurre un error si e no es incidente (o emergente de v). • endVertices(e): Retorna un arreglo (de 2 componentes) conteniendo los vértices del arco e. • areAdjacent(v,w): Testea si los vértices v y w son adyacentes. Estructuras de datos - Dr. Sergio A. Gómez

11

ADT Grafo • replace(v,x) : Reemplaza el rótulo del vértice v con x • replace(e,x): Reemplaza el rótulo del arco e con x • insertVertex(x): Inserta y retorna un nuevo vértice con rótulo x • insertEdge(v, w, x): Inserta un arco con rótulo x entre los vértices v y w • insertDirectedEdge(v, w, x): Inserta un arco dirigido con rótulo x entre los vértices v y w Estructuras de datos - Dr. Sergio A. Gómez

12

ADT Grafo • removeVertex(v): Elimina el vértice v y todos sus arcos adyacentes y retorna el rótulo de v • removeEdge(e): Elimina el arco e y retorna el rótulo almacenado en e.

Estructuras de datos - Dr. Sergio A. Gómez

13

ADT Grafo

Buenos Aires

Graph g = new Digrafo(); Vertex bb = g.insertVertex("Bahia Blanca"); Vertex pa = g.insertVertex("Punta Alta"); Vertex ba = g.insertVertex("Buenos Aires"); Vertex mdp = g.insertVertex("Mar del Plata");

400km

Edge vueloBB2PA = g.insertDirectedEdge(bb, pa, 15); g.insertDirectedEdge(bb, mdp, 470); g.insertDirectedEdge(mdp, ba, 400); 470km

Mar del Plata

g.removeEdge(vueloBB2PA); g.removeVertex(pa); Punta Alta

Estructuras de datos - Dr. Sergio A. Gómez

Bahía Blanca

15km 14

Estructuras de datos para grafos • Lista de arcos • Lista de adyacencias • Matriz de adyacencias

Estructuras de datos - Dr. Sergio A. Gómez

15

Lista de arcos

Estructuras de datos - Dr. Sergio A. Gómez

16

Implementación de lista de arcos Position element():E

E -> V Vertex

Edge

Graph

Vertice

Arco

GrafoListaArcos

Rotulo: V posicionEnListaVertices: Position

Rotulo: E posicionEnListaArco: Position cola, punta : Vertice

Estructuras de datos - Dr. Sergio A. Gómez

nodos: PositionList arcos: PositionList

17

Performance de la lista de arcos Dado un grafo G=(V,A) Sea n = #V y m = #A Operación

Tiempo

Vertices

O(n)

Edges

O(m)

endVertices, opposite

O(1)

incidentEdges, areAdjacent

O(m)

Replace

O(1)

insertVertex, insertEdge, removeEdge

O(1)

removeVertex

O(m)

Estructuras de datos - Dr. Sergio A. Gómez

18

Lista de adyacencias

Estructuras de datos - Dr. Sergio A. Gómez

19

Performance de la lista de adyacencias

Operación

Tiempo

Vertices

O(n)

Edges

O(m)

endVertices, opposite

O(1)

incidentEdges(v), areAdjacent

O(deg(v))

Replace

O(1)

insertVertex, insertEdge, removeEdge

O(1)

removeVertex

Estructuras de datos - Dr. Sergio A. Gómez

O(deg(v))

20

Matriz de adyacencias

Estructuras de datos - Dr. Sergio A. Gómez

21

Performance de matriz de adyacencias

Operación

Tiempo

vertices

O(n)

edges

O(m)

endVertices, opposite, areAdjacent

O(1)

incidentEdges(v)

O(n+deg(v))

replace

O(1)

insertVertex, insertEdge, removeEdge

O(1)

insertVertex, removeVertex

O(n2)

Estructuras de datos - Dr. Sergio A. Gómez

22

Implementación de digrafo con lista de adyacencias public interface Vertex extends Position {

} // Vertex.java

public interface Edge extends Position {

} // Edge.java

public interface Graph { // Graph.java public Iterable vertices(); public Iterable edges(); public Iterable incidentEdges(Vertex v); public Iterable succesorEdges(Vertex v); public Vertex opposite(Vertex v, Edge e); public Vertex [] endVertices(Edge e); public boolean areAdjacent(Vertex v, Vertex w); public V replace( Vertex v, V x); public E replace( Edge e, E x); public Vertex insertVertex(V x); public Edge insertEdge(Vertex v, Vertex w, E x); public V removeVertex(Vertex v); public E removeEdge(Edge e); } Estructuras de datos - Dr. Sergio A. Gómez

23

// Vertice.java

public class Vertice implements Vertex { private V rotulo; private PositionList adyacentes; private Position posicionEnNodos; public V element() { return rotulo; } public Vertice( V rotulo ) { this.rotulo = rotulo; adyacentes = new Lista(); } public void setRotulo(V nuevoRotulo) { … } public PositionList getAdyacentes() { … } public void setPosicionEnNodos(Position p ) { … } public Position getPosicionEnNodos() { …} } Estructuras de datos - Dr. Sergio A. Gómez

24

// Arco.java public class Arco implements Edge { private E rotulo; private Vertice sucesor, predecesor; private Position posicionEnAdyacentes; public Arco( E rotulo, Vertice predecesor, Vertice sucesor ) { /* solo setea atributos */ } public E element() { return rotulo; } public Vertice getPredecesor() { … } public Vertice getSucesor() { … } public Position getPosicionEnAdyacentes() { … } public void setPosicionEnAdyacentes( Position p) { … } } Estructuras de datos - Dr. Sergio A. Gómez

25

// Digrafo.java public class Digrafo implements Graph { protected PositionList nodos; public Digrafo() { nodos = new Lista(); } public Iterable vertices() { PositionList lista = new Lista(); for( Vertex v : nodos ) lista.addLast(v); Uso: return lista; for( Vertex v : g.vertices() ) } System.out.println( v.element() ); Tvertices(n, m) = O(n) Tarea: PensarEstructuras cómo de agregar la lista de arcos. datos - Dr. Sergio A. Gómez

26

// Atributos del grafo: // protected PositionList nodos;

public Iterable edges() { PositionList lista = new Lista(); for( Vertex v : nodos ) for( Edge e : succesorEdges(v)) lista.addLast(e); return lista; } Tedges(n, m) = O(n+m) Tarea: Pensar cómo cambia esta Implementación si agrego la lista de arcos. Estructuras de datos - Dr. Sergio A. Gómez

27

// Atributos del grafo: // protected PositionList nodos;

public Iterable successorEdges( Vertex v) { PositionList lista = new Lista(); Vertice vert = (Vertice) v; for( Edge e : vert.getAdyacentes() ) lista.addLast(e); return lista; } TsuccessorEdges(n,m) = O(deg(v))

Estructuras de datos - Dr. Sergio A. Gómez

28

// Atributos del grafo: // protected PositionList nodos;

public Vertex insertVertex(V x) { Vertice v = new Vertice(x); nodos.addLast(v); v.setPosicionEnNodos(nodos.last()); return v; } TinsertVertex(n,m) = O(1)

Estructuras de datos - Dr. Sergio A. Gómez

29

// Atributos del grafo: // protected PositionList nodos; //Inserta un arco dirigido de v a w public Edge insertEdge(Vertex v, Vertex w, E x) { Vertice vv = ((Vertice) v); Vertice ww = ((Vertice) w); Arco arco = new Arco(x, vv, ww); vv.getAdyacentes().addLast(arco); arco.setPosicionEnAdyacentes(vv.getAdyacentes().last()); return arco; } TinsertEdge(n,m) = O(1)

Estructuras de datos - Dr. Sergio A. Gómez

30

// Atributos del grafo: // protected PositionList nodos; public E removeEdge(Edge e) { try { Arco ee = ((Arco) e); Position pee = ee.getPosicionEnAdyacentes(); Vertice pred = ee.getPredecesor(); return pred.getAdyacentes().remove(pee).element(); } catch(InvalidPositionException excep) { return null; } } TremoveEdge(n,m) = O(1)

Estructuras de datos - Dr. Sergio A. Gómez

31

// Atributos del grafo: // protected PositionList nodos; // Asume que no tiene arcos. public V removeVertex(Vertex v) { try { Position pos = ((Vertice) v).getPosicionEnNodos(); return nodos.remove( pos ).element(); } catch(InvalidPositionException e) { return null; } } TremoveVertex(n,m) = O(1) Tarea: Pensar cómo modificarla para Primero eliminar todos los arcos Que salen del nodo v (como propone GT) Estructuras de datos - Dr. Sergio A. Gómez

32

Bibliografía • Capítulo 13 de M. Goodrich & R. Tamassia, Data Structures and Algorithms in Java. Fourth Edition, John Wiley & Sons, 2006.

Estructuras de datos - Dr. Sergio A. Gómez

33