¿Qué es la estructura de datos del gráfico?
A Grafico Es una estructura de datos no lineal que consta de vértices y aristas. A los vértices a veces también se les llama nodos y los bordes son líneas o arcos que conectan dos nodos cualesquiera en el gráfico. Más formalmente, un gráfico se compone de un conjunto de vértices ( EN ) y un conjunto de bordes ( Y ). La gráfica se denota por GRAMO(V, mi) .
fcfs
Representaciones de gráficos
Estas son las dos formas más comunes de representar un gráfico:
- Matriz de adyacencia
- Lista de adyacencia
Matriz de adyacencia
Una matriz de adyacencia es una forma de representar un gráfico como una matriz booleana (0 y 1).
Supongamos que hay norte vértices en el gráfico Entonces, crea una matriz 2D adjMat[n][n] teniendo dimensión n x n.
- Si hay una arista desde el vértice i a j , marca adjMat[i][j] como 1 .
- Si no hay arista desde el vértice i a j , marca adjMat[i][j] como 0 .
Representación de gráfico no dirigido a matriz de adyacencia:
La siguiente figura muestra un gráfico no dirigido. Inicialmente, se inicializa toda la Matriz para 0 . Si hay un borde desde el origen al destino, insertamos 1 a ambos casos ( adjMat[destino] y adjMat [ destino]) porque podemos ir en cualquier dirección.
Gráfico no dirigido a matriz de adyacencia
Representación de gráfico dirigido a matriz de adyacencia:
La siguiente figura muestra un gráfico dirigido. Inicialmente, se inicializa toda la Matriz para 0 . Si hay un borde desde el origen al destino, insertamos 1 para ese particular adjMat[destino] .
Gráfico dirigido a matriz de adyacencia
Lista de adyacencia
Se utiliza una matriz de Listas para almacenar aristas entre dos vértices. El tamaño de la matriz es igual al número de vértices (es decir, n) . Cada índice de esta matriz representa un vértice específico en el gráfico. La entrada en el índice i de la matriz contiene una lista enlazada que contiene los vértices adyacentes al vértice. i .
encadenamiento hacia adelante
Supongamos que hay norte vértices en el gráfico Entonces, crea un conjunto de lista de tamaño norte como listaadj[n].
- adjList[0] tendrá todos los nodos que están conectados (vecinos) al vértice 0 .
- adjList[1] tendrá todos los nodos que están conectados (vecinos) al vértice 1 etcétera.
Representación de gráfico no dirigido a la lista de adyacencia:
El siguiente gráfico no dirigido tiene 3 vértices. Entonces, se creará una matriz de lista de tamaño 3, donde cada índice representa los vértices. Ahora, el vértice 0 tiene dos vecinos (es decir, 1 y 2). Entonces, inserte los vértices 1 y 2 en los índices 0 de la matriz. De manera similar, para el vértice 1, tiene dos vecinos (es decir, 2 y 0). Entonces, inserte los vértices 2 y 0 en los índices 1 de la matriz. De manera similar, para el vértice 2, inserte sus vecinos en la matriz de la lista.
Lista de gráfico no dirigido a adyacencia
Representación del gráfico dirigido a la lista de adyacencia:
El siguiente gráfico dirigido tiene 3 vértices. Entonces, se creará una matriz de lista de tamaño 3, donde cada índice representa los vértices. Ahora el vértice 0 no tiene vecinos. Para el vértice 1, tiene dos vecinos (es decir, 0 y 2). Entonces, inserte los vértices 0 y 2 en los índices 1 de la matriz. De manera similar, para el vértice 2, inserte sus vecinos en la matriz de la lista.
Gráfico dirigido a la lista de adyacencia