/* programma per stabilire se un grafo è bipartito */
/* si assume che il grafo fornito in ingresso sia connesso */
#include <stdio.h>
#include <stdlib.h>
/********************/
/* definizione tipi */
/********************/
/* implementazione di insiemi disgiunti con liste */
typedef struct lnode {
int id;
struct lnode* next;
struct lnode* rap;
} lnode;
/*********************/
/* variabili globali */
/*********************/
/* matrice di adiacenza per la rappresentazione del grafo */
char **IncMatrix;
/* puntatori che implementano le due collezioni di insiemi disgiunti (liste) */
lnode *L1, *L2;
/* array che memorizza i puntatori alle strutture lnode */
lnode **LNodes;
/* numero di nodi del grafo */
int NumNodes;
/* numero di archi del grafo */
int NumEdges;
/* rappresentazione del grafo [1=liste, 2=foreste] */
char GraphRapType;
/*********************/
/* funzioni */
/*********************/
/* legge il grafo in input come matrice di adiacenza */
void ReadGraph() {
/* identifichiamo i nodi con interi da 0 a NumNodes-1 */
/* legge il numero di nodi del grafo */
printf("\nNumero di Nodi: ");
scanf("%d", &NumNodes);
printf("\nNumero di Archi: ");
scanf("%d", &NumEdges);
/* alloca memoria e inizializza la matrice di incidenza */
IncMatrix = (char**)malloc(NumNodes * sizeof(char*));
for (int i=0; i<NumEdges; i++)
IncMatrix[i] = (char*)malloc(NumEdges * sizeof(char));
/* inizializza matrice di incidenza */
for (i=0; i<NumNodes; i++)
for (int j=0; j<NumEdges; j++) IncMatrix[i][j] = 0;
/* alloca memoria e inizializza la collezione di nodi */
LNodes = (lnode**)malloc(NumNodes * sizeof(lnode*));
/* legge gli archi del grafo */
for (i=0; i<NumEdges; i++) {
int a, b;
printf("\n arco %d-esimo: ");
scanf("%d ", &a);
scanf("%d", &b);
IncMatrix[a][i] = 1;
IncMatrix[b][i] = 1;
} }
/* crea un insieme disgiunto con un solo elemento (liste) */
lnode* MakeSet(short n)
1
{ lnode* pn = (lnode*)malloc(sizeof(lnode));
pn->id = n;
pn->next = NULL;
pn->rap = pn;
LNodes[n] = pn;
return pn;
}
/* trova il rappresentante dell'insieme che contiene a (liste) */
lnode* FindSet(int n) {
return LNodes[n]->rap;
}
/* unisce a all'insieme che contiene b (liste) */
void Union(lnode* pa, int b) { lnode* pn1, *pn2;
pn1=FindSet(b);
/* trova l'ultimo elemento dell'insieme che contiene b */
pn2 = pn1;
while (pn2->next != NULL) pn2 = pn2->next;
/* aggiungi pa */
pn2->next = pa;
pa->rap = pn1;
}
/* prova a inserire gli adiacenti del nodo node nell'insieme set (liste) */
void TryInsert(int setid, short node) {
lnode* lp;
lnode *curset, *otherset;
if (setid == 1) {
curset = L1;
otherset = L2;
} else {
curset = L2;
otherset = L1;
}
/* controlla che il nodo non sia presente nell'altro insieme */
if (otherset != NULL) lp = otherset;
while (lp != NULL) {
if (lp->id == node) {
printf("\nGrafo non bipartito");
exit(0);
}
lp = lp->next;
}
/* controlla che il nodo non sia già presente in set */
if (curset != NULL) lp = curset;
while (lp != NULL) {
if (lp->id == node) return;
lp = lp->next;
}
/* inserisci il nuovo nodo */
MakeSet(node);
Union(LNodes[node], curset->id);
}
/* controlla se sono stati inseriti tutti i nodi del grafo nei due insiemi L1 e L2 */
2
void CheckEnd() {
lnode* curnode;
char found = 0;
for (int j=1; j<NumNodes; j++) {
/* controlla se è presente in L1 */
curnode = L1;
while (curnode != NULL) {
if (curnode->id == j) {
found = 1;
break;
} else
curnode = curnode->next;
}
if (!found) {
/* controlla se è presente in L2 */
curnode = L2;
while (curnode != NULL) {
if (curnode->id == j) {
found = 1;
break;
} else
curnode = curnode->next;
} }
if (!found) return;
}
printf("\nGrafo bipartito");
exit(1);
} /* main */
void main() {
/* legge il grafo e inizalizza le strutture */
ReadGraph();
/* visita il grafo in ampiezza per determinare se è bipartito */
/* parti dal primo nodo */
lnode* curnode = MakeSet(0);
L1 = curnode;
L2 = NULL;
int otherset = 2;
/* disponi gli adiacenti nell'altra lista */
while (1) {
/* scandisci tutta la lista corrente */
while (curnode != NULL) {
for (int j=1; j<NumNodes; j++) if (IncMatrix[curnode->id][j]) {
TryInsert(otherset, j);
CheckEnd();
}
curnode = curnode->next;
}
/* scandisci tutta l'altra lista */
otherset = 1;
curnode = L2;
while (curnode != NULL) {
for (int j=1; j<NumNodes; j++) if (IncMatrix[curnode->id][j]) {
TryInsert(otherset, j);
CheckEnd();
}
curnode = curnode->next;
3
} } }
4
