Examen de ingreso de posgrado de 2015: ¿Algoritmos comúnmente utilizados para estructuras de datos informáticos (7)?

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, el requisito de amplitud requiere los puntos adyacentes de un punto. Por lo tanto, la matriz de adyacencia solo se usa en Floyd, Prim y Dijstra.

La lista de adyacencia puede encontrar fácilmente los puntos adyacentes de un vértice. La mayoría de los algoritmos relacionados con el recorrido del índice 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, todo lo que se pueda lograr 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)

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 Si hay un camino entre dos 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 gráfico dirigido significa que el gráfico dirigido está

fuertemente conectado

El proceso de recorrer el gráfico es esencialmente el proceso de encontrar sus vecinos para cada vértice, que es tiempo- El consumo depende principalmente de la estructura de almacenamiento utilizada. Cuando el gráfico se almacena con una matriz de adyacencia, se necesita tiempo o() para encontrar los puntos adyacentes de cada vértice, donde n es el número de vértices en el gráfico. Cuando se utiliza una lista de adyacencia para almacenar un gráfico, el tiempo necesario para encontrar puntos adyacentes es O(e), donde e es el número de aristas o arcos dirigidos en el gráfico. Por lo tanto, cuando utilice la lista de adyacencia como estructura de almacenamiento, primero realice una búsqueda profunda con una complejidad temporal de O (n + e) ​​para recorrer el gráfico.

La complejidad temporal del gráfico transversal de búsqueda en amplitud y del gráfico transversal de búsqueda en profundidad es la misma. La única diferencia entre los dos es el orden en que se visitan los nodos. Es decir, su complejidad temporal depende de la estructura de almacenamiento utilizada. Cuando se almacena en una matriz de adyacencia, la complejidad es O(), y cuando se almacena en una lista de adyacencia, la complejidad temporal es O(n+e).

Algoritmo de construcción de gráficos: (la lista de adyacencia a menudo se prueba, la matriz de adyacencia es simple, la lista entrecruzada y la lista múltiple son muy similares a la creación de una lista de adyacencia)

void create graph(adj list & amp; G) //Crea una estructura de almacenamiento de lista de adyacencia para un gráfico no dirigido con n vértices y m aristas.

{ int n, m;

scanf("%d%d ",&n&m); //Ingrese el número de vértices y aristas.

for (i =1, i & lt= n; I++)//Ingrese información de vértice y cree un vector de vértice.

scanf(& g[i]. vértice);

g[i]. firstarc = null

}

for(k = 1; k & lt= m; K++)//Ingrese información lateral

scanf(& amp; v1 .v2); //Ingrese dos vértices.

i= LocateVertex (g, v 1); j=GraphLocateVertex (g, v2); //Posicionamiento de vértices

p = (ArcNode *)malloc(sizeof(ArcNode)) ; // Solicitar un nodo de borde

p->; adj vex = j

p->; primerarcg[i]. first arc = p; // Vincula el nodo de borde al encabezado de la lista de bordes.

p =(ArcNode *)malloc(sizeof(ArcNode)); //Por ser un gráfico no dirigido, debería estar en otro.

p->; adj vex = I;

p->; siguiente=g[j]. primerarcg[j]. frstarc = p; // Inserta el nodo en la tabla de borde del vértice.

}

}//Fin del algoritmo CreatGraph

Dos algoritmos para encontrar el árbol de expansión mínimo (Prim y Kruskal)

Prim algoritmo Hay un bucle doble. La capa exterior es para encontrar n-1 bordes y la capa interior es para encontrar el valor mínimo en el espacio cerrado [v]. Los efectos del lowcost y del actual punto añadido al cierre[] se descubren en paralelo. Por lo tanto, su complejidad temporal es O (), que no tiene nada que ver con el número de aristas en el camino, por lo que es más adecuado para gráficos con aristas densas. (No importa cuántas aristas haya, el número de vértices es el mismo).

Kruskal le corresponde. Su complejidad temporal es O(eloge), que no tiene nada que ver con el número de nodos. el gráfico, pero con el número de aristas relacionadas. Por lo tanto, funciona bien para gráficos dispersos.

(El número de aristas es fijo y la complejidad es la misma independientemente del número de vértices)

En el algoritmo de Prim para encontrar el árbol de expansión mínimo, el peso de la arista no puede ser negativo.

estructura typedef {

Adjvex de tipo de vértice

VRType de bajo costo

} cerrado[MAX _ VERTEX _ NUM]; p >Supongamos que el costo(u,w) representa el peso en el borde (U,w), para cada vértice w en el conjunto V-U,

cerrado[LocateVex(G,w)]. Bajo costo = mínimo {costo (U, w) | u∈U}

void MiniSpanTree_PRIM(MGraph G, VertexType u, SqList & ampMSTree)

{

//G es una red conectada representada por una matriz de almacenamiento, construida a partir del vértice U según el algoritmo de prim.

k = LocateVex (G, u);

for(j = 0; j

if (j!=k) cerradoge[j] = { u, G.arcs[k][j].adj}; //{adjvex, lowcost}

lowcost=0; //Estado inicial, U={u }

for(I = 1; I

{ k = valor mínimo (dge cercano); //Encuentra el siguiente nodo de T (el k-ésimo vértice en el gráfico)

/ /En este momento cerrado[k]. Bajo costo=

// Min{ cerrado[vi]. Bajo costo & gt0, vi∈V-U}

printf(cerrado[k] .adkvex,g.vexs[k]); //Editor de generación de salida

closedge[k] low cost = 0; //kth Los vértices se fusionan en el conjunto U

. for(j = 0; j

if (G.arcs[k][j].adj & ltkloski[j].lowcost ) //Vuelve a seleccionar el borde más pequeño después de fusionar los nuevos vértices en u

cerrado[j] = { G.vexs[k], G.arcs[k][j];

} // para

} // MiniSpanTree

Problema de clasificación topológica

Estado TopologicalSort (álgebra G)

{

FindIn Degree(G, en grados); la permeabilidad de cada punto en el índice [vnum];

InitStack

for(I = 0; i

if(Intitle[i]= =0 )

Empuje (S, I);

count = 0;

Y (! Parte superior de la pila)

{ Pop( S, I); printf(i, G.vex[i]. data); ++ count;

for( p=G..provocar problemas firstarcp;p = p->nextarc)

{ k = p->adjvex

en grados[k]-;

if( Ingrados[k]= =0) push(S,k );

}//para

}//cuando

Si (cuenta

devuelve error;

other

devuelve OK

}

Análisis de algoritmo: la complejidad temporal de encontrar la penetración de cada vértice es O(e), y el punto con cero la penetración entra en la pila O(n). En el bucle, cada vértice se introduce en la pila una vez y se saca una vez. Mientras tanto***, la operación de reducir la penetración en 1 se realiza e veces, por lo que la complejidad del tiempo total es O(n+e).

El recorrido en profundidad también se puede utilizar para la clasificación topológica cuando no hay ciclos en el gráfico. Como no hay ciclos en el gráfico, el vértice que sale primero de la función DFS, es decir, el punto con grado cero, es el último vértice en la clasificación topológica. Por lo tanto, la secuencia de vértices registrada en el orden de la función DFS es la secuencia ordenada topológicamente inversa.

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/