Data Structure and Algorithm

/*******************************************************
APPLICATION : Program to create Adjacency Matrix (using Linked List)
CODED BY    : Ankit Pokhrel
COMPILED ON : Borland C++ Ver 5.02
DATE     : 2010 - October - 12
********************************************************/

#include "iostream.h"
#include "conio.h"

struct Node //Structure to represent a Node or Vertices of a Graph
{
char data;
struct Node *next,*head; //Pointers to next node and Start
struct Adjacent *adj; //Pointer to Adjacent node
};

struct Adjacent //Structure to represent Adjacent node of a Graph
{
char data;
struct Adjacent *adj; //Pointer for next Adjacent
};

Node *New,*top; //Global Variables for New node and Pointer to Top
void create()
{
New = new Node; //Create a node
New -> next = NULL;
New -> adj = NULL;
}

void CreateVertices(Node *&n,char Item) //Function to Create a Vertices of a Graph
{
if(n == NULL) //if first node
  {
   n = new Node; //Create a node
   n -> data = Item; //Insert Data
   n -> next = NULL;
   n -> adj = NULL;
   n -> head = n; //Initialize head
   top = n; //Update top
   return;
  }

create(); //Create a node
New -> data = Item; //Insert Item
top -> next = New; //Assign new node to next of top
top = New; //Update top
}

void LinkVertices(Node *&n)
{
Adjacent *a,*ptr;
cout << "\nEnter Link for each Vertices (0 at Last Input): ";
Node *temp = n -> head;
while(temp != NULL) //Until last
{
  cout << "\nEnter Adjacents of " << temp -> data << " : ";
  int flag = 0;
  char ch = ' ';
  do
   {
    cin >> ch; //Scan Adjacent
    a = new Adjacent; //Create an Adjacent
    a -> data = ch; //Insert Data
    a -> adj = NULL;
    if(flag == 0) //if first Adjacent
     {
      temp -> adj = a;
      ptr = a;
      flag++; //Increase flag
     }

    else
     {
      ptr -> adj = a;
      ptr = a;
     }
   }while(ch != '0');
   temp = temp -> next;
  }
}

void display(Node *n)
{
if(n == NULL)
  {
   cout << "Graph is Empty.";
   return;
  }

Node *temp = n;
Adjacent *a;
while(temp != NULL) //Until Last
  {
   cout << temp -> data << ' '; //Print first data
   a = temp -> adj; //go to adjacent node
   while(a -> adj != NULL) //Until last of adjacent
    {
     cout << a -> data << ' '; //print adjacent
     a = a -> adj; //goto next adjacent
    }
   cout << endl;
   temp = temp -> next; //goto next Node
  }
}

int main()
{
int m;
char ch;
Node *nd = NULL;
cout << "How Many Vertices? "; //Number of Nodes on a Graph
cin >> m;

cout << "\nEnter Vertices Name : "; //Input the name of Vertices
for(int i = 0;i < m;i++)
  {
   cin >> ch;
   CreateVertices(nd,ch);
  }

LinkVertices(nd);
cout << "\nThe Adjacency Matrix is\n";
cout << "-----------------------\n";
display(nd);
getch();
}

OUTPUT

How Many Vertices? 9

Enter Vertices Name : A B C D E F G J K

Enter Link for each Vertices (0 as Last Input):
Enter Adjacents of A : F C B 0

Enter Adjacents of B : G C 0

Enter Adjacents of C : F 0

Enter Adjacents of D : C 0

Enter Adjacents of E : D C J 0

Enter Adjacents of F : D 0

Enter Adjacents of G : C E 0

Enter Adjacents of J : D K 0

Enter Adjacents of K : E G 0

The Adjacency Matrix is
-----------------------
A F C B
B G C
C F
D C
E D C J
G C E
J D K
K E G

Download Original File

Adjacency.cpp