ٹرانسپوز گراف



اکثر پوچھا جاتا ہے ایکسینچر ایمیزون جے پی مورگن مائیکروسافٹ زائکس
بنیادی سائپٹوگرافی گراف

مسئلہ یہ بیان

مسئلہ "ٹرانسپوز گراف" میں بتایا گیا ہے کہ آپ کو گراف دیا گیا ہے اور آپ کو دیئے گئے ٹرانسپوس کو تلاش کرنے کی ضرورت ہے گراف.

ٹرانسپوز: ہدایت شدہ گراف کی ٹرانسپوز اسی کنارے اور نوڈ کنفگریشنوں کے ساتھ ایک اور گراف تیار کرتا ہے لیکن تمام کناروں کی سمت الٹ کردی گئی ہے۔

مثال کے طور پر

گراف منتقل کریں

ٹرانسپوس گراف تلاش کرنے کے لئے حل کی اقسام

ملحقہ فہرست

نقطہ نظر

گراف کے ہر نوڈ کی ٹروراس ملحقہ فہرست۔ کہو ، نوڈ ہے u, اب کے ساتھ ملحقہ فہرست میں ہر نوڈ کو عبور کریں u. کہو ، نوڈ ہے v (جیسے آپ -> وی) ٹرانسپوز گراف میں ، شامل کریں u کی آس پاس کی فہرست میں v (وہاں موجود ہے اور وی سے یو تک یعنی v -> u)۔ اس عمل کو گراف میں تمام نوڈس (اور ان کی متعلقہ لسٹ لسٹس) کے ل Rep دہرائیں جب تک ٹرانسپوسڈ گراف حاصل نہ ہوجائے۔

گراف منتقل کریں

ضابطے

Transpose گراف کو تلاش کرنے کے لئے C ++ پروگرام
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// Add Edge from node u to v
void addEdge(vector <int> graph[], int u, int v)
{
    graph[u].push_back(v);
}

int main()
{
    // Construct the Given graph
    int n = 7;
    vector <int> graph[n];
    vector<pair<int,int>> edges = {{0,1},{0,2},{3,2},{3,4},{4,5},{6,5},{6,0}};
    
    for(auto e : edges)
    addEdge(graph,e.first,e.second);
    
    // Print Adjacency list of given Graph
    cout<<"The Adjacency List of Given Graph "<<endl;
    for(int i=0;i<n;i++)
    {
        cout<<i<<"->";
        for(auto node : graph[i])
        cout<<node<<" ";
        
        cout<<endl;
    }
    
    // Obtain transpose of the given graph
    vector <int> transpose[n];
    for(int i=0;i<n;i++)
    {
        for(auto node : graph[i])
        addEdge(transpose,node,i);
    }
    
    // Print Adjacency list of the Transpose
    cout<<endl<<"The Adjacency List of Transpose Graph "<<endl;
    for(int i=0;i<n;i++)
    {
        cout<<i<<"->";
        for(auto node : transpose[i])
        cout<<node<<" ";
        
        cout<<endl;
    }
    
    return 0;
}
The Adjacency List of Given Graph 
0->1 2 
1->
2->
3->2 4 
4->5 
5->
6->5 0 

The Adjacency List of Transpose Graph 
0->6 
1->0 
2->0 3 
3->
4->3 
5->4 6 
6->
ٹرانسپوز گراف تلاش کرنے کے لئے جاوا پروگرام
import java.util.*;
import java.io.*;

class TutorialCup
{
    // Add Edge from node u to v
    static void addEdge(ArrayList<ArrayList<Integer>> graph, int u, int v)
    {
        graph.get(u).add(v);
    }
    
    public static void main (String[] args)
    {
        // Construct the Given graph
        int n = 7;
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        
        for(int i=0;i<n;i++)
        graph.add(new ArrayList<Integer>());
        
        int [][] edges = {{0,1},{0,2},{3,2},{3,4},{4,5},{6,5},{6,0}};
        
        for(int i=0;i<edges.length;i++)
        addEdge(graph,edges[i][0],edges[i][1]);
        
        // Print Adjacency list of given Graph
        System.out.println("The Adjacency List of Given Graph ");
        for(int i=0;i<n;i++)
        {
            System.out.print(i+"->");
            
            Iterator itr = graph.get(i).iterator();
            
            while(itr.hasNext())
            {
                int node = (Integer)itr.next();
                System.out.print(node+" ");
            }
            
            System.out.println();
        }
        
        // Obtain transpose of the given graph
        ArrayList<ArrayList<Integer>> transpose = new ArrayList<>();
        
        for(int i=0;i<n;i++)
        transpose.add(new ArrayList<Integer>());
        
        for(int i=0;i<n;i++)
        {
            Iterator itr = graph.get(i).iterator();
            
            while(itr.hasNext())
            {
                int node = (Integer)itr.next();
                addEdge(transpose,node,i);
            }
        }
        
        // Print Adjacency list of the Transpose
        System.out.println("\nThe Adjacency List of Transpose Graph ");
        for(int i=0;i<n;i++)
        {
            System.out.print(i+"->");
            
            Iterator itr = transpose.get(i).iterator();
            
            while(itr.hasNext())
            {
                int node = (Integer)itr.next();
                System.out.print(node+" ");
            }
            
            System.out.println();
        }
        
    }
}
The Adjacency List of Given Graph 
0->1 2 
1->
2->
3->2 4 
4->5 
5->
6->5 0 

The Adjacency List of Transpose Graph 
0->6 
1->0 
2->0 3 
3->
4->3 
5->4 6 
6->

ملحقہ فہرست کا استعمال کرتے ہوئے ٹرانسپوس گراف کیلئے پیچیدگی کا تجزیہ

  1. وقت کی پیچیدگی: T (n) = O (V + E)، ملحقہ فہرست کی تکرار ٹرورسال۔ کیونکہ ہم نے گراف میں موجود تمام نوڈس کے اوپر ہی عبور کرلیا ہے۔
  2. خلائی پیچیدگی: A (n) = O (V + E) ، کیونکہ ٹرانسپوز گراف کو اسٹور کرنے کے ل for ہمیں نئی ​​ملحقہ فہرست کی ضرورت ہے۔

V = گراف میں عمودی کی تعداد۔

E = گراف میں کناروں کی تعداد۔

ایڈجینسسی میٹرکس

نقطہ نظر

بیان کردہ گراف کی ٹرانسپوز nxn ملحق میٹرکس (جہاں n = نوڈس کی تعداد) یہ میٹرکس ٹرانسپوز ہے۔

الگورتھم

  1. ملحق میٹرکس کا استعمال کرتے ہوئے گراف کی وضاحت کریں۔
  2. دیئے گراف کو ٹرانسپوس حاصل کرنے کے لئے ملحق میٹرکس کے ٹرانسپوس انجام دیں۔

گراف منتقل کریں

ضابطے

Transpose گراف کو تلاش کرنے کے لئے C ++ پروگرام
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main()
{
    // Define The Adjacency Matrix
    vector<vector<int>> graph = {{0,1,1,0,0,0,0},
                                {0,0,0,0,0,0,0},
                                {0,0,0,0,0,0,0},
                                {0,0,1,0,1,0,0},
                                {0,0,0,0,0,1,0},
                                {0,0,0,0,0,0,0},
                                {1,0,0,0,0,1,0}};
    
    cout<<"Adjacency Matrix of Given Graph."<<endl;
    
    for(auto node : graph)
    {
        for(auto neighbor : node)
        cout<<neighbor<<" ";
        
        cout<<endl;
    }
    
    // Perform Matrix Transpose
    for(int i=0;i<graph.size();i++)
    {
        for(int j=i+1;j<graph[0].size();j++)
        swap(graph[i][j],graph[j][i]);
    }
    
    // Print the Matrix Transpose
    cout<<"\nAdjacency Matrix of Transpose Graph."<<endl;
    for(auto node : graph)
    {
        for(auto neighbor : node)
        cout<<neighbor<<" ";
        
        cout<<endl;
    }
    
    return 0;
}
Adjacency Matrix of Given Graph.
0 1 1 0 0 0 0 
0 0 0 0 0 0 0 
0 0 0 0 0 0 0 
0 0 1 0 1 0 0 
0 0 0 0 0 1 0 
0 0 0 0 0 0 0 
1 0 0 0 0 1 0 

Adjacency Matrix of Transpose Graph.
0 0 0 0 0 0 1 
1 0 0 0 0 0 0 
1 0 0 1 0 0 0 
0 0 0 0 0 0 0 
0 0 0 1 0 0 0 
0 0 0 0 1 0 1 
0 0 0 0 0 0 0 
ٹرانسپوز گراف تلاش کرنے کے لئے جاوا پروگرام
import java.util.*;
import java.io.*;

class TutorialCup
{
    public static void main (String[] args)
    {
        // Define The Adjacency Matrix
        int [][] graph =            {{0,1,1,0,0,0,0},
                                    {0,0,0,0,0,0,0},
                                    {0,0,0,0,0,0,0},
                                    {0,0,1,0,1,0,0},
                                    {0,0,0,0,0,1,0},
                                    {0,0,0,0,0,0,0},
                                    {1,0,0,0,0,1,0}};
        
        System.out.println("Adjacency Matrix of Given Graph.");
        
        for(int i=0;i<graph.length;i++)
        {
            for(int j=0;j<graph[0].length;j++)
            System.out.print(graph[i][j]+" ");
            
            System.out.println();
        }
        
        // Perform Matrix Transpose
        for(int i=0;i<graph.length;i++)
        {
            for(int j=i+1;j<graph[0].length;j++)
            {
                int temp = graph[i][j];
                graph[i][j] = graph[j][i];
                graph[j][i] = temp;
            }
        }
        
        // Print the Matrix Transpose
        System.out.println("\nAdjacency Matrix of Transpose Graph.");
        for(int i=0;i<graph.length;i++)
        {
            for(int j=0;j<graph[0].length;j++)
            System.out.print(graph[i][j]+" ");
            
            System.out.println();
        }
    }
}
Adjacency Matrix of Given Graph.
0 1 1 0 0 0 0 
0 0 0 0 0 0 0 
0 0 0 0 0 0 0 
0 0 1 0 1 0 0 
0 0 0 0 0 1 0 
0 0 0 0 0 0 0 
1 0 0 0 0 1 0 

Adjacency Matrix of Transpose Graph.
0 0 0 0 0 0 1 
1 0 0 0 0 0 0 
1 0 0 1 0 0 0 
0 0 0 0 0 0 0 
0 0 0 1 0 0 0 
0 0 0 0 1 0 1 
0 0 0 0 0 0 0

ملحق میٹرکس کا استعمال کرتے ہوئے ٹرانسپوس گراف کیلئے پیچیدگی کا تجزیہ

  1. وقت کی پیچیدگی: T (n) = O (V x V) ہم بھی گراف میں ہر نوڈ کے لئے تمام نوڈس سے گزر چکے ہیں۔ اس طرح O (V * V) ، یہ کثیر الوقت پیچیدگی ہے۔
  2. خلائی پیچیدگی: A (n) = O (1)، کوئی اضافی جگہ استعمال نہیں کی گئی۔ یہاں ہم نے جگہ جگہ کام کیا ، ہم نے ابتدائی میٹرکس میں اقدار کی جگہ لی ہے۔ اس طرح مستقل جگہ لی جاتی ہے۔

V = گراف میں عمودی کی تعداد۔

E = گراف میں کناروں کی تعداد۔