Graph Implementation in C

I want to know what is best and fastest way of implementing graph data structure and its related algorithms.

1. Adjacency-List is suggested by the book.

But I fail to under开发者_如何学Pythonstand for a large graph when I want to find the edge between the two vertices v1 and v2

I will have to traverse through the array which will be O(n).

Is my understanding correct or there is better approach to get this done.

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

You can use an adjacency matrix instead of the list. It will let you find edges very quickly, but it will take up a lot of memory for a large graph.

There are many ways of implementing graphs. You should choose the one that suits your algorithm best. Some ideas:

a) Global node and edge list.

b) Global node list, per-node edge list.

c) Adjacency matrix (A[i][j] = w(edge connecting Vi-Vj if it exists), 0 otherwise)

d) Edge matrix.(A[i][j] = 1 if the Ei connects the node Vj)