Grafos
Programación Estructurada
Lic. Burghardt, Mariela V.
2021
• Los grafos, constituyen estructuras de datos en las que se
pueden expresar relaciones de conexión entre diversos
elementos denominados vértices.
Grafos • Ejemplos: búsqueda del camino más corto entre dos
vértices, análisis de páginas web y análisis de las redes
sociales.
Un grafo, es una estructura
matemática que permite modelar
problemas de la vida cotidiana,
mediante una representación
gráfica formada por nodos o
vértices que muestra a los
actores y aristas que sirven para
representar los lazos o relaciones
entre los actores. Así mismo, un
Mapeando Twitter desde NodeXL y Gephi grafo puede representar un único
tipo de relación entre los actores,
o más de un tipo de relación,
además cada vínculo o relación
puede ser orientado.
Grafos
Análisis de #NiUnaMenos en las redes Grafo de seguidores en Twitter
Grafos
• Un grafo es una estructura de datos que
almacena datos de dos tipos:
• Vértices, con un valor almacenado,
• Aristas o arcos: cada uno conecta
un vértice con otro, y puede tener un
valor almacenado.
• Se clasifican en:
• Dirigidos: cuando todas las aristas
son dirigidas. Es importante el orden
del par de nodos que definen cada
arista.
• No dirigidos: cuando todas las
aristas son NO dirigidas. El orden del
par de nodos carece de importancia.
Grafos
• Dirigidos • No dirigidos
Grafos: Matriz de Adyacencia
• El conjunto de arcos se representa mediante una MATRIZ CUADRADA de
grado igual al número máximo de vértices que puede tener el grafo. La
matriz se representa mediante elementos booleanos ( un valor verdadero,
significa que hay camino.
01001000
00000010
0 1 2 3
00000000
A(G) =
00100010
00000000
4 5 6 7
11100000
00000000
00000010
1
Grafos
Implementación
en lenguaje C
2
3
4
5
typedef int tVertice;
typedef struct {
tVertice origen;
Grafos No Ponderados
tVertice destino;
} tArco; /* El arco es un par de vértices [ origen, destino ] */
typedef bool conjuntoVertices [N]; /* vector de vértices */
typedef bool conjuntoArcos [N][N]; /* matriz de arcos */
typedef struct { /*El grafo es una estructura compuesta por un
conjunto de vértices y un conjunto de arcos o aristas */
conjuntoVertices vertices;
conjuntoArcos arcos;
} tGrafoNoPonderado;
tGrafoNoPonderado grafo;
typedef int tPeso;
typedef int tVertice;
typedef struct {
tVertice origen;
tVertice destino;
Grafos Ponderados
tPeso peso;
} tArco; /* El arco es una terna compuesta por los vértices origen y destino, y el peso
entre ellos */
typedef bool conjuntoVertices [N]; /* vector de vértices */
typedef tPeso conjuntoArcos [N][N]; /* matriz de arcos */
typedef struct { /*El grafo es una estructura compuesta por un
conjunto de vértices y un conjunto de arcos o aristas */
conjuntoVertices vertices;
conjuntoArcos arcos;
} tGrafoPonderado;
tGrafoPonderado grafo;
Bibliografía
• Estructuras de datos y algoritmos; Alfred
V Aho, John E. Hopcroft, Jefrey D.
Ullman; 1988; Editorial Addison-Wesley
Iberoamercana; ISBN: 968-6048-19-7.
• [Link]
/12/la-belleza-de-las-redes-
herramientas-de-visualizacion-de-
grafos/ ; La belleza de las redes:
herramientas de visualización de grafos;
iNFoRMáTiCa++; Universitat Oberta de
Catalunya
• [Link] – Graph
drawer
• [Link] - Graph
Online. Encontrar camino más corto.
