Grafos

EDA

Grafos
Lengoaia eta sistema informatikoak UPV-EHU

Jesús Bermudez-en gardenkietan oinarrituta Eta haren Creative Commons baimenekin zabaldua

EDA

¿Qué es un grafo?
 G=(N, A)
– N esun conjunto de nodos (o vértices) – A es un conjunto de arcos (par de nodos) A C E B D
{A, C} {B, C} {A, B} {D, B} {A, E} {E, D}

A

C E

B

D
(A, C) (C, B) (A, B) (B, D) (E, A) (D, E)NO dirigido
Grafoak/Grafos

dirigido
2

EDA

Conceptos básicos
 Adyacencia: se produce una relación de adyacencia entre 2 vértices cuando existe un arco que los une  Recorrido: unasecuencia de arcos que unen 2 nodos.  Ciclo: recorrido que acaba en el mismo nodo en el que empieza, en el que no hay ciclos.

Grafoak/Grafos

3

EDA

Conceptos básicos
 Grafos vs árboles: elgrafo es más general que un árbol, ya que no tiene la siguiente restricción de los árboles:
– Cada nodo tiene un solo padre (excepto la raíz)

 Un grafo no tiene raíz, y cada nodo puede estarconectado como máximo con todos los demás nodos (n - 1)  Se dice que un grafo es completo cuando el número de arcos que conectan los nodos es máximo

Grafoak/Grafos

4

EDA

GraphADT (interface)void addVertex (T vertex) void removeVertex (T vertex) void addEdge (T vertex1, T vertex2) Adds a vertex to this graph Removes a single vertex with the given value from this graph Inserts an edgebetween two vertices of this graph

void removeEdge (T vertex1, T vertex2) Removes an edge between two vertices of this graph Iterator iteratorBFS(T startVertex) Iterator iteratorBFS(T startVertex)boolean isConnected() Returns a breadth first iterator starting with the given vertex Returns a depth first iterator starting with the given vertex Returns true if this graph is connected, false otherwiseGrafoak/Grafos

5

EDA

Representación de grafos
 Listas de adyacencia
A B C D E A B C D E

C B E

A C D

A B

B E

A D

B C

D

B

E

A

Grafoak/Grafos

6...