2

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 understand 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.

Improve this question
5
  • You will indeed have to traverse through the list, but that is usually not a problem, since most graph algorithms look at all edges from a given vertex, so traversing the list costs O(1) for each edge. Although if you need to check if an edge exists, say (v1, v2), then maybe an adjacency matrix is more suited to your situation Commented Mar 30, 2011 at 20:08
  • How well this situation work with huge graphs ? Commented Mar 30, 2011 at 20:10
  • 1
    How well depends on your situation, it's faster lookup, but more memory. Do you have memory/speed restrictions? If so, what is more important and what is less? Do you have a specific set of algorithms you will be executing, if so, then tailor your data strcuture to optimise for those algorithms... Commented Mar 30, 2011 at 20:13
  • Those might help: stackoverflow.com/q/3218124/509868 stackoverflow.com/q/4504646/509868 Commented Mar 30, 2011 at 20:14
  • maybe a sparse matrix? (Yea awkward, probably best to look for an existing implementation) Commented Mar 30, 2011 at 20:49

3 Answers 3

Reset to default
2

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

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

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.

Improve this answer

Comments

0

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)

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.