Featured Posts
First, a little about how we perceive images and then the details about how it is displayed on the computer screen.

Every object's color we see is a composite of Red, Green and Blue components. The mixture of these primary colors in different proportions produces the entire spectrum of colors we can see. There are two ways we can understand this - One is the additive color system and the second is the subtractive color system.

In an additive color scheme, we understand colors as a mixture of primary colors - Red, Green and Blue (RGB). For example, Yellow is an equal mixture of Red and Green colors. White is an equal mixture or red, green, blue components.


In the subtractive scheme, we understand colors based on what quantities of primary colors are absorbed by an object and what is reflected off of it. For example, an object in white light that absorbs no wavelengths of the visible light spectrum appears white because it reflects everything. Similarly, an object appears black because it absorbs everything and reflects nothing. 

How colors are represented in a computer and rendered on the screen:

In a computer, the primary colors Red, Green and Blue are represented by bits. These bits are rendered by tiny display units called pixels. The display unit is a huge grid of individual pixels and each pixel can display a mixture of primary colors. Now if you have one bit for each color RGB, how many different colors could be represented with it? The answer is 2^3=8 colors. Each bit can take a value 0 or 1.

R G B                           R G B               R G B                           R G B
0  0 0    = Black            1  0 0  = Red    0  1 0 = Green               0 0  1 = Blue

R G B                            R G B                  R G B               R G B   
1  1  1   = White             1  1 0 = Yellow   0  1 1 = Cyan   1  0  1  = Magenta

Computers usually deal with 8 bits of information for every color for each pixel. So each component R,G or B can take 256 different values. That's 256 different shades of Red, Green and Blue or 256^3 = 16 million different color combinations that can represent virtually any color possible.


An image file like bitmap (.bmp) consists of color data for each pixel and color in a grid called the raster. You can visualize the raster as follows:


Each square represents a pixel and for each pixel, the image file holds the exact mixture of Red, Green and Blue colors. On a monitor, there are thousands of pixels close to each other. They are so tiny that the human eye cannot spot them. This is the secret of producing a life like image on screen. Because the pixels are so densely packed (On a 15 inch screen with resolution of 1366x768, there are 104 pixels per inch (PPI), the human eye cannot distinguish between individual pixels.

This raster data is then mapped to the screen where it is displayed. Each pixel takes the color corresponding to it's position in the raster data. See the image below. On the left side is the image that you normally see. But when you zoom in, you can see individual pixels taking different colors.


How are pixels actually rendered on screen?

This depends on the type of monitor. In the old days, we had the Cathode Ray Tube (CRT monitor).


In a CRT monitor, there exists a device called the electron gun which shoots electrons onto a phosphor screen. Phosphor is a fluorescent material and glows when electrons bombard them. The color produced by the phosphor element depends of the energy of the electrons which is controlled by the electron gun.

The electron gun shoots electrons and the trajectory of electrons is controlled by magnetic deflections. Based on the raster data, the electron gun starts at the top left and shoots electrons line by line at the desired energy based on the color that is to be produced at that point. Once it reaches the bottom of the screen, it goes back up and repeats. This process is called scanning and the rate at which it happens is called the refresh rate.


We have come a far way from CRTs and now have TFT LCD (Thin film transistor Liquid Crystal Display) screens. These screens work very differently. They rely on a special property of Liquid Crystals in the presence/absence of an electric field. Liquid crystals in a twisted nematic state reorient polarized light.

In a LCD display, the liquid crystal is sandwiched between two polarizers that are 90 degrees out of phase (1 and 5 in the figure below are polarizers).


When light passes through the first polarizer, it gets horizontally oriented. When there is no electric field, the Liquid crystal reorients this light and brings it in phase with the second polarizer. When an electric field is applied, the molecules in the liquid crystal align with the field and untwist. In this state, it doesn't reorient the light. Since the light is 90 degrees out of phase with the second polarizer, it cannot pass through it. White light source is used to illuminate the panel and filters are used to produce color.


In a  TFT LCD, the electric field is controlled by thin silicon transistors arranged in a grid. Each pixel in the grid has a liquid crystal element sandwiched between two capacitive plates supplied by the transistors. By turning the transistors on and off, we can control the intensity and color produced by the pixels.


The hardware takes care of rendering the image and the device drivers know how to communicate the raster to the hardware (it's hardware specific). The only thing left is to create the image file. There are different formats, but they all contain the RGB information about pixels.

fffeewww.... Thats huge... Hope now you know how these things actually work. This article has been contributed by someone on quora so I thought its useful..

Later, people.... :)
Its been a long time since I'd posted something about programming and algorithms. I've been reading a lot more about algorithms, so found one perfectly explained article, thought I should share it with you people.

Using Stack is the obvious way to traverse tree without recursion. Below is an algorithm for traversing binary tree using stack.
See this for step wise step execution of the algorithm.

1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and set current = current->left until current is NULL
4) If current is NULL and stack is not empty then
     a) Pop the top item from stack.
     b) Print the popped item, set current = current->right
     c) Go to step 3.
5) If current is NULL and stack is empty then we are done.

Let us consider the below tree for example:

            1
          /   \
        2      3
      /  \
    4     5

Step 1 Creates an empty stack: S = NULL

Step 2 sets current as address of root: current -> 1

Step 3 Pushes the current node and set current = current->left until current is NULL
     current -> 1
     push 1: Stack S -> 1
     current -> 2
     push 2: Stack S -> 2, 1
     current -> 4
     push 4: Stack S -> 4, 2, 1
     current = NULL

Step 4 pops from S
     a) Pop 4: Stack S -> 2, 1
     b) print "4"
     c) current = NULL /*right of 4 */ and go to step 3
Since current is NULL step 3 doesn't do anything.

Step 4 pops again.
     a) Pop 2: Stack S -> 1
     b) print "2"
     c) current -> 5/*right of 2 */ and go to step 3

Step 3 pushes 5 to stack and makes current NULL
     Stack S -> 5, 1
     current = NULL

Step 4 pops from S
     a) Pop 5: Stack S -> 1
     b) print "5"
     c) current = NULL /*right of 5 */ and go to step 3
Since current is NULL step 3 doesn't do anything

Step 4 pops again.
     a) Pop 1: Stack S -> NULL
     b) print "1"
     c) current -> 3 /*right of 5 */

Step 3 pushes 3 to stack and makes current NULL
     Stack S -> 3
     current = NULL

Step 4 pops from S
     a) Pop 3: Stack S -> NULL
     b) print "3"
     c) current = NULL /*right of 3 */

Traversal is done now as stack S is empty and current is NULL.

Implementation:


#include<stdio.h>
#include<stdlib.h>
#define bool int

/* A binary tree tNode has data, pointer to left child
   and a pointer to right child */
struct tNode
{
   int data;
   struct tNode* left;
   struct tNode* right;
};

/* Structure of a stack node. Linked List implementation is used for
   stack. A stack node contains a pointer to tree node and a pointer to
   next stack node */

struct sNode
{
  struct tNode *t;
  struct sNode *next;
};

/* Stack related functions */
void push(struct sNode** top_ref, struct tNode *t);
struct tNode *pop(struct sNode** top_ref);
bool isEmpty(struct sNode *top);

/* Iterative function for inorder tree traversal */
void inOrder(struct tNode *root)
{
  /* set current to root of binary tree */
 struct tNode *current = root;
  struct sNode *s = NULL;  /* Initialize stack s */
  bool done = 0;
  while (!done)
  {
    /* Reach the left most tNode of the current tNode */
    if(current !=  NULL)
    {
      /* place pointer to a tree node on the stack before traversing
        the node's left subtree */
      push(&s, current);                                              
      current = current->left; 
    }      
    /* backtrack from the empty subtree and visit the tNode
       at the top of the stack; however, if the stack is empty,
      you are done */
    else                                                            
    {
      if (!isEmpty(s))
      {
        current = pop(&s);
        printf("%d ", current->data);

        /* we have visited the node and its left subtree.
          Now, it's right subtree's turn */
        current = current->right;
      }
      else
        done = 1;
    }
  } /* end of while */
}    

/* UTILITY FUNCTIONS */

/* Function to push an item to sNode*/
void push(struct sNode** top_ref, struct tNode *t)
{
  /* allocate tNode */
  struct sNode* new_tNode =
            (struct sNode*) malloc(sizeof(struct sNode));
  if(new_tNode == NULL)
  {
     printf("Stack Overflow \n");
     getchar();
     exit(0);
  }           
  /* put in the data  */
  new_tNode->t  = t;
  /* link the old list off the new tNode */
  new_tNode->next = (*top_ref);  

  /* move the head to point to the new tNode */
  (*top_ref)    = new_tNode;
}

/* The function returns true if stack is empty, otherwise false */
bool isEmpty(struct sNode *top)
{
   return (top == NULL)? 1 : 0;
}  
/* Function to pop an item from stack*/

struct tNode *pop(struct sNode** top_ref)
{
  struct tNode *res;
  struct sNode *top;

  /*If sNode is empty then error */
  if(isEmpty(*top_ref))
  {
     printf("Stack Underflow \n");
     getchar();
     exit(0);
  }
  else
  {
     top = *top_ref;
     res = top->t;
     *top_ref = top->next;
     free(top);
     return res;
  }
}

/* Helper function that allocates a new tNode with the
   given data and NULL left and right pointers. */
struct tNode* newtNode(int data)
{
  struct tNode* tNode = (struct tNode*)
                       malloc(sizeof(struct tNode));
  tNode->data = data;
  tNode->left = NULL;
  tNode->right = NULL;

  return(tNode);
}

/* Driver program to test above functions*/
int main()
{

  /* Constructed binary tree is

            1

          /   \

        2      3

      /  \

    4     5

  */
  struct tNode *root = newtNode(1);
  root->left        = newtNode(2);
  root->right       = newtNode(3);
  root->left->left  = newtNode(4);
  root->left->right = newtNode(5);

  inOrder(root);

  getchar();
  return 0;
}

Time Complexity: O(n)

This article has been shared from Geeks for Geeks. Please let me know if you have any concern about anything in this article.

Later folks.... :)
Given a linked list, write a function to reverse every alternate k nodes (where k is an input to the function) in an efficient way. Give the complexity of your algorithm.

Example:
Inputs:   1->2->3->4->5->6->7->8->9->NULL and k = 3
Output:   3->2->1->4->5->6->9->8->7->NULL.

Method 1 (Process 2k nodes and recursively call for rest of the list) 

This method is basically an extension of the method discussed in this post.
kAltReverse(struct node *head, int k)
  1)  Reverse first k nodes.
  2)  In the modified list head points to the kth node.  So change next
       of head to (k+1)th node
  3)  Move the current pointer to skip next k nodes.
  4)  Call the kAltReverse() recursively for rest of the n - 2k nodes.
  5)  Return new head of the list.

#include<stdio.h>

#include<stdlib.h>



/* Link list node */

struct node

{

    int data;

    struct node* next;

};



/* Reverses alternate k nodes and

   returns the pointer to the new head node */

struct node *kAltReverse(struct node *head, int k)

{

    struct node* current = head;

    struct node* next;

    struct node* prev = NULL;

    int count = 0;  



    /*1) reverse first k nodes of the linked list */

    while (current != NULL && count < k)

    {

       next  = current->next;

       current->next = prev;

       prev = current;

       current = next;

       count++;

    }

  

    /* 2) Now head points to the kth node.  So change next

       of head to (k+1)th node*/

    if(head != NULL)

      head->next = current;  



    /* 3) We do not want to reverse next k nodes. So move the current

        pointer to skip next k nodes */

    count = 0;

    while(count < k-1 && current != NULL )

    {

      current = current->next;

      count++;

    }



    /* 4) Recursively call for the list starting from current->next.

       And make rest of the list as next of first node */

    if(current !=  NULL)

       current->next = kAltReverse(current->next, k);



    /* 5) prev is new head of the input list */

    return prev;

}



/* UTILITY FUNCTIONS */

/* Function to push a node */

void push(struct node** head_ref, int new_data)

{

    /* allocate node */

    struct node* new_node =

            (struct node*) malloc(sizeof(struct node));



    /* put in the data  */

    new_node->data  = new_data;



    /* link the old list off the new node */

    new_node->next = (*head_ref);   



    /* move the head to point to the new node */

    (*head_ref)    = new_node;

}



/* Function to print linked list */

void printList(struct node *node)

{

    int count = 0;

    while(node != NULL)

    {

        printf("%d  ", node->data);

        node = node->next;

        count++;

    }

}   



/* Drier program to test above function*/

int main(void)

{

    /* Start with the empty list */

    struct node* head = NULL;



    // create a list 1->2->3->4->5...... ->20

    for(int i = 20; i > 0; i--)

      push(&head, i);



     printf("\n Given linked list \n");

     printList(head);

     head = kAltReverse(head, 3);



     printf("\n Modified Linked list \n");

     printList(head);



     getchar();

     return(0);

}

Output:
Given linked list
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Modified Linked list
3 2 1 4 5 6 9 8 7 10 11 12 15 14 13 16 17 18 20 19

Time Complexity: O(n)

Method 2 (Process k nodes and recursively call for rest of the list) 

The method 1 reverses the first k node and then moves the pointer to k nodes ahead. So method 1 uses two while loops and processes 2k nodes in one recursive call.

This method processes only k nodes in a recursive call. It uses a third bool parameter b which decides whether to reverse the k elements or simply move the pointer.

_kAltReverse(struct node *head, int k, bool b)
  1)  If b is true, then reverse first k nodes.
  2)  If b is false, then move the pointer k nodes ahead.
  3)  Call the kAltReverse() recursively for rest of the n - k nodes and link
       rest of the modified list with end of first k nodes.
  4)  Return new head of the list.

#include<stdio.h>

#include<stdlib.h>



/* Link list node */

struct node

{

    int data;

    struct node* next;

};



/* Helper function for kAltReverse() */

struct node * _kAltReverse(struct node *node, int k, bool b);



/* Alternatively reverses the given linked list in groups of

   given size k. */

struct node *kAltReverse(struct node *head, int k)

{

  return _kAltReverse(head, k, true);

}

 

/*  Helper function for kAltReverse().  It reverses k nodes of the list only if

    the third parameter b is passed as true, otherwise moves the pointer k

    nodes ahead and recursively calls iteself  */

struct node * _kAltReverse(struct node *node, int k, bool b)

{

   if(node == NULL)

       return NULL;



   int count = 1;

   struct node *prev = NULL;

   struct node  *current = node;

   struct node *next;

 

   /* The loop serves two purposes

      1) If b is true, then it reverses the k nodes

      2) If b is false, then it moves the current pointer */

   while(current != NULL && count <= k)

   {

       next = current->next;



       /* Reverse the nodes only if b is true*/

       if(b == true)

          current->next = prev;

            

       prev = current;

       current = next;

       count++;

   }

   

   /* 3) If b is true, then node is the kth node.

       So attach rest of the list after node.

     4) After attaching, return the new head */

   if(b == true)

   {

        node->next = _kAltReverse(current,k,!b);

        return prev;       

   }

   

   /* If b is not true, then attach rest of the list after prev.

     So attach rest of the list after prev */  

   else

   {

        prev->next = _kAltReverse(current, k, !b);

        return node;      

   }

}

 



/* UTILITY FUNCTIONS */

/* Function to push a node */

void push(struct node** head_ref, int new_data)

{

    /* allocate node */

    struct node* new_node =

            (struct node*) malloc(sizeof(struct node));

 

    /* put in the data  */

    new_node->data  = new_data;

 

    /* link the old list off the new node */

    new_node->next = (*head_ref);

 

    /* move the head to point to the new node */

    (*head_ref)    = new_node;

}

 

/* Function to print linked list */

void printList(struct node *node)

{

    int count = 0;

    while(node != NULL)

    {

        printf("%d  ", node->data);

        node = node->next;

        count++;

    }

}

 

/* Drier program to test above function*/

int main(void)

{

    /* Start with the empty list */

    struct node* head = NULL;

    int i;

 

    // create a list 1->2->3->4->5...... ->20

    for(i = 20; i > 0; i--)

      push(&head, i);

 

    printf("\n Given linked list \n");

    printList(head);

    head = kAltReverse(head, 3);

 

    printf("\n Modified Linked list \n");

    printList(head);

 

    getchar();

    return(0);

}
Output: Given linked list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Modified Linked list 3 2 1 4 5 6 9 8 7 10 11 12 15 14 13 16 17 18 20 19 Time Complexity: O(n)
Hello folks, hope you people are doing well..

I have tried some of the techniques to print 100 to 1 without using any loops in the program. So here are some of the best suitable techniques. Actually I only have one right now, but will surely share others as soon as I get some better differences between them to share.

Main concept here is to use Recursion.

Method #1:


#include <iostream>

using namespace std;

void printvals(int);



void printvals(int n)

{

  if(n!=0)

  {

  cout<<n<<" ";

  printvals(--n);

  }

}

int main()

{

  int i=100;

  printvals(i);

  return 0;

}

Later Folks...... :)
Automatic: auto 

  • storage is automatically allocated on function/block entry and automatically freed when the function/block is exited 
  • may not be used with global variables (which have storage space that exists for the life of the program) 
  • auto is the default for function/block variables 
    • auto int a is the same as int a 
    • because it is the default, it is almost never used

Optimization Hint: register

  • register provides a hint to the compiler that you think a variable will be frequently used
  • compiler is free to ignore register hint
  • if ignored, the variable is equivalent to an auto variable with the exception that you may not take the address of a register (since, if put in a register, the variable will not have an address)
  • rarely used, since any modern compiler will do a better job of optimization than most programmers

Static Storage: static

  • if used inside a block or function, the compiler will create space for the variable which lasts for the life of the program
  •   int
      counter(void)
      {
     static int cnt = 0;
    
     return cnt++;
      }
    
    causes the counter() function to return a constantly increasing number

External References: extern

  • If a variable is declared (with global scope) in one file but referenced in another, the extern keyword is used to inform the compiler of the variable's existence:
    • In declare.c:
      int farvar;
      
    • In use.c:
      {
       extern int farvar;
       int a;
       a = farvar * 2;
      }
      
  • Note that the extern keyword is for declarations, not definitions
    • An extern declaration does not create any storage; that must be done with a global definition

Private Variables: static

  • another use for the static keyword is to ensure that code outside this file cannot modify variables that are globally declared inside this file
    • If declare.c had declared farvar as:
      static int farvar;
      
      then the extern int farvar statement in use.c would cause an error
    • This use of static is commonly used in situations where a group of functions need to share information but do not want to risk other functions changing their internal variables
      static int do_ping = 1; /* start with `PING' */
      
      void
      ping(void)
      {
       if (do_ping == 1) {
        printf("PING ");
        do_ping = 0;
       }
      }
      
      void
      pong(void)
      {
       if (do_ping == 0) {
        printf("PONG\n");
        do_ping = 1;
       }
      }

Variable Initialization

  • autoregister and static variables may be initialized at creation:
      int
      main(void)
      {
     int a = 0;
     register int start = 1234;
     static float pi = 3.141593;
      }
    
  • Any global and static variables which have not been explicitly initialized by the programmer are set to zero
  • If an auto or register variable has not been explicitly initialized, it contains whatever was previously stored in the space that is allocated to it
    • this means that auto and register variables should always be initialized before being used
    • compiler may provide a switch to warn about uninitialized variables
Its been very important that you know all the techniques of converting a decimal into binary or vice-versa. Here I am going to show two techniques of converting a decimal into binary, one of them is using bit-manipulation and the other one is conventional.

One conventional method of converting decimal into binary is shown below:

Here is the implementation:

#include <iostream>

#include <math.h>

using namespace std;



void dec2bin(unsigned n, int a[])

/* This method is bit-manipulation */ 

{

   unsigned i, j=0;

   for(i = 1 << 15; i>0; i = i/2)

   {
a
  if(n & i)

  {

   a[j++] = 1;

  }

  else

  {

   a[j++] = 0;

  }

   }

}



void dec2bin2(int n)

/* Conventional Method */ 

{

   if(n>1)

  dec2bin2(n/2);

  

   printf("%d", n%2);

}



int main()

{

   int a[16] = {0}, i, sum=0;

   dec2bin(4, a);

   for(i=0; i<=15; i++)

  cout<<a[i];

   cout<<endl;

   //dec2bin2(65535);

   

   /* Below method will convert the binary into Decimal */
   for(i=0; i<16; i++)

   {

  sum+=((pow(2, (15-i)))*a[i]);

   }

   cout<<"Decimal: "<<sum;

   return 0;

}

I have shown two methods of converting the decimal number into binary and one method in the main() to show the conversion of binary in decimal number...

Let me know if you have any queries or above program requires any correction...
.... Next time... :)

I have discussed O(n) method for finding first non-repeating character in a given string.
You can find it here Method-1

The above approach takes O(n) time, but in practice it can be improved. The first part of the algorithm runs through the string to construct the count array (in O(n) time). This is reasonable. But the second part about running through the string again just to find the first non-repeater is not good in practice. In real situations, your string is expected to be much larger than your alphabet. Take DNA sequences for example: they could be millions of letters long with an alphabet of just 4 letters. What happens if the non-repeater is at the end of the string? Then we would have to scan for a long time (again).

We can augment the count array by storing not just counts but also the index of the first time you encountered the character e.g. (3, 26) for ‘a’ meaning that ‘a’ got counted 3 times and the first time it was seen is at position 26. So when it comes to finding the first non-repeater, we just have to scan the count array, instead of the string. Thanks to Ben for suggesting this approach.

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#define NO_OF_CHARS 256

// Structure to store count of a character and index of the first
// occurrence in the input string
struct countIndex {
   int count;
   int index;
};

/* Returns an array of above structure type. The size of
   array is NO_OF_CHARS */
struct countIndex *getCharCountArray(char *str)
{
   struct countIndex *count =
        (struct countIndex *)calloc(sizeof(countIndex), NO_OF_CHARS);
   int i;
   for (i = 0; *(str+i);  i++)
   {
      (count[*(str+i)].count)++;

      // If it's first occurrence, then store the index
      if (count[*(str+i)].count == 1)
         count[*(str+i)].index = i;
   }
   return count;
}

/* The function returns index of first non-repeating
   character in a string. If all characters are repeating
   then reurns INT_MAX */
int firstNonRepeating(char *str)
{
  struct countIndex *count = getCharCountArray(str);
  int result = INT_MAX, i;

  for (i = 0; i < NO_OF_CHARS;  i++)
  {
    // If this character occurs only once and appears
    // before the current result, then update the result
    if (count[*(str+i)].count == 1 &&
        result > count[*(str+i)].index)
      result = i;
  }
 
  free(count); // To avoid memory leak
  return result;
}

/* Driver program to test above function */
int main()
{
  char str[] = "HelloWorldHowAreYou";
  int index =  firstNonRepeating(str);
  if(index == INT_MAX)
    printf("Either all characters are repeating or string is empty");
  else
   printf("First non-repeating character is %c", str[index]);
  getchar();
  return 0;
}
Hope it helps... ....Next time... :)
Given a string, find the first non-repeating character in it. For example, if the input string is “HelloWorld”, then output should be ‘H’ and if input string is “HelloHowAreYou”, then output should be ‘w’.

We can use string characters as index and build a count array. Following is the algorithm.

1) Scan the string from left to right and construct the count array.
2) Again, scan the string from left to right and check for count of each
 character, if you find an element who's count is 1, return it.

Example:

Input string: str = helloworld
1: Construct character count array from the input string.

  count['h'] = 1
  count['e'] = 1
  count['l'] = 3
  count['o'] = 2
  count['w'] = 1
  ……
2: Get the first character who's count is 1 ('h').

Implementation:
#include <iostream>

#include <malloc.h>

#define NO_OF_CHAR 256

using namespace std;



int *getcharcountarray(char *str)

{

    int *count = (int *)calloc(sizeof(int), NO_OF_CHAR);

    int i;

    for(i=0; *(str+i); i++)

     count[*(str+i)]++;

    return count;

}



int gettheindex(char *str)

{

    int *count = getcharcountarray(str);

    int index = -1, i;

    

    for(i=0; *(str+i); i++)

    {

     if(count[*(str+i)] == 1)

     {

         index = i;

         break;

     }

    }

    free(count);

    return index;

}



int main()

{

    char str[] = "samsungelectronics";

    int index = gettheindex(str);

    if(index == -1)

     cout<<"Either all characters are repeating or string is empty"<<endl;

    else

     cout<<"First repeating character is "<<str[index]<<endl;

    return 0;



}
As I have explained basic concepts of the Graph in my previous post, I hope it is clear to you people. Now, I am going to show, how you can represent this graph in programming. 

Now, if I call these vertices as to be the pieces of similar information and the edges as to be the various linkages between them, then, you can certainly think of representing any Graph with the help of Linked Lists, can't you?
Well, we'll see that implementation in our next section. But for now, you've a bit simpler representation of Graphs, the Adjacency Matrix. This matrix shows you all the direct linkages between the vertices; meaning the direct edges between the vertices. Let me explain this with the help of an example -



Consider, this directed graph. It has five vertices and five edges - AD, BD, CB, DE and EC. The Adjacency matrix for this will be -

A B C D E
A 0 0 0 1 0
B 0 0 0 1 0
C 0 1 0 0 0
1 if the edge is there
0 if no edge is there
D 0 0 0 0 1
E 0 1 0 0 0

Now you know why it is called as an adjacency matrix. It only shows the direct paths between the vertices but you can see there exist paths which have intermediate vertices also; like from A to B you have D->E->C. 

Remember, it does not matter if the graph is weighted, the adjacency matrix is gonna remain the same.

Note:- When I say route, I mean the direct path between the vertices and that no other vertex is there in that path except the two adjacent vertices forming the edge. I guess you know how to store a 2D-matrix in an array! That is left for your practice.

#include <iostream>
#define MAX 5
using namespace std;
int main()
{
int E, V[MAX]; //E=number of Edges, V=Vertices
int i, j;
int temp1=0, temp2=0;
int adj_mat[MAX][MAX] = {0}; //Adjacency Matrix
cout<<"Enter Vertices"<<endl; //Enter all the vertices. for example 1,2,3,4 etc..
for(i=0; i<MAX; i++)
{
cin>>V[i];
}
cout<<"Enter number of Edges"<<endl;
cin>>E; //Total number of edges between vertices.

for(j=0; j<E; j++)
{
cout<<"Edge #"<<j+1<<" "; //j+1 because we will be starting from Edge #1 and not 0.
cin>>temp1; //Path from
cin>>temp2; //Path To
//Path from and to, are in case of directed graph.
adj_mat[temp1-1][temp2-1] = 1; //Placing 1 in appropriate place in adjacency matrix
} for(i=0; i<MAX; i++)
{
for(j=0; j<MAX; j++)
{
cout<<adj_mat[i][j]<<" "; //Display the adjacency matrix.
}
cout<<endl;
}
return 0; //Get back in where you came from... :)
}
I've been reading about the data structures a lot lately and came across this article on the website http://datastructures.itgo.com, So I though this is worth sharing on my blog. The person has neatly explained about the data structures and I am going to share some of the information available. So lets start with Graph.

Sorry! I can't give that mathematical definition, involving all those Vs and  Es, for the Graphs. Rather, take it this way - a graph is a collection of some finite VERTICES and some finite EDGES which happen to connect these vertices. If I consider a given list of cities as my list of VERTICES then you can, probably, call the air routes between them as to be the EDGES for them.'

Based on this analogy, we can say that a Directed Graph is a one in which you have one way air routes and that you can not come back through that same route; means, you can fly from Delhi to Mumbai but can not come back through that same route. Similarly, if you have two way air routes between the cities then I call it, an Undirected Graph. Finally, if its not a sponsored journey then certainly you will have to bear the ticket fare, which means every route (EDGE) has some cost of journey attached and that makes it a Weighted Graph. No fare, no weight!

Directed Graph
Undirected Graph


Weighted Graph
Directed Graph:-  
Vertices(cities): A, B, C and D        
Edges(routes): AB, AC, CD

Undirected Graph:-  

Vertices: A, B, C, D     
Edges:  AB, AC, BA, CD, DC
  
Weighted Graph:-  

Vertices: A, B, C, D      
Weighted Edges: AC-10, AB-17, CD-13

You might be thinking by now, what these Graphs have to do with computers! Well, to name a few I'll give you some applications of it - in the study of information routing on computer networks (helps in finding the shortest routes); electronic circuit designing (helps to find out the electrical loops and overlaps); ticketing software uses it to find out the shortest route... Got the idea!


Note:- When I said route here, I meant the direct path between the adjacent vertices and that no other vertex is there in that path except the two adjacent vertices forming the path.