A data structure that consists of a set of nodes (vertices) and a set of edges that relate the nodes to each other. The set of edges describes relationships among the vertices. As a formal definition, a graph G is defined as follows:

V(G): a set of vertices
E(G): a set of edges (pairs of vertices)

Types of Graphs

Directed graph

  • all the edges are directed
  • Edge (u,v) goes from vertex u to vertex v,
  • e.g., route network

Undirected graph

  • all the edges are undirected
  • Edge (u,v) = edge (v,u)
  • e.g., flight network

Applications of Graphs

  • Electronic circuits
  • Transportation networks
    • Highway network
    • Flight network
  • Computer networks
    • Local area network
    • Internet
    • Web

Trees vs graphs

Trees are special cases of graphs!!

Graph terminology

  • Adjacent nodes: two nodes are adjacent if they are connected by an edge
  • Path: a sequence of vertices that connect two nodes in a graph
  • Complete graph: a graph in which every vertex is directly connected to every other vertex
  • What is the number of edges in a complete directed graph with N vertices?  N * (N-1)
  • What is the number of edges in a complete undirected graph with N vertices? N * (N-1) / 2
  • Weighted graph: a graph in which each edge carries a value
Tagged with: C/C++ languageData structures

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Looking for something?

Use the form below to search the site:

Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Related News Feeds

Set your Twitter account name in your settings to use the TwitterBar Section.