Graph Implementation C++

Graph Adjacency List Implementation (C)

This looks strange:

        new_node->next = G.edges[i].head;
        new_node = G.edges[i].head;

as you overwrite new_node with head.

Maybe you want to do:

        new_node->next = G.edges[i].head;
        G.edges[i].head = new_node;

to make head point to the new node.

Graph Implementation in C

first of all, it is not O(n). Keep the lists sorted and it will be O(logN). Adjacency list need not be necessarily implemented by a linked list. It's more usual to have an array.

Another very popular approach is the adjacency matrix nxn where a[i][j] is 1 (or the weight of the edge) if i and j are connected and 0 otherwise. This approach is optimal for dense graphs, which has many edges. For sparse graphs the adjacencly list tends to be better

Implementation of a directed graph in C

City graph[] is your whole graph, but each City reference adjacent nodes via City.list_adj

and you would treat Node/struct node as a linked list

So I would alter create_arc in this manner:

// shorthand reference
// initialize new node
Node *newnode = malloc(sizeof(Node));
if(newnode == NULL ) {abort();} // prefer spelling out the test.

newnode->vertex_id = tail;
newnode->link=NULL; // not necessary

// insert our new arc at the head of the linked list
City *current = &(graph[head]);
newnode->link = current->list_adj;
current->list_adj = newnode;

Step by step:

1. City.list_adj -> NULL
2. City.list_adj -> NULL , insert0 -> NULL
3. City.list_adj -> insert0 -> NULL
4. City.list_adj -> insert0 -> NULL , insert1 -> Insert0 ...
5. City.list_adj -> insert1 -> insert0 -> NULL
   ...

You could also try inserting at the end of the list, but you would have to search for the list end.

For inserting in order you would have to alter the code the following way:

City *current = &(graph[head]);
// list is size 0 no need to look further
if(current->list_adj == NULL) {
    current->list_adj = newnode;
    return;
}
// insert at the head of the list
if(current->list_adj->vertex_id > head) {
    newnode->link = current->list_adj;
    current->list_adj = newnode;
    return;
}
// look at the rest of the list to find 
Node *insert_point = current->list_adj;
while(insert_point->link != NULL) {
    if(insert_point->link->vertex_id > head) { break; }
    insert_point = insert_point->link;
}
newnode->link = insert_point->link;
insert_point->link = newnode;

Create a graph with letters

This line is wrong

printf("-> %d", pCrawl->dest);

"%d" is the specifier for integers, pCrawl->dest is a pointer to char so this is working because it is printing the address of pCrawl->dest, since pCrawl->dest points to a string, you should use the string format specifier "%s", so use this

printf("-> %s", pCrawl->dest);

C graph adjacency list implementation growing neighbour array

Because it's less costly in terms of CPU time to double the size each time you need more memory instead of adding just 1 to the size.

In the latter case realloc will be called for each newly added edge, and realloc is pretty expensive. Imagine you have 128 edges: realloc will be called 128 times, but if you double the size each time, it will only be called 7 = log2(128) times.

Furthermore realloc will most likely be slower the longer the original memory portion is, because realloc will potentially copy the old memory portion buffer to a new larger one, and the longer the portion, the longer the copying will take.

---

Related Topics