יבערשטעלן גראַפיק



אָפט געבעטן אין אַקסענטורע אַמאַזאָן דזשפּ מאָרגאַן מייקראָסאָפֿט זיקוס
יקערדיק סיפּטאָגראַפי גראַפיק

פּראָבלעם סטאַטעמענט

די פּראָבלעם "טראַנספּאָסע גראַפיק" זאגט אַז איר באַקומען אַ גראַפיק און איר דאַרפֿן צו געפֿינען די טראַנספּאָסיטע פון ​​די געגעבן גראַפיק.

יבערשטעלן: טראַנספּאָסע פון ​​אַ דירעקט דירעקט גראַפיק טראגט אן אנדער גראַפיק מיט זעלביקער קאַנפיגיעריישאַנז פון די ברעג און נאָדע, אָבער די ריכטונג פון אַלע עדזשאַז איז ריווערסט.

בייַשפּיל

יבערשטעלן גראַפיק

טייפּס פון סאַלושאַן פֿאַר דערגייונג טראַנספּאָרט גראַפיק

אַדדזשאַסענסי רשימה

צוגאַנג

דורך אַדזשאַסטאַנסי רשימה פון יעדער נאָדע פון ​​די גראַפיק. זאָגן, די נאָדע איז u, איצט דורך יעדער נאָדע אין די אַדזשאַסטאַנסי רשימה פון u. זאָגן, די נאָדע איז v (ד"ה ו -> וו). לייג אין די טראַנספּאָסע גראַפיק u צו אַדזשאַסטאַנסי רשימה פון v (עס יגזיסץ און ברעג פון V צו U ד"ה v -> u). איבערחזרן דעם פּראָצעס פֿאַר אַלע די נאָודז (און זייער ריספּעקטיוו אַדזשאַסטאַנסי רשימות) אין די גראַפיק ביז די טראַנספּאָוזד גראַפיק איז באקומען.

יבערשטעלן גראַפיק

קאָדעקס

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->
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. דורכפירן טראַנספּאָסיטיאָן פון די אַדזשאַסטאַנס מאַטריץ צו באַקומען טראַנספּאָוזד די געגעבן גראַפיק.

יבערשטעלן גראַפיק

קאָדעקס

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 
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) מיר האָבן אויך דורכגעקאָכט אַלע נאָודז פֿאַר יעדער נאָדע אין גראַפיק. אזוי אָ (V * V), דאָס איז פּאַלינאָומיאַל-צייַט קאַמפּלעקסיטי.
  2. ספעיס קאַמפּלעקסיטי: A (n) = O (1), קיין עקסטרע פּלאַץ געוויינט. דאָ מיר האָבן דורכגעקאָכט אַן אָרט אַרבעט, מיר האָבן ריפּלייסט די וואַלועס אין די ערשט מאַטריץ. אזוי קעסיידערדיק פּלאַץ איז גענומען.

V = נומער פון ווערטיסעס אין די גראַפיק.

E = נומער פון עדזשאַז אין די גראַפיק.