initialize

1 files changed, 164 insertions, 0 deletions

diff --git a/c/dataStructure/408/graph/dgraph.c b/c/dataStructure/408/graph/dgraph.c
new file mode 100755
index 0000000..499fc0d
--- /dev/null
+++ b/c/dataStructure/408/graph/dgraph.c
@@ -0,0 +1,164 @@
+#include "graph.h"
+
+/* Thdse functions can use for both direct or undirect graph,
+ * only be affected by argument 'directed' we give
+ */
+
+void retreat(char * str)
+{
+    fprintf(stderr,"%s\n",str);
+    exit(EXIT_FAILURE);
+}
+
+void initializeGraph(graph * g, bool directed)
+{
+    int i;  /* counter */
+
+    g->nvertices = 0;
+    g->nedges = 0;
+    g->directed = directed;
+
+    for (i = 1; i <= MAXV; i++)
+        g->degree[i] = 0;
+    
+    for (i = 1; i <= MAXV; i++)
+        g->edges[i] = NULL;
+}
+
+/* x, y is a pair of vertices */
+void insertEdge(graph * g, int x, int y, bool directed)
+{
+    edgeNode * p;       /* temporary pointer */
+
+    p = (edgeNode *) malloc (sizeof(edgeNode));
+    if (!p)
+        retreat("Error allocate memory p");
+    
+    p->weight = 0;
+    p->y = y;
+
+    p->next = g->edges[x];      /* insert at head */
+    g->edges[x] = p;
+
+    g->degree[x]++;
+
+    if (!directed)
+        insertEdge(g,y,x,true);         /* add another one for undirected */
+    else
+        g->nedges++;
+}
+
+void readGraph(graph * g, bool directed)
+{
+    int i;      /* counter */
+    int m;      /* number of edges */
+    int x, y;   /* vertices in edge (x, y) / <x, y> */
+
+    printf("Enter number of vertices and edges: ");
+    scanf ("%d%d", &(g->nvertices), &m);    /* read number of vertices and edges */
+
+    printf("Enter two vertices consist one edge: ");
+    for (i = 1; i <= m; i++)
+    {
+        scanf("%d %d", &x, &y);             /* readindex and vertex */
+        insertEdge(g,x,y,directed);         /* this is the one to make a graph */
+    }
+}
+
+void printGraph(graph * g)
+{
+    int i;          /* counter */
+    edgeNode * p;   /* temporary pointer */
+
+    for (i = 1; i <= g->nvertices; i++)
+    {
+        printf("%d: ",i);
+        p = g->edges[i];
+        while (p)
+        {
+            printf(" %d", p->y);
+            p = p->next;
+        }
+        putchar('\n');
+    }
+}
+
+void purgeGraph(graph * g)
+{
+    int i;          /* counter */
+    edgeNode * p, * q;   /* temporary pointer */
+
+    for (i = 1; i < g->nvertices; i++)
+    {
+        p = g->edges[i];
+        while (p)
+        {
+            q = p;
+            p = p->next;
+            free(q);
+        }
+    }
+}
+
+void initializeSearch(graph * g)
+{
+    int i;
+
+//    time = 0;
+
+    for (i = 0; i <= g->nvertices; i++)
+    {
+        g->processed[i] = false;
+        g->discovered[i] = false;
+        g->parent[i] = -1;
+    }
+}
+
+void processVertexEarly(int v)
+{
+    printf("processed vertex %d\n",v);
+}
+void processVertexLate(int v)
+{
+}
+void processEdge(int v, int y)
+{
+    printf("Process edge (%d,%d)\n",v,y);
+}
+
+void bfs(graph * g, int start)
+{
+    queue q;    /* queue of vertices to visit */
+    int v;      /* current vertex */
+    int y;      /* successor vertex */
+    edgeNode * p; /* temporary pointer */
+
+    initializeSearch(g);
+
+    initQueue(&q);
+    enQueue(&q,start);
+    g->discovered[start] = true;
+
+    while (!emptyQueue(&q))
+    {
+        v = deQueue(&q);
+        processVertexEarly(v);
+        g->processed[v] = true;
+        p = g->edges[v];
+
+        while (p)
+        {
+            y = p->y;
+            if (!g->processed[y] || g->directed)
+                processEdge(v,y);
+            if (!g->discovered[y])
+            {
+                enQueue(&q,y);
+                g->discovered[y] = true;
+                g->parent[y] = v;
+            }
+            p = p->next;
+        }
+        processVertexLate(v);
+    }
+}