เปลี่ยนกราฟ  



ถามบ่อยใน แอคเซนเจอร์ อเมซอน มอร์แกน JP ไมโครซอฟท์ ไซคัส
ขั้นพื้นฐาน ไซปโตกราฟี กราฟ

คำชี้แจงปัญหา  

ปัญหา“ กราฟเปลี่ยนภาพ” ระบุว่าคุณได้รับกราฟและคุณต้องหาทรานสโพสของสิ่งที่กำหนด กราฟ.

ไขว้: การเปลี่ยนกราฟที่กำหนดทิศทางจะสร้างกราฟอื่นที่มีการกำหนดค่าขอบและโหนดเดียวกัน แต่ทิศทางของขอบทั้งหมดกลับกัน

ตัวอย่าง  

เปลี่ยนกราฟหมุดหมุด

ประเภทของคำตอบสำหรับการค้นหากราฟทรานสโพส  

รายการ Adjacency

เข้าใกล้

Traverse adjacency list ของแต่ละโหนดของกราฟ สมมติว่าโหนดคือ u, ตอนนี้สำรวจแต่ละโหนดในรายการ adjacency ของ u. สมมติว่าโหนดคือ v (เช่น u -> v) ในกราฟทรานสโพสเพิ่ม u ไปยังรายการ adjacency ของ v (มีอยู่และขอบจาก v ถึง u เช่น v -> u) ทำซ้ำขั้นตอนนี้สำหรับโหนดทั้งหมด (& รายการ adjacency ตามลำดับ) ในกราฟจนกว่าจะได้รับกราฟที่เปลี่ยนทิศทาง

เปลี่ยนกราฟหมุดหมุด

รหัส

โปรแกรม C ++ เพื่อค้นหากราฟ Transpose
#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 เพื่อค้นหากราฟ Transpose
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->

การวิเคราะห์ความซับซ้อนสำหรับกราฟทรานสโพสต์โดยใช้รายการ adjacency

  1. ความซับซ้อนของเวลา: T (n) = O (V + E), การข้ามซ้ำของรายการ adjacency เนื่องจากเราได้ข้ามผ่านโหนดทั้งหมดในกราฟ
  2. ความซับซ้อนของอวกาศ: A (n) = O (V + E) เนื่องจากเราต้องการรายการ adjacency ใหม่สำหรับจัดเก็บกราฟทรานสโพส
ดูสิ่งนี้ด้วย
ให้อาร์เรย์ของคู่ค้นหาคู่สมมาตรทั้งหมดในนั้น

V = จำนวนจุดยอดในกราฟ

E = จำนวนขอบในกราฟ

เมทริกซ์ Adjacency

เข้าใกล้

ทรานสโพสของกราฟที่กำหนดโดย nxn เมทริกซ์ adjacency (โดยที่ n = จำนวนโหนด) คือเมทริกซ์ทรานสโพส

ขั้นตอนวิธี

  1. กำหนดกราฟโดยใช้เมทริกซ์ adjacency
  2. ดำเนินการทรานสโพสของเมทริกซ์ adjacency เพื่อให้ได้ทรานสโพสของกราฟที่กำหนด

เปลี่ยนกราฟหมุด

รหัส

โปรแกรม C ++ เพื่อค้นหากราฟ Transpose
#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 เพื่อค้นหากราฟ Transpose
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

การวิเคราะห์ความซับซ้อนสำหรับกราฟทรานสโพสต์โดยใช้เมทริกซ์ adjacency

  1. ความซับซ้อนของเวลา: T (n) = O (V x V) ที่นี่เราได้ข้ามผ่านโหนดทั้งหมดสำหรับแต่ละโหนดในกราฟ ดังนั้น O (V * V) นั่นคือความซับซ้อนของเวลาพหุนาม
  2. ความซับซ้อนของอวกาศ: A (n) = O (1) ไม่ใช้ช่องว่างเพิ่มเติม ที่นี่เราทำงานแทนเราได้แทนที่ค่าในเมทริกซ์เริ่มต้น ดังนั้นจึงใช้พื้นที่คงที่
ดูสิ่งนี้ด้วย
โซลูชัน Leetcode Triangle II ของ Pascal

V = จำนวนจุดยอดในกราฟ

E = จำนวนขอบในกราฟ