График дүрс шилжүүлэх



Байнга асуудаг Accenture Амазоны JP Morgan Microsoft- Зикус
үндсэн Киптографи График

Асуудлын мэдэгдэл

“Транспоз график” бодлогод танд график өгөгдсөн бөгөөд өгөгдсөн транспозыг олох хэрэгтэй гэсэн байна график.

Шилжүүлэх: Чиглүүлсэн графын шилжүүлэлт нь ижил ирмэг ба зангилааны тохиргоотой өөр график үүсгэдэг боловч бүх ирмэгүүдийн чиглэлийг буцааж оруулсан болно.

Жишээ нь

График дүрсийг шилжүүлэх

Транспос график олох шийдлийн төрлүүд

Хажуугийн жагсаалт

арга барил

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

График дүрсийг шилжүүлэх

код

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 = зангилааны тоо) энэ нь матриц шилжүүлэн суулгах явдал юм.

Алгоритм

  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 
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 = графикийн ирмэгийн тоо.