차례
문제 정책
"그래프 전치"문제는 그래프가 주어졌고 주어진 전치의 전치를 찾아야 함을 나타냅니다. 그래프.
Transpose : 방향성 그래프를 전치하면 동일한 에지 및 노드 구성을 가진 또 다른 그래프가 생성되지만 모든 에지의 방향이 반전되었습니다.
예
전치 그래프를 찾기위한 솔루션 유형
인접 목록
접근
그래프의 각 노드에 대한 인접 목록을 탐색합니다. 노드는 u, 이제 인접 목록의 각 노드를 순회합니다. u. 노드는 v (예 : 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->
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->
인접 목록을 사용한 그래프 전치의 복잡성 분석
- 시간 복잡성: T (n) = O (V + E), 인접 목록의 반복 순회. 그래프의 모든 노드를 방금 횡단했기 때문입니다.
- 공간 복잡성: A (n) = O (V + E), 전치 그래프를 저장하기위한 새로운 인접 목록이 필요하기 때문입니다.
V = 그래프의 꼭지점 수.
E = 그래프의 간선 수.
인접 매트릭스
접근
다음에 의해 정의 된 그래프의 전치 nxn 인접 행렬 (여기서 n = 노드 수) 행렬 전치입니다.
암호알고리즘
- 인접 행렬을 사용하여 그래프를 정의합니다.
- 주어진 그래프의 전치를 얻기 위해 인접 행렬의 전치를 수행합니다.
암호
전치 그래프를 찾는 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
인접 행렬을 사용한 전치 그래프의 복잡성 분석
- 시간 복잡성: T (n) = O (V x V) 여기에서도 그래프의 각 노드에 대한 모든 노드를 탐색했습니다. 따라서 O (V * V), 즉 다항식 시간 복잡도입니다.
- 공간 복잡성: A (n) = O (1), 추가 공간이 사용되지 않습니다. 여기서 우리는 내부 작업을 수행했으며 초기 행렬의 값을 대체했습니다. 따라서 일정한 공간이 사용됩니다.
V = 그래프의 꼭지점 수.
E = 그래프의 간선 수.
