Graph Theory(adjacency matrix,adjacency list)

today I will speak about one of the most important topics which are graph theory.

I will take a long time in this series because I wanna speak a lot of data structure related to graph theory

but in the beginning, I will speak about just two representations which are 

(adjacency matrix, adjacency list).

adjacency matrix

the first let's talk about adjacency matrix .this to make a memory representation for any graph

(directed or non-directed) we can imagine that Like 

File:Adjacency matrix for graph.png

code


bool adjacency_matrix[100][100];     
 

Example

n=3
0 1 0
1 1 0
0 1 1

for(int i=0;i<n;i++)
for(int j=0;j<;j++){
int x;
cin>>x;
adjacency_matrix[i][j]=x;

}

adjacency list

then I will speak about adjacency list, how to represent it in memory and how we implement it with code

code


vector< vector<int> > adjList1;               if adjacency list without  weight

vector< vector< pair<int, int> > > adjList2;    if adjacency list with weight


Example-1

              3
2  1 2
1  2
2  0 1
 
cin>>n;
adjList1 = vector< vector<int> >(n);
for(i=0;i< n; i++)
{
int cnt;
cin>>cnt;
for( j=0; j< cnt;j++)
{
int to;
cin>>to;
adjList1[i].push_back(to);
}
}

Example-2



           3
2    1 13 2 4
1    2 9 3 -4
2    0 -7 1 8

cin>>n;
adjList2 = vector< vector< pair<int, int> > >(n);
for(int i=0;i< n;i++)
{
int cnt;
cin>>cnt;
for(int j=0; j< cnt;j++)
{
int to, cost;
cin>>to>>cost;
adjList2[i].push_back( make_pair(to, cost));
}
}












Comments

Post a Comment

Popular posts from this blog

Leet code (Reverse Integer)

  7.   Reverse Integer Given a signed 32-bit integer  x , return  x  with its digits reversed . If reversing  x  causes the value to go outside the signed 32-bit integer range  [-2 31 , 2 31  - 1] , then return  0 . Assume the environment does not allow you to store 64-bit integers (signed or unsigned).   Example 1: Input: x = 123 Output: 321 Example 2: Input: x = -123 Output: -321 Example 3: Input: x = 120 Output: 21 Example 4: Input: x = 0 Output: 0   Constraints: -2 31  <= x <= 2 31  - 1 Solution class Solution { public:     int reverse(int x) {         int rev = 0;         while (x) {             int pop = x % 10;             x /= 10;             if (rev > INT_MAX/10 || (rev == INT_MAX / 10 && pop > 7)) return 0;             if (rev < INT_MIN/10 || (rev == INT_MIN / 10 && pop < -8)) return 0;             rev = rev * 10 + pop;         }         return rev;   }      };
Read more

Recursion(Part 1)

In this article I will speak about one of the main topics in computer science and I will write some examples to make you know what is that and how you should use it.   Recursion function it’s a function call itself. And this function is consisting of three parts (Base Case, some Logic,  Sub-problem). 1-Base case: this is a case when it happens this recursion function should stop and gave you the result.     2- some Logic: which happens when function called himself. 3- Sub-problem: in this part, the function calls itself by part of it but this calling should never go to infinity. Ex1: void SayHello(int num) {     if(num < 1)                                                                // Base Case                         return;       cout<<"Hello.\n";                  // Some logic       SayHello(num - 1);                // Sub-problem - never go to infinity } Ex2 int Fact(int n) {             if(n <= 1)                   
Read more