#define MAXV 1000 struct edgenode { int y; int weight; struct edgenode *next; }; typedef struct { edgenode *edges[MAXV + 1]; int degree[MAXV + 1]; int nvertices; int nedges; bool directed; } graph; void initialize_graph(graph *g, bool directed) { int i;
g->nvertices = 0; g->nedges = 0; g->directed = directed;
for (i = 1; i < MAXV; i++) { g->degree[i] = 0; g->edges[i] = NULL; }
} void insert_edge(graph *g, int x, int y, bool directed) { edgenode *p; p = (edgenode *)malloc(sizeof(edgenode));
p->weight = NULL; p->y = y; p->next = g->edges[x];
g->edges[x] = p; g->degree[x]++; if (directed == false) insert_edge(g, y, x, true); else g->nedges++;
} // To read the graph from command line void read_graph(graph *g, bool directed) { int i; int m; int x, y, weight;
initialize_graph(g, directed); scanf("%d %d", &(g->nvertices), &m);
for (i = 1; i <= m; i++) { scanf("%d %d", &x, &y); insert_edge(g, x, y, directed); }
} // Create a sample graph void load_graphA(graph *g, bool directed) { initialize_graph(g, directed); g->nvertices = 7;
insert_edge(g, 1, 2, directed); insert_edge(g, 1, 3, directed); insert_edge(g, 1, 7, directed); insert_edge(g, 2, 3, directed); insert_edge(g, 3, 4, directed); insert_edge(g, 3, 5, directed); insert_edge(g, 4, 5, directed); insert_edge(g, 5, 6, directed); insert_edge(g, 5, 7, directed); insert_edge(g, 1, 6, directed);
} void print_graph(graph *g) { int i; edgenode *p;
for (i = 1; i <= g->nvertices; i++) { printf("%d: ", i); p = g->edges[i]; while (p != NULL) { printf(" %d", p->y); p = p->next; } printf("\n"); }
} int main(int argc, const char * argv[]) { graph *myGraph = (graph *)malloc(sizeof(graph)); read_graph(myGraph, false); // Or load_graphA(myGraph, false);
print_graph(myGraph); return 0;
} |
Algorithms >