美文网首页
Concerning Graph Part I: Basic I

Concerning Graph Part I: Basic I

作者: 刘煌旭 | 来源:发表于2021-01-06 21:26 被阅读0次

And this is the Graph implementation:

#include "linked_list_bag.c"
#include "out.c"
#ifndef GRAPH
#define GRAPH
typedef struct GraphStruct {
    int v;
    int e;
    LinkedListBag *adj;
}* Graph;

Graph GraphCreateV(int v) {
    Graph g = (Graph)malloc(sizeof(*g));
    g->v = v;
    g->e = 0;
    g->adj = (LinkedListBag*)malloc(v * sizeof(LinkedListBag));
    for (int i = 0; i < v; i++) { *(g->adj + i) = LinkedListBagCreate(); }
    return g;
}

void GraphAddEdge(Graph g, int v, int w) {
    LinkedListBagAdd(*(g->adj + v), w);
    LinkedListBagAdd(*(g->adj + w), v);
    g->e++; 
}

int GraphNumberOfEdges(Graph g) { return g->e; }

int GraphNumberOfVertices(Graph g) { return g->v; }

Graph GraphCreate(int v, int e, int a[]) {
    Graph g = GraphCreateV(v);
    for (int i = 0; i < e; i++) { GraphAddEdge(g, *(a + 2 * i), *(a + 2 * i + 1)); }
    return g;
}

/**
 * examle:
 * 3 //number of vetices
 * 3 //number of edges
 * 1 0
 * 1 2
 * 2 1
*/
Graph GraphCreateFromInput() {
    int v, e, *a;
    scanf("%i%i", &v, &e);
    a = (int*)malloc(2 * e * sizeof(*a));
    for (int i = 0; i < e; i++) { scanf("%i%i", a + 2 * i, a + 2 * i + 1); }
    Graph g = GraphCreate(v, e, a);
    free(a);
    return g;
}

int* GraphAdjcency(Graph g, int v, int *n) { return LinkedListBagItems(g->adj[v], n); }

void GraphIterateAdjency(Graph g, int v, void(*func)(int, void*), void *context) {
    int n = 0;
    int *adj = GraphAdjcency(g, v, &n);
    for (int i = 0; i < n; i++) { func(adj[i], context); }
    if (adj != NULL) { free(adj); }
}

void GraphRelease(Graph g) { 
    if (g != NULL) {
        for (int i = 0; i < g->v; i++) { LinkedListBagRelease(g->adj[i]); }
        free(g); 
    }
}

void GraphPrint(Graph g) {
    if (g != NULL) {
        printf("%i vertices, %i edges\n", g->v, g->e);
        for (int i = 0; i < g->v; i++) {
            printf("%i: ", i);
            int n = 0;
            int *adj = LinkedListBagItems(g->adj[i], &n);
            if (adj != NULL) {
                printa(adj, n);
                free(adj);
            }
        }
        printf("\n");
    }
}
#endif

相关文章

网友评论

      本文标题:Concerning Graph Part I: Basic I

      本文链接:https://www.haomeiwen.com/subject/qqwooktx.html