CODEWITHSUNDEEP
c++graphadjacency-matrix
Claud
Claud

Reputation: 1075

Using adjaceny matrix to solve graph problems

I was just wondering how you can use and adjacency matrix to solve graph problems.

For example for my program I have an exchange rate for two items.

Input to build a directed graph: 6 shirts 15 socks Input to build a directed graph: 2 socks 1 underwear

Directed graph:

shirts --(6/15)-- socks --(2/1)-- underwear

So the edge from shirts to socks is 6, edge from socks to shirts is 15, socks to underwear is 2 and underwear to socks is 1.

Input to compare: socks shirts Solution : 15 socks 6 shirts

Input to compare: shirts underwear Soltuion : 12 shirts 15 underwear

My question is how can I represent this with an adjacency matrix and be able to get its weight to solve the problem.

I was thinking of having an adjacency matrix that would look like this for the above problem.

          shirts   socks  underwear
shirts    [ 0       6     0 ]
socks     [ 15      0     2 ]
underwear [ 0       1     0 ]

Is this a good start? I'm trying to get the logic before the code.

Just looking for some more information on how to do this on a bigger scale with more items and separate graphs.

Upvotes: 0

Views: 3315

Answers (2)

Shahbaz
Shahbaz

Reputation: 47493

I will give you a basic hint on what is an adjacency graph. Solving your problem is your homework so I cannot do it.

Imagine the following graph:

    A-----B
   / \   | \
  /   \  |  \
 /     \ |   \
C-------D-----E

An adjacency matrix tells which node in the graph is connected to which:

    A  B  C  D  E
A [ 0  1  1  1  0 ]
B [ 1  0  0  1  1 ]
C [ 1  0  0  1  0 ]
D [ 1  1  1  0  1 ]
E [ 0  1  0  1  0 ]

For example entry (D, E) shows that D and E are connected, while (A, E) shows that A and E are not. Note that this matrix is symmetric because the graph is undirected.

If the matrix is weighted as follows:

    A--3--B
   / \   | \
  5   3  2  1
 /     \ |   \
C---2---D--7--E

then the adjacency matrix shows which are connected and with what weight (assuming 0 shows no connection):

    A  B  C  D  E
A [ 0  3  5  3  0 ]
B [ 3  0  0  2  1 ]
C [ 5  0  0  2  0 ]
D [ 3  2  2  0  7 ]
E [ 0  1  0  7  0 ]

In your case, your graph is a bunch of nodes having edges to a bunch of other nodes. Your adjacency matrix would look very similar to what you have already come up with, but the values might not be correct. The values should be either the same, negative of each other or 1 over the other, depending on what your algorithm is going to be.

Upvotes: 2

blahman
blahman

Reputation: 1314

This was a previous SO post I wrote about how you could represent graphs, using Adjacency Matrices or Adjacency Lists.

It discusses solving the Minimum Spanning Tree graph problem and which of the data structures would be appropriate for solving the problem. I'm not sure what you're trying to accomplish with your graph problem, but this would be a starting point as to how you represent graphs. I'll try and edit my answer if you add more information.

Upvotes: 0

Related Questions