Transpos ဇယား



မကြာခဏမေးတယ် Accenture အမေဇုံ JP Morgan Microsoft က ဆိ
အခြေခံပညာ လက်စွဲစာအုပ် သရုပ်ပြဇယား

ပြProbleနာဖော်ပြချက်

ပြTransနာက“ Transpose graph” ကသင့်ကို graph တစ်ခုပေးထားတယ်၊ သရုပ်ပြဇယား.

လွှဲပြောင်းရန်: တစ် ဦး ညွှန်ကြားဂရပ်၏ transpose တူညီအစွန်း & node ကို configurations အတူအခြားဂရပ်ထုတ်လုပ်ပေမယ့်အားလုံးအနား၏ညှနျကွားပြောင်းပြန်ပါပြီ။

နမူနာ

transpos ဂရပ်

transpose ဂရပ်ရှာဖွေတာများအတွက်ဖြေရှင်းချက်အမျိုးအစားများ

ကပ်လျက်စာရင်း

ချဉ်းကပ်နည်း

ဂရပ်၏တစ်ခုချင်းစီကို node တစ်ခု၏ travers ကပ်လျက်စာရင်း။ ပြောပါ, node ကိုဖြစ်ပါတယ် u, ယခု၏ကပ်လျက်စာရင်းထဲတွင်တစ်ခုချင်းစီကို node ကိုဖြတ်သန်း u။ ပြောပါ, node ကိုဖြစ်ပါတယ် v (ဆိုလိုသည်မှာ - - v) ။ အဆိုပါ transpose ဂရပ်များတွင်ထည့်ပါ u ၏ကပ်လျက်စာရင်းရန် v (v ထံမှ ဦး မှတည်ရှိခြင်းနှင့်အစွန်းရှိပါတယ် ဆိုလိုသည်မှာ v -> ဦး) အဆိုပါ transposed ဂရပ်ရယူထားပြီးသည်အထိဂရပ်၌ရှိသမျှသော node များ (& ၎င်းတို့၏သက်ဆိုင်ရာကပ်လျက်စာရင်း) အဘို့ဤလုပ်ငန်းစဉ်ကိုပြန်လုပ်ပါ။

transpos ဂရပ်

ကုဒ်

Transpose graph ကိုရှာရန် C ++ Program
#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->
Transpose ဂရပ်ကိုရှာရန် Java Program
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->

ကပ်လျက်စာရင်းကိုအသုံးပြု။ transpose ဂရပ်များအတွက်ရှုပ်ထွေးအားသုံးသပ်ခြင်း

  1. အချိန်ရှုပ်ထွေး: T က ()) = အို (V + E ကို), ကပ်လျက်စာရင်း၏ကြားမှာဖြတ်သန်း။ အဘယ်ကြောင့်ဆိုသော်ကျွန်ုပ်တို့သည်ဂရပ်အတွင်းရှိ node များအားလုံးကိုဖြတ်ကျော်သွားသောကြောင့်ဖြစ်သည်။
  2. အာကာသရှုပ်ထွေးမှုကျနော်တို့ transpose ဂရပ်သိုလှောင်အသစ်ကကပ်လျက်စာရင်းလိုအပ်ပါတယ်ဘာဖြစ်လို့လဲဆိုတော့: A (n) = အို (V + E ကို) ။

V ကို = ဂရပ်အတွက် vertices အရေအတွက်။

အီး = ဂရပ်အတွက်အနား၏အရေအတွက်။

ကပ်လျက် Matrix

ချဉ်းကပ်နည်း

အားဖြင့်သတ်မှတ်ထားသောဂရပ်၏ transpose nxn ကပ်လျက် matrix ကို (ဘယ်မှာ n = node များအရေအတွက်) က matrix ကို transpose ရဲ့ဖြစ်ပါတယ်။

algorithm

  1. ကပ်လျက် matrix ကိုအသုံးပြု။ ဂရပ် Define ။
  2. ပေးထားသောဂရပ်၏ transpose ရရှိရန်ကပ်လျက် matrix ကို၏ transpose လုပ်ဆောင်ပါ။

transpos ဂရပ်

ကုဒ်

Transpose graph ကိုရှာရန် C ++ Program
#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 
Transpose ဂရပ်ကိုရှာရန် Java Program
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

ကပ်လျက် matrix ကိုအသုံးပြု။ transpose ဂရပ်များအတွက်ရှုပ်ထွေးအားသုံးသပ်ခြင်း

  1. အချိန်ရှုပ်ထွေး: T ()) = အို (V ကို x ကို V ကို) ဤတွင်ကိုလည်းငါတို့ဂရပ်အတွက်တစ်ခုချင်းစီကို node ကိုအပေါငျးတို့သ node များမှတဆင့်ဖြတ်သန်းပါပြီ။ ထို့ကြောင့်အို (V * V) သည် polynomial အချိန်ရှုပ်ထွေးမှုဖြစ်သည်။
  2. အာကာသရှုပ်ထွေးမှု: တစ် ဦး က ()) = အို (1), အဘယ်သူမျှမပိုဆောင်းအာကာသကိုအသုံးပြုခဲ့သည်။ ဤတွင်ကျွန်ုပ်တို့သည် in-place တာဝန်တစ်ခုလုပ်ခဲ့ပြီးကန ဦး matrix တွင်တန်ဖိုးများကိုအစားထိုးခဲ့သည်။ ထို့ကြောင့်စဉ်ဆက်မပြတ်အာကာသကိုယူသည်။

V ကို = ဂရပ်အတွက် vertices အရေအတွက်။

အီး = ဂရပ်အတွက်အနား၏အရေအတွက်။