Transpose Graph



Көп суралган Accenture Amazon JP Morgan Microsoft Zycus
негизги Киптография график

Маселени билдирүү

"Transpose graph" көйгөйүндө сизге график берилгендиги жана берилгендин транспозициясын табуу керектиги айтылат график.

Transpose: Багытталган графиктин которулушу менен бир эле чекити жана түйүн конфигурациясы бар башка график пайда болот, бирок бардык четтеринин багыты өзгөртүлдү.

мисал

Transpose graph

Транспоздук графикти табуу үчүн чечим түрлөрү

Чектештик тизмеси

жакындоо

Графиктин ар бир түйүнүнүн жанаша өтүү тизмеси. Түйүн мындай деп айт u, эми тизмесинин ар бир түйүнүн басып өтүңүз u. Түйүн мындай деп айт v (б.а. u -> v). Транспоздук графикке кошуңуз u чектеш тизмеге v (бар жана чети v чейин u башкача айтканда, v -> u). Бул процессти графиктеги бардык түйүндөр үчүн (& алардын чектеш тизмелери) көчүрүлгөн график алынганга чейин кайталаңыз.

Transpose graph

коду

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->
Transpose графигин табуу үчүн Java программасы
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), анткени бизге транспозанын графигин сактоо үчүн жаңы чектөө тизмеси керек.

V = графиктеги чокулардын саны.

E = графиктеги кырлардын саны.

Чектештик матрицасы

жакындоо

Менен аныкталган графиктин транспозициясы nxn чектештик матрицасы (кайда n = түйүндөрдүн саны) бул матрицанын транспозициясы.

Algorithm

  1. Чектештик матрицасын колдонуп графикти аныктаңыз.
  2. Берилген графиктин транспозициясын алуу үчүн чектештик матрицасынын транспозасын аткарыңыз.

Transpose graph

коду

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 
Transpose графигин табуу үчүн Java программасы
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 = графиктеги кырлардын саны.