El gráfico se compone de un conjunto de vértices (indicado como V ) y un conjunto de aristas (indicado como E ).
El gráfico se denota por G(E, V).
Componentes de un gráfico
- Vértices: Los vértices son las unidades fundamentales del grafo. A veces, los vértices también se conocen como vértices o Nodes. Cada Node/vértice se puede etiquetar o no etiquetar.
- Bordes: Los bordes son los que se dibujan o se utilizan para conectar dos Nodes del gráfico. Se puede ordenar un par de Nodes en un gráfico dirigido. Los bordes pueden conectar dos Nodes cualesquiera de cualquier forma posible. No hay reglas. A veces, los bordes también se conocen como arcos. Cada borde se puede etiquetar/desetiquetar.
Tipos de gráfico
Gráfico nulo
- Un gráfico se conoce como gráfico nulo si no hay bordes en el gráfico.
Gráfico trivial
- Gráfico que tiene un solo vértice, es el gráfico más pequeño posible.
Gráfico no dirigido
- Un gráfico en el que los bordes no tienen ninguna dirección. Es decir, los Nodes son pares desordenados en la definición de cada borde.
Gráfico dirigido
- Un gráfico en el que el borde tiene dirección. Es decir, los Nodes son pares ordenados en la definición de cada borde.
Gráfico conectado
- El grafo en el que desde un Node podemos visitar cualquier otro Node del grafo se le conoce como grafo conexo.
Gráfico desconectado
- El grafo en el que al menos un Node no es accesible desde un Node se conoce como grafo desconectado.
Gráfico regular
- El gráfico en el que el grado de cada vértice es igual a los otros vértices del gráfico. Sea K el grado de cada vértice, entonces el gráfico se llama K-regular .
Gráfico completo
- El gráfico en el que de cada Node hay un borde a cada otro Node.
Gráfico de ciclo
- El gráfico en el que el gráfico es un ciclo en sí mismo, el grado de cada vértice es 2.
Gráfico cíclico
- Un gráfico que contiene al menos un ciclo se conoce como gráfico cíclico.
Gráfico Acíclico Dirigido
- Un gráfico dirigido que no contiene ningún ciclo.
Gráfica bipartita
- Un gráfico en el que el vértice se puede dividir en dos conjuntos de modo que el vértice de cada conjunto no contenga ninguna arista entre ellos.
Gráfico ponderado
1. Un gráfico en el que los bordes ya están especificados con el peso adecuado se conoce como gráfico ponderado.
2. El gráfico ponderado se puede clasificar además como gráfico ponderado dirigido y gráfico ponderado no dirigido.
Árbol v/s Gráfico
Los árboles son los tipos restringidos de gráficos, solo que con algunas reglas más. Todo árbol siempre será un gráfico, pero no todos los gráficos serán árboles. Linked List , Trees y Heaps son casos especiales de gráficos.
Representación de Gráficos
Hay dos formas de almacenar un gráfico:
- Array de adyacencia
- Lista de adyacencia
Array de adyacencia
En este método, el gráfico se almacena en forma de array 2D donde las filas y las columnas indican vértices. Cada entrada en la array representa el peso del borde entre esos vértices.
Lista de adyacencia
Este gráfico se representa como una colección de listas enlazadas. Hay una array de punteros que apuntan a los bordes conectados a ese vértice.
Comparación entre ellos
Cuando el gráfico contiene una gran cantidad de aristas, es bueno almacenarlo como una array porque solo algunas entradas en la array estarán vacías. Se utiliza un algoritmo como la array de adyacencia de Prim y Dijkstra para tener menos complejidad.
Acción Array de adyacencia Lista de adyacencia Agregar borde O(1) O(1) Quitar y bordear O(1) EN) Inicializando O(N*N) EN) Pasos para resolver el problema
- Reconocer un problema como un problema gráfico.
- Encuentre un algoritmo para resolver el problema.
- Diseñar estructuras de datos y algoritmos para implementar la solución gráfica.
- ¡ Codifícalo !
Operaciones básicas en gráficos
A continuación se muestran las operaciones básicas en el gráfico:
- Inserción de Nodes/bordes en el gráfico: inserte un Node en el gráfico.
- Eliminación de Nodes/bordes en el gráfico: elimine un Node del gráfico.
- Búsqueda en gráficos: busque una entidad en el gráfico.
- Recorrido de gráficos: recorrer todos los Nodes del gráfico.
Uso de gráficos
- Los mapas se pueden representar mediante gráficos y luego los ordenadores pueden utilizarlos para proporcionar diversos servicios, como el camino más corto entre dos ciudades.
- Cuando varias tareas dependen unas de otras, esta situación se puede representar usando un gráfico acíclico dirigido y podemos encontrar el orden en el que se puede realizar la tarea usando la ordenación topológica.
- El diagrama de transición de estado representa lo que pueden ser los movimientos legales de los estados actuales. En el juego de tic tac toe esto se puede usar.
- Matar entrevistas !
Aplicaciones de la vida real de Graph
Más recursos para gráficos:
