Red de conocimiento informático - Aprendizaje de código fuente - Encuentra todos los caminos entre dos vértices en un gráfico no dirigido. El gráfico se almacena en una matriz bidimensional. Es mejor utilizar el lenguaje c. Por favor, dígame también cómo resolver el problema. Gracias.

Encuentra todos los caminos entre dos vértices en un gráfico no dirigido. El gráfico se almacena en una matriz bidimensional. Es mejor utilizar el lenguaje c. Por favor, dígame también cómo resolver el problema. Gracias.

/*/

Algoritmo de búsqueda en profundidad.

*/

#include

#include

#include

//El número máximo de puntos en el gráfico

# define MAX_NODES_NUM 10

//El número de rutas con como máximo dos puntos en el gráfico

#define MAX_PATHS_BETWEEN_TWO_NODES_NUM (1<<(MAX_NODES_NUM-2))

//// Marcar la longitud de la ruta como infinita

#define INFINTITY (1< <30)

p>

// Marca la longitud de la ruta accesible

#define REACHABLE 1

#define TRUE 1

#define FALSE 0

ruta de estructura

{

int tamaño;

int nodos[MAX_NODES_NUM];

};

/*

Obtener todas las rutas desde el punto inicial hasta el punto final del mapa mapa

mapa: mapa

n: punto en el mapa

N: punto en el mapa.

n: el número de puntos en el mapa

inicio: el punto de partida

fin: el punto final

rutas: guardar todos los puntos encontrados desde el punto inicial hasta el punto final Rutas

rutas: Guarda los números de todas las rutas encontradas desde el punto inicial hasta el punto final

*/

void getPaths(int map[][MAX_NODES_NUM],int n ,int start,int end,int isNodeUsed[],struct Path paths[],int * pathsNum)

{

int i,j;

struct Path tempPaths[MAX_PATHS_BETWEEN_TWO_NODES_NUM];

int tempPathsNum

// Marcar el punto de partida actual como no disponible

isNodeUsed[start] = TRUE;

for(i=0;i

{

// El nodo no está en la ruta y se puede acceder a él

if(isNodeUsed [i] == FALSE && map[start][i]== REACHABLE)

{

// El punto de partida actual puede llegar directamente al punto final

if(i == end)

{

paths[(*pathNum )].tamaño = 2;

rutas[(*pathsNum)].nodos [0] = fin;

rutas[(*pathsNum)].nodos[0] = fin ;

rutas[(*pathsNum)].pathsNum)].nodos[1 ] = inicio;

(*pathsNum)++

}<; /p>

// Si el punto de partida actual puede llegar al punto final directamente, intente pasar otras rutas desde el nodo actual El nodo llega al punto final

else

{

// Calcula recursivamente todas las rutas desde el punto inicial actual hasta el punto final.

tempPathsNum = 0;

getPaths(map,n,i,end,isNodeUsed,tempPaths,&tempPathsNum);

// Procesa el punto de partida encontrado desde el actual Todos los caminos hasta el final del mapa.

for(j=0;j

{

// Agrega el punto de partida actual a todas las rutas desde el punto de partida actual hasta el punto final

tempPaths[j].nodes[tempPaths[j].size] = inicio;

tempPaths[j].size ++;

// Fusionar con la ruta final

paths[(*pathsNum)] = tempPaths[j];

(*pathsNum)++;

}

}

}

}

isNodeUsed[start] = FALSE;

}

int main (int argc, char *argv[])

{

int map[MAX_NODES_NUM][MAX_NODES_NUM]

int isNodeUsed[MAX_NODES_NUM];

struct Ruta rutas[MAX_PATHS_BETWEEN_TWO_NODES_NUM];

int rutasNum;

int i,j;

int inicio,fin;

int a ,b;

int n,m;

// Lee el número de puntos y caminos

while(scanf("%d%d ",&n, &m)! =EOF)

{

// Inicializa el mapa

for(i=0;i

{

isNodeUsed[i] = FALSE;

for(j=0;j

{

map[i][j] = INFINTITY;

}

}

// Inicializa el mapa.

}

//Leer ruta

for(i=0;i

{

scanf("%d%d",&a,&b);

// Marca la ruta entre a y b. Tenga en cuenta que este es un mapa no direccional, marcado dos veces

map[a][b] = REACHABLE

map[b][a] = REACHABLE

}

// Dos mapas El El camino entre ellos no está dirigido.

// Conexión de dos puntos

scanf("%d%d",&start,& end);

// Búsqueda de punto a punto

pathsNum = 0;

getPaths(map,n,start,end,isNodeUsed,paths,&pathsNum); // Imprime todas las rutas desde el punto inicial hasta punto final

for(i=0;i

{

for(j=paths[i].size -1;j >=1;j--)

{

printf("%d -> ", rutas[i].nodos[j]); }

printf("%d\n",rutas[i].nodos[j]);

}

}

devolver 0;

}

/*

Datos de prueba:

1) Primero ingrese el número de puntos n, el número de caminos m,

2) Luego ingrese el número de m pares de puntos. Cada par de puntos a, b significa que hay un camino entre el punto a y el punto b

El. número del punto Comience desde 0 y suba hasta n-1.

3) Finalmente ingresa los dos puntos a conectar

Ingresa:

6 14

0 1

0 2

1 0

1 3

2 0

2 4

2 5

3 1

3 5

4 2

4 5

5 2

5 3

5 4

0 5

Salida:

0 -> 1 -> 3 -> 5

0 -> 2 -> 4 -> 5

0 -> 2 -> 5

*/