Para gráficos no dirigidos, el rango de e es:
Los gráficos analizados en la estructura de datos son gráficos simples y no habrá aristas bilaterales entre dos nodos. .
Para gráficos dirigidos, el rango de e es:
Varias estructuras de almacenamiento de gráficos
La matriz de adyacencia es conveniente para acceder a los bordes de dos cualesquiera. puntos, pero es inconveniente Calcular sus puntos adyacentes. En los recorridos de profundidad y amplitud, la amplitud requiere vecinos de un punto. Por lo tanto, la matriz de adyacencia solo se usa en Floyd, Prim y Dijstra.
Las listas de adyacencia pueden encontrar fácilmente las adyacencias de un vértice. La mayoría de los algoritmos relacionados con el recorrido de índices utilizan listas de adyacencia. Como profundidad, ancho, clasificación topológica y ruta crítica. Pero también tiene algunas deficiencias, es decir, no conviene entrar o esos puntos los puede operar él. Entonces alguien introdujo la lista de adyacencia inversa. Finalmente, las personas combinaron estos dos tipos de listas, es decir, listas entrecruzadas y listas múltiples adyacentes. Uno es almacenar gráficos dirigidos y el otro es almacenar gráficos no dirigidos.
Es muy conveniente encontrar puntos adyacentes y sus correspondientes operaciones inversas en listas entrecruzadas y multilistas adyacentes. Por lo tanto, en aplicaciones prácticas, cualquier cosa que pueda lograrse mediante listas de adyacencia debe implementarse mediante listas entrecruzadas y listas múltiples de adyacencia. Y son más eficientes en almacenamiento.
1. Las matrices de adyacencia (gráficos dirigidos y gráficos no dirigidos y redes) también se denominan representaciones de matriz.
estructura typedef
{ vextype vexs[maxn]; ∨espacio de almacenamiento de vértices∨
adj tipo A[maxn][maxn] ∑ matriz de adyacencia∧
int vexnum, arcnum//El número de vértices y aristas del gráfico
GraphKind class; //El tipo de gráfico
} mgraph
2. Lista de adyacencia (redes y gráficos dirigidos y no dirigidos)
Estructura Typedef borde del nodo
{ int adjint w; ∑ puntos y pesos adyacentes
Nodo de estructura * siguiente puntos al siguiente arco o borde
} linknode
Estructura Typedef ∨tipo de vértice∨
{ vtype datos ∑ rango de vértices
linknode * farc∑ apunta al primer arco o arista asociado al vértice
} Vnode
estructura typedef
{
vnode G[maxn]; ∨tabla de vértices∨
int vexnum, arcnum
clase GraphKind;
} ALGraph
adjvexnextarcinfo
Nodos de borde
Datos firstarc
Nodos de vértice
3. Listas entrecruzadas (gráficos dirigidos y redes dirigidas)
headvextaivexhlinktlinkinfo
Nodos de borde
datafirstinfirstout
Nodos de vértice
4. Adyacencia de múltiples tablas (gráfico no dirigido)
p>markivexjvexilinkjlinkinfo
Nodo de borde
Borde de datos
Nodo de vértice
Gráfico acíclico dirigido (DAG): es un método eficaz herramienta para describir expresiones utilizando subexpresiones comunes. Los árboles binarios también pueden representar expresiones, pero el uso de gráficos acíclicos dirigidos puede compartir la misma subfórmula, ahorrando así espacio de almacenamiento.
Grado de vértice:
Gráfico no dirigido: El grado de un vértice V es D(V), que representa el número de aristas asociadas a V.
Gráfico dirigido: El grado del vértice V d(V)= ID(V) OD(V)
Rama fuertemente conectada: En un gráfico dirigido, si hay dos Si hay un camino entre vértices, se llama gráfico fuertemente conexo. El subgrafo fuertemente conexo más grande de un gráfico se denomina componente fuertemente conexo.
La "máxima" aquí significa que si agrega vértices y aristas a una rama conectada, no puede formar un subgrafo conectado en el gráfico original, es decir, la rama conectada es un subgrafo conectado con el conjunto más grande . La conectividad de un grafo dirigido significa que está fuertemente conectado.
Si tiene preguntas sobre el examen de ingreso de posgrado, no sabe cómo resumir el contenido del centro de examen de ingreso de posgrado o no conoce las políticas locales para el registro del examen de ingreso de posgrado, haga clic en la parte inferior para consultar el sitio web oficial y obtener materiales de revisión gratuitos: /xl/