GRAFOS
ESTRUCTURAS DE DATOS
COMPONENTES CONEXAS

De un grafo no dirigido


Componentes conexas:
entre ellas son conexas
Se pude saber si es conexo
Si no lo es se pueden conocer sus

Componentes Conexas

Conjunto W, de vértices del grafo

En el cual hay camino desde cualquier V1 a cualquier V2

Donde V1 y V2 pertenecen a W
CONEXO
A
B
C
E
D
A
B
C
E
D
No
CONEXO
ALGORTIMO: DETERMINAR
CONEXIÓN

Si entre todos los vértices, hay camino



Un recorrido desde cualquier vértice
Visitara a TODOS los vértices del grafo
Si no

Tendremos una componente conexa


Conjunto de vértices recorrido
Para descubrir otras


Repetir recorrido desde un vértice no visitado
Hasta que todos los vértices hayan sido visitados
EJEMPLO
A
B
E
D
A
Recorrido desde E
B
Conjunto recorridos =
Conjunto de Vertices
Es CONEXO
E
C
A
Component
e Conexa
W1
D
Recorrido desde B
B
E
D
D
Recorrido desde E
C
B
C
C
E
A
Component
e Conexa
W2
IMPLEMENTACION
No olvidar: Luego de
recorrer, obtendremos
un conjunto de
vertices LRecorrido
bool ComponentesConexas(Grafo G, LSE *LComponentes){
Vertice *V;
LSE *LRecorrido;
Las componentes
while(TRUE){
forman una Lista de
V = BuscarVerticeNoVisitado(G);
Listas
if(!V) break;
LRecorrido = RecorrerAnchura(G,*V);
LSE_InsertarNodoFin(LComponentes,
LSE_CrearNodo(LRecorrido));
}
if(LComponentes->header == LComponentes->last) return TRUE;
return FALSE;
}
COMPONENTES
FUERTEMENTE CONEXAS

De un grafo DIRIGIDO


Se puede saber si es FUERTEMENTE CONEXO
Si no lo es se pueden conocer sus

Componentes Fuertemente Conexas
Conjunto W, de vertices del grafo
 En el cual hay camino desde cualquier V1 a cualquier V2
 Donde V1 y V2 pertenecen a W

No
CONEXO
C
B
H
4
Componentes
8
5
6
F
S
CONEXO
ALGORITMO

Dado un Vo, se desea conocer



Si D interseccion A = V entonces



Los vertices a los que se puede llegar (D)
Los vertices que llegan a Vo (A)
Hay camino entre cualquier par de vertices
Fuertemente conexo
Si no

Tendremos una componente conexa


Conjunto de vertices recorrido
Para descubrir otras
Repetir recorrido desde vertice que no sea elemento de una C.F.C.
 Hasta que todos los vertices esten en C.F.C

C
EJEMPLO
B
H
F
S
C
W=DA
B
H
S
1) Recorrer desde H
(Descendientes)
1) Recorrer desde B
(Descendientes)
S
W3 = {F}
W <> V,
Componente F.C.
F
D= B
W2 = {H}
W1 = {B, C, S}
C
D= H
F
C
B
1) Recorrer desde F
(Descendientes)
S
D= F
C
B
2) Invertir Direcciones
3) Recorrer desde B
(Ascendientes)
A= B
C
F
H
3) Recorrer desde H
(Ascendientes)
S
A= H
3) Recorrer desde F
(Ascendientes)
A= FH
S
PUNTOS DE ARTICULACION

En un grafo no dirigido conexo

Existen vertices que si se eliminan


“Desconectan” al Grafo

Lo dividen en componentes conexas
Estos vertices “clave”


Si un grafo no tiene P.A.


Son puntos de articulacion
Es biconexo
La conectividad de un grafo

Es el numero de nodos que se necesitan eliminar

Para dejar a un grafo “desconectado”
EJEMPLO
A
B
C
D
Puntos de
Articulacion
E
F
ARBOL DE EXPANSION

Para poder calcular los P.A. de un grafo


A

Hay que obtener el arbol de expansion
Este se obtiene

A partir del Recorrido en Profundidad
Ejemplo
D
C
F
B
E
C
D
A
E
F
Arco en Retroceso:
Cuando se quiere visitar
un nodo que ya ha sido
visitado y no es el
padre
B
COMO REPRESENTAR EL
ARBOL DE EXPANSION

Un arbol en expansion




Si no tomamos en cuenta los


Arcos en Retroceso
La representacion depende del Grafo



No es un arbol binario
Cada Vertice puede tener 0, 1 o n hijos
Si sabemos que CADA VERTICESOLO TIENE UN PADRE
Matriz de Ady -> Usar un arreglo o
Lista de Ady -> Una lista
La representacion mostrará

Quien es el padre de cada nodo
ARBOL DE EXPANSION
CON MATRIZ DE ADY.


Los vertices del grafo
A

Se encuentran en un arreglo

Cada indice del arreglo

Representa un vertice

Ej: A – 0, B – 1, etc
Al representar el arbol de expansion

El padre(indice) de cada nodo

Puede almacenarse en un arreglo

Que tambien represente a los vertices
typedef struct TVertices{
Generico V[MAX];
int Padres[MAX];
int nvertices;
}Vertices;
B
C
E
D
F
0
0
0
5
2
1
2
3
4
5
A B
C
D
E
F
0
4
ARBOL DE EXP. CON LISTA
DE ADYACENCIA
B
A



Se encuentran en una lista
Cada nodo


C
Los vertices del grafo
D
Representa un vertice
Al representar el arbol de expansion

De cada nodo de esta lista


Solo nos interesa conocer al padre
Se puede añadir un dato al nodo vertice

Un enlace con el padre
typedef struct Vertice{
Generico Informacion;
Vertice *padre;
Lista *LArcos;
}Vertice;
E
F
A
B
C
D
E
F
ALGORITMO: ENCONTRAR
P.A.
Num(v) se calcula a
medida que se
genera el Arbol de
Expansion
Para calcular
Bajo(v), se necesita
bajar hasta conocer
los Bajos(hijos de v)

A cada vertice numerarlo



A es P.A.
De acuerdo al recorrido
Se obtiene Num(v)
2 ,2
A c/vertice, calcular Bajo(v)

Minimo entre
Num(v)
 Num(arco_retroceso de v)
 Bajo(hijos de v)

La raiz si tiene >= 2 hijos
Vertices para los cuales

Algun Bajo(hijo de v) >= Num(v)
Min(1, --, 2)
C es P.A.
3 ,3
C
Min(3, --, 3)
4 ,3
Min(2, --, --)
P.A. son

A
D


1 ,1
Min(4, ---, 3)
F
5 ,3
E
Min(5, ---, 3)
6 ,3
B
Min(6, 3, ----)
CAMBIOS EN EL ARBOL

Tanto Num(v) como Bajo(v)
Deben ser parte ahora de la estructura
 Del arbol

typedef struct TVertices{
typedef struct Vertice{
Generico V[MAX];
Generico Informacion;
int Padres[MAX];
int Num, Bajo;
int Num[MAX];
Vertice *padre;
int Bajo[MAX];
int nvertices;
}Vertices;
Lista *LArcos;
}Vertice;
COMO IMPLEMENTAR??

Primero


Que representacion se usara?
Si es M.A.


Si es L.A.


Usar Arbol de Expansion como un tipo aparte
Usar Grafo para trabajar con Arbol de Exp.
Luego

Recorrer el grafo


Para llenar Num y enlazar a los padres
Calcular Bajo

Y con esta informacion decidir cual es punto de art.
IMPLEMENTACION
CALCULAR NUM y PADRES
//Al recorrer, llenar Num y enlazar con los padres
void RecorrerParaArbol(Grafo G, Vertice *V, int *vez){
int i;
Al vertice de origen, marcar como vistado y
LSE_nodo *p;
contarlo, hay que llevar rastreo del aumento
del contador
V->visitado = TRUE;
*vez++;
((Vertice *)(p->G))->Num = *vez;
for(p = V->LA->header; p!=NULL; p= p->sig){
if(!((Vertice *)(p->G))->Visitado){
RecorrerParaArbol(G, p->G, vez);
((Vertice *)p->G)->padre = V;
}
}
IMPLEMENTACION
CALCULAR BAJO
//Para calcular el Bajo de Vorigen, calcular Bajo de los hijos(en recorrido9
//Es decir, recorrer otra vez el grafo para poder “bajar” x el mismo
void CalcularBajo(Grafo G, Vertice *V ){
int i;
Antes de llamar a esta funcion, el grafo debe
de volver a quedar como si no se hubiese
LSE_nodo *p;
recorrido antes
Vertice *Ad;
V->visitado = TRUE;
V->Bajo = V->Num;
Calcular el bajo
for(p = V->LA->header; p!=NULL; p= p->sig){
del hijo, si es
Ad = Generico_ObtenerVertice(p->G);
menor que el
if(!Ad->Visitado){
actual,
CalcularBajo(G, Ad);
cambiarlo
if(Ad->Bajo < V->Bajo) V->Bajo = A->Bajo;
}else if(V->padre!=Ad)
Si ya fue visitado y
no es el padre:
if(Ad->Num < V->Bajo) V->Bajo = Ad->Num;
arco en retroceso
}
}
EJERCICIO

Escriba una funcion que dado un Grafo permita
conocer los puntos de Articulacion del mismo

Recuerde que los P.A. son vertices
Descargar

GRAFOS - Pastranamoreno Blog