Buon pomeriggio devo realizzare il seguente programma in c con grafi orientati : Dato un grafo G orientato rappresentato con liste di adiacenza, scrivere una funzione che verifichi se ci siano cicli nel grafo e, in caso ne esista uno, elimini l’arco che lo crea. Posto il codice che ho iniziato a realizzare
Il MAIN
Graph.h
Graph.c
List.h
List.c
Non riesco a capire come applicare la hfs per determinare se nel grafo ci sono cicli
Il MAIN
C:
#include <stdio.h>
#include "Graph.h"
#include "List.h"
int main() {
int n,e,i,v,u;
Graph G =NULL;
printf("\nEnter the number of vertices - ");
scanf("%d",&n);
G = initGraph(n);
printf("\nEnter the number of edges - ");
scanf("%d",&e);
printf("\nVertices are - ");
for(i=1;i<n;i++)
printf("%d ",i);
printf("\nEnter the edges separated by space - ");
for(i=1;i<e;i++)
{
scanf("%d%d",&v,&u);
addEdge(G,v,u);
}
printGraph(G);
DFS(G, 2);
printf("\n\n");
return 0;
}
C:
#ifndef Graph_h
#define Graph_h
#include <stdio.h>
#include "List.h"
struct TGraph {
List *adj;
int* visited;
struct TList** adjLists;
int nodes_count;
};
typedef struct TGraph* Graph;
// Crea un grafo in modo random con nodes nodi
Graph randomGraph(int nodes);
// Dealloca l'intero grafo
void freeGraph(Graph G);
// Inizializza un nuovo grafo vuoto specificando in ingresso quanti nodi saranno nel grafo
Graph initGraph(int nodes_count);
// Stampa il grafo
void printGraph(Graph G);
// Aggiunge un arco, specificando sorgente, target e peso
void addEdge(Graph G, int source, int target);
// Rimuovi un arco specificando sorgente e target,restituisce la lista degli archi modifcata
List removeEdge(Graph G, int source, int target);
// Aggiungi un nodo
void addNode(Graph G);
// Rimuovi un nodo dal grafo, sistemando gli indici e riallocando la memoria
void removeNode(Graph G, int node_to_remove);
List checkListRemoval(List L, int node_to_remove);
// Crea un nuovo grafo e lo popola in base alla scelta effettuata dal menu
Graph graphCreationMenu(int n);
// Menu per la modifica e gestione dei grafi
void graphEditorMenu(Graph);
#endif /* Graph_h */
C:
#include "Graph.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
#include "Graph.h"
Graph initGraph(int nodes_count) {
Graph G = (Graph)malloc(sizeof(struct TGraph));
G->adj = (List *)calloc(nodes_count, sizeof(List));
G->nodes_count = nodes_count;
return G;
}
void freeGraph(Graph G) {
if (G != NULL) {
if (G->nodes_count > 0) {
int i = 0;
for (i = 0; i < G->nodes_count; i++) {
freeList(G->adj[i]);
}
}
free(G);
}
}
void printGraphAux(Graph G) {
if (G != NULL) {
int x = 0;
for (x = 0; x < G->nodes_count; x++) {
printf("%d -> ", x);
printList(G->adj[x]);
printf("\n");
}
}
}
void printGraph(Graph G) {
printGraphAux(G);
printf("\n\n");
}
void addEdge(Graph G, int source, int target) {
assert(G != NULL);
assert(source < G->nodes_count);
assert(target < G->nodes_count);
if (source != target) {
G->adj[source] = appendNodeList(G->adj[source], target);
}
}
List removeEdge(Graph G, int source, int target) {
assert(G != NULL);
assert(source < G->nodes_count);
assert(target < G->nodes_count);
if (source != target) {
G->adj[source] = removeNodeList(G->adj[source], target);
}
return G->adj[source];
}
void addNode(Graph G) {
if (G != NULL) {
List * old=G->adj;
int i=0;
//G->adj = (List *)realloc(G->adj, (G->nodes_count+1) * sizeof(List));
G->adj = (List *)malloc((G->nodes_count+1) * sizeof(List));
for(i=0;i<G->nodes_count;i++)
G->adj[i]=old[i];
G->nodes_count += 1;
G->adj[G->nodes_count-1] = NULL;
}
}
void removeNode(Graph G, int node_to_remove) {
if (G != NULL) {
int i = 0;
int x = 0;
List *tmp = G->adj;
G->adj = (List *)calloc(G->nodes_count-1, sizeof(List));
for (i = 0; i < G->nodes_count; i++) {
if (i != node_to_remove) {
G->adj[x] = checkListRemoval(tmp[i], node_to_remove);
x++;
} else {
freeList(tmp[i]);
}
}
free(tmp);
G->nodes_count -= 1;
}
}
List checkListRemoval(List L, int node_to_remove) {
if (L != NULL) {
L->next = checkListRemoval(L->next, node_to_remove);
if (L->target == node_to_remove) {
List tmp = L->next;
free(L);
return tmp;
} else if (L->target > node_to_remove) {
L->target -= 1;
}
}
return L;
}
// DFS algo
void DFS(struct TGraph* graph, int vertex) {
struct TList* adjList = graph->adjLists[vertex];
struct TList* temp = adjList;
graph->visited[vertex] = 1;
printf("Visited %d \n", vertex);
while (temp != NULL) {
int connectedVertex = temp->vertex;
if (graph->visited[connectedVertex] == 0) {
DFS(graph, connectedVertex);
}
temp = temp->next;
}
}
C:
#ifndef List_h
#define List_h
#include <stdio.h>
struct TList {
int target;
int vertex;
struct TList* next;
};
typedef struct TList* List;
// Inizializza un nuovo nodo
List initNodeList(int info);
// Aggiunge un nodo alla fine della lista
// controllandone l'esistenza
// La funzione ritorna sempre la testa della lista
List appendNodeList(List L, int target);
// Aggiunge un nodo in testa alla lista
// senza controllare l'esistenza
// La funzione ritorna sempre la testa della lista
List addNodeList(List L, int target);
// Rimuove solo un occorrenza di un nodo con il target specificato
// dalla lista
// La funzione ritorna sempre la testa della lista
List removeNodeList(List L, int target);
// Dealloca la lista interamente
void freeList(List L);
// Stampa la lista
void printList(List L);
#endif /* List_h */
C:
#include "List.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "List.h"
List initNodeList(int info) {
List L = (List)malloc(sizeof(struct TList));
L->target = info;
L->next = NULL;
return L;
}
List appendNodeList(List L, int target) {
if (L != NULL) {
if (L->target != target) {
L->next = appendNodeList(L->next, target);
}
} else {
L = initNodeList(target);
}
return L;
}
List addNodeHead(List L, int target, int peso) {
if (L != NULL) {
List G = (List )malloc(sizeof(struct TList));
G->target = target;
G->next = L;
return G;
}
return initNodeList(target);
}
List removeNodeList(List L, int target) {
if (L != NULL) {
if (L->target == target) {
List tmp = L->next;
free(L);
return tmp;
}
L->next = removeNodeList(L->next, target);
}
return L;
}
void freeList(List L) {
if (L != NULL) {
freeList(L->next);
free(L);
}
}
void printList(List L) {
if (L != NULL) {
printf(" %d ", L->target);
printList(L->next);
}
}
