Adjacency List

[lost110]

I am trying to print the adjacency list! But its printing wrong data! Its quite confusing because I just have to use loops for it! Its printing wrong data!

 #include <iostream>
using namespace std;
int main()
{

	int size;
	int **ptr;
	int x;
	cout << "Enter rows in 2d array:" << endl;
	cin >> size;
	ptr = new int *[size]; // 2d array of 10*5 .....so size = rows.....array of pointer is made! 
						   // SO WE ARE ASSIGNING A NEW ARRAY TO EACH SINGLE POINTER	

	cout << "Enter columns " << endl;
	cin >> x;
	for (int i = 0; i <size; i++)
	{
		ptr[i] = new int[x];
	}
	cout << "Enter 1 OR 0 as elements in matrix : " << endl;
	for (int i = 0; i <size; i++)
	{
		for (int j = 0; j <x; j++)
		{
			cout << endl;
			cin >> ptr[i][j];
		}
	}
	char y = 'A';
	for (int i = 0; i < x; i++)
	{
		cout << y << '\t';
		y++;
	}
	y = 'A';
	cout << endl;
	for (int i = 0; i <size; i++)
	{
		cout << y;
		for (int j = 0; j <x; j++)
		{
			cout <<  ptr[i][j] << '\t';
			
		}
		y++;
		cout << endl;
	}
	cout << "Adjancy list :" << endl;
	y = 'A';
	for (int i = 0; i < size; i++)
	{
		cout << y;
		for (int j = 0; j < x; j++)
		{
			if (ptr[i][j] == 1)
			{
				cout << "->";
				cout << y;
			}
			else if(ptr[i][j] == 0)
			{
			
				break; // "0" So move to next index
			}
			y++; // increment the alphabet
		}
		cout << endl;
		
	}
	system("pause");
}

[lastchance]

Try

	cout << "Adja[ce]ncy list :" << endl;
	for (int i = 0; i < size; i++)
	{
		cout << (char)('A' + i);
		for (int j = 0; j < x; j++)
		{
			if (ptr[i][j] == 1)
			{
				cout << "->";
		                cout << (char)('A' + j);
			}
		}
		cout << endl;
	}

[lost110]

Cool! Can you explain line 4 and 10 !

[lastchance]

On the assumption that your 0th element is called 'A', then ...
the 1st element is 'A' + 1, or 'B'
the 2nd element is 'A' + 2 or 'C'
...
the ith element is 'A' + i

Each character has an integer value (its position in the character-collating sequence, which is usually, but doesn't have to be, an extension of ASCII). To force it to put out the character rather than the integer, cast it with (char).


Your problems arose because of your (mis)use of variable y and (probably) your misuse of break. This code simply circumvents both issues.


There's quite a lot of other things about your code that gave me the jitters, but I hope this gets it running.

Have fun with graph theory!

[lost110]

Many of my friends are using linked list in this program. Would that be a better approach?

[lastchance]

I think you would find an STL-based graph would probably be easier. (If you are actually doing graphs - you don't say.)

The real trouble with an adjacency matrix like this is that it is very sparse - most entries are zero, so a huge amount of memory is wasted. Also, the adjacency matrix often carries weights, rather than just 1s and 0s.

If I am coding a graph (which I haven't done for a while) then I usually have a 'node' class, a vector of nodes and then, for each node, vectors holding the collection of other nodes accessible from the given node.

geeksforgeeks.org has many examples of graphs, both using and not using the STL.

In answer to your question - I don't know and I'm not the best to give advice. You would need to say what you are trying to do and how many nodes your problem is likely to have.

[lost110]

How would I reverse this code ? i.e from list to matrix