0

There are different ways one can represent a simple undirected graph on a computer:

  • Adjacency lists: Vertices are stored as records or objects, and every vertex stores a list of adjacent vertices. This data structure allows the storage of additional data on the vertices.
  • Incidence list: Vertices and edges are stored as records or objects. Each vertex stores its incident edges, and each edge stores its incident vertices. This data structure allows the storage of additional data on vertices and edges.
  • Adjacency matrix: A two-dimensional matrix, in which the rows represent source vertices and columns represent destination vertices. Data on edges and vertices must be stored externally. Only the cost for one edge can be stored between each pair of vertices.
  • Incidence matrix: A two-dimensional Boolean matrix, in which the rows represent the vertices and columns represent the edges. The entries indicate whether the vertex at a row is incident to the edge at a column.

Two questions:

  1. What are the efficient algorithms to go from one representation to another?
  2. What are the complexities in going from one representation to another?
4
  • 1
    I think the answer to both of your questions is the same as fully traversing a graph. Jan 12, 2013 at 18:16
  • @JonathonReinhart Fully traversing a graph means linear time in the number of vertices plus the number of edges, right?
    – a06e
    Jan 12, 2013 at 18:17
  • Indeed: Inspecting one format requires visiting every node/edge, and creating a new format requires creating every node/edge. Jan 12, 2013 at 18:17
  • Please migrate this question to cstheory.stackexchange.com
    – a06e
    May 22, 2014 at 15:32

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.