Пренеси графикон



Често питани у Аццентуре амазонка ЈП Морган мицрософт Зицус
основни Циптографија Графикон

Изјава о проблему

Проблем „Транспонуј граф“ наводи да ти је дат граф и треба да пронађеш транспоновање датог графикон.

Транспонујте: Транспоновање усмереног графа даје други граф са истим конфигурацијама ивица и чворова, али смер свих ивица је обрнут.

Пример

Пренеси граф

Врсте решења за проналажење транспонованог графа

Листа суседства

Приступ

Пређите листу суседности сваког чвора графикона. Рецимо, чвор је u, сада пређите преко сваког чвора на листи суседности u. Рецимо, чвор је v (тј. у -> в). У графикону за транспоновање додајте u на листу суседности v (постоји и ивица од в до у односно в -> у). Понављајте овај поступак за све чворове (и њихове одговарајуће листе суседности) на графикону док се не добије транспоновани граф.

Пренеси граф

код

Ц ++ програм за проналажење транспонованог графа
#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. Сложеност времена: Т (н) = О (В + Е), итеративни прелазак листе суседности. Јер смо управо прешли преко свих чворова на графикону.
  2. Сложеност простора: А (н) = О (В + Е), јер нам је потребна нова листа суседности за чување транспонованог графика.

В = број темена на графикону.

Е = број ивица на графикону.

Матрица суседства

Приступ

Транспозиција графа дефинисана са нкн матрица суседности (где н = број чворова) је да је транспозиција матрице.

Алгоритам

  1. Дефинишите графикон помоћу матрице суседности.
  2. Извршите транспоновање матрице суседности да бисте добили транспоновање датог графика.

Пренеси граф

код

Ц ++ програм за проналажење транспонованог графа
#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. Сложеност времена: Т (н) = О (В к В) И овде смо прешли све чворове за сваки чвор у графикону. Дакле, О (В * В), то је полиномно-временска сложеност.
  2. Сложеност простора: А (н) = О (1), не користи се додатни простор. Овде смо извршили задатак на месту, заменили смо вредности у почетној матрици. Тако се узима стални простор.

В = број темена на графикону.

Е = број ивица на графикону.