5.グラフ(2)
56626 ワード
グラフ＃グラフ＃
グラフィック表示
幹線リスト
隣接行列
これは2 Dグラフィック表現ですが、この方法はあまり使われていません.
りんせつひょう
その他の使用方法
V個の頂点数、E本の幹線数を有する図形については、図形情報をV個の接続リストとして保存する
1.Union Find
はんぱつしゅうごう
2つの演算からなる.
1.Find:xが含む演算を検索する
2.Union:xとyの集合を含む演算のマージ
使用ツリーを実装します.
親[i]=iの親は保存されています
最初は親がいなくて、自分が親です.
Union(1,2)は後ろを前に付けます.
しかし、このように勝手に貼ってはいけません.
元の4-5の関係をユニオン(2,5)で5万2に加算すると、本来は4つが1つの集合になるはずだったが、3つだけが1つの集合になる.
だからfind演算を利用しています.Find演算はルートを探す演算です.
実際の結果もユニオン(1,4)の結果です.시간 복잡도 : O(n)
int Find(int x){
if(x==parent[x]) return x;
else return Find(parent[x]);
}
시간 복잡도 : O(n)
int Union(int x,int y){
x=Find(x);
y=Find(y);
parent[y]=x;
}
しかし、これは実はO(3 N)なので効率的ではありません.パス圧縮を使用しています
Union Find:圧縮パス
私たちにとって重要なのは、親子関係ではなくルートです.したがって,出会ったすべてのノードの親をルートノードとする.
int Find(int x){
if(x==parent[x]) return x;
else {
int y = Find(parent[x]);
parent[x]=y;
return y;
}
}
Union Find:Rankによる実装
ユニオンを実施する場合は、ツリーの順位を基準にすることができます.
ツリーの順位は高さと同じですが、パス圧縮を使用すると高さとは異なる値になる場合があります.そのため、高さの代わりに「順位」を使う.
ランクを高ランクの子供に変える.int Union(int x,int y){
x=Find(x);
y=Find(y);
if(x==y) return;
if(rank[x]<rank[y]) swap(x,y);
parent[y]=x;
if(rank[x]==rank[y]){
rank[x]=rank[y]+1;
}
}
全ての演算の時間複雑度O(a(N))
集合を表す
質問する
1717集合の表現
Unionシードタイプ:頂点間の接続と接続をチェックするタイプ(コレクションかどうかを確認)
同父異母int par[100005];
int find(int a){
if(par[a]==a) return a;
return par[a] = find(par[a]);
}
void merge(int a,int b){
int p_a = find(a);
int p_b = find(b);
par[p_b]=p_a;
}
int main(void){
int n,m,x,y,z;
scanf("%d %d",&n,&m);
for(int i = 1;i<=n;++i){
par[i]=i;
}
for(int i = 0;i<m;++i){
scanf("%d %d %d",&x,&y,&z);
}
}
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
int ans, i, j,n,m;
int parent[1000001];
int rank_t[1000001];
int Find(int x) {
if (parent[x] == x) {
return x;
}
else {
return parent[x] = Find(parent[x]);
}
}
void Union(int x, int y) {
/* 부모를 찾는 부분 */
x = Find(x);
y = Find(y);
/* 같은 부모이면 스킵 */
if (x == y) return;
/* 랭크가 보다 높은 게 부모가 돰 : 랭크는 연결된 부모의 수를 의미*/
if (rank_t[x] < rank_t[y]) swap(x, y);
parent[y] = x;
/* 부모간 연결, 같은 자식 부모수이면 열결되는쪽 랭크를 증가 */
if (rank_t[x] == rank_t[y]) {
rank_t[x] = rank_t[y] + 1;
}
}
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 0; i <= n; i++) {
parent[i] = i;
rank_t[i] = 0;
}
while (m--) {
int w, x, y;
cin >> w >> x >> y;
if (w == 0) {
Union(x, y);
}
else {
x = Find(x);
y = Find(y);
if (x == y) {
cout << "YES" << '\n';
}
else {
cout << "NO" << '\n';
}
}
}
}
2606ウイルス
2.最小生成ツリー（MST）
生成ツリーの重み付けと最小のツリーを表します.すべての頂点を含むが重みの低い1本の幹線のみを使用して、すべての頂点を接続します.
1)幹線リストを入力します.
2)料金順に幹線明細書を並べ替える.
3) while(true){
幹線リスト回り
2つのifを接続
}
4)接続する幹線数が頂点数-1の場合に中断する.
ツリー幹線の数:頂点の数-1
グラフを木にすることを生成木と言います.
≪ツリーの生成｜Generate Tree｜oem_src≫:図形から幹線の一部を選択して作成したツリー
≪最小生成ツリー｜Minimum Generation Tree｜oem_src≫:ツリーで選択した幹線の重みの合計と最小のツリーを生成します.
プリムとクルーズアルゴリズムが存在し,ループを作成しないことが重要である.
クリーム
生成生成ツリーを生成する方法は、任意の頂点から開始し、接続された幹線で最小値を選択します.
頂点を選択するには、すべての接続された幹線から表示する必要があります.
O(VxE)、Eの最値はV^2なのでO(V^3)です.
質問する
1922ネットワーク接続
この問題を解決するために,優先キューを利用する方法がある.
すべての幹線は3種類に分けられる.選択された頂点と選択されていない頂点
したがって、1つを選択すると、すべての関係が線-線X、線-線形式になります.幹線に関する情報を優先順位キューに入れると、logEのみが幹線を選択できます.
従って,最終時間複雑度はO(ElogE)であった.
優先順位キューには(to,cost)のみが含まれます.fromが選択されているので意味がなく、別の配列も作成されます.#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
int ans, i, j,n,m;
struct Edge {
int to;
int cost;
bool operator < (const Edge& other) const {
return cost > other.cost;
}
};
vector<Edge> a[1001];
bool c[1001];
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
cin >> m;
for (i = 0; i < m; ++i) {
int from, to, cost;
cin >> from>>to >> cost;
a[from].push_back(Edge({ to, cost }));
a[to].push_back(Edge({ from, cost }));
}
priority_queue<Edge> q;
for (Edge ee : a[1]) {
q.push(ee);
}
c[1] = true;
while (!q.empty()) {
Edge num = q.top();
q.pop();
if (c[num.to]) continue;
c[num.to] = true;
ans += num.cost;
for (Edge ee : a[num.to]) {
q.push(ee);
}
}
cout << ans << '\n';
}
この質問に答えると,構造体内部にオファーを設定できることがわかる.これにより、優先順位キューがオペレータによってソートされ、非常に便利に決定される.
クルースカ
3. DAG (Directed Acyclic Graph)
無循環方向図
この図を用いて複数のアルゴリズムが存在する.
位相位置合わせ
BFS>DFS
図の幹線u->vは,uがvより先にある場合に頂点順序を探すアルゴリズムを表し,この条件に違反しない方法を研究する.
上のグラフも[1,2,3,4,5,6,7,8,9]のようにすることができます.例えば、服を着る順番がどのように正しい順番なのかを知る方法があります.
位相整列アルゴリズムはBFSを適用して実現できる.
上記の関係がある場合、サブノードを1つずつ除去すると、vのin-dereは0になります.これは、このノードも一緒に削除できることを意味します.
位相整列では,最も重要なのは進入度が0の瞬間である.
BFS形式でノードをキューに入れ続け、マイナス記号を繰り返し、in degreeが0でない場合はキューを再挿入します.
ind[i]=iのin-dereを保存して続行します.
O(E) -> O(N+E)
必要成分3要素
1.優先キュー
2.度数を計算する変数
3.隣接リスト->BFSを使用してすべての接続を挿入
DFS形式で解くこともできます.
図のすべての幹線を反転してDFSを実行し、頂点がスタックから抜ける順序を記録すると、位相位置合わせの順序と同じになります.
例えば、上の図に示すように、DAGが8から始まる場合、1まで上がることができる.次に、位相を2、4、3、5、7、8、6、9の順に並べます.
質問する
2252キュー
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
int ans, i, j, n, m;
vector<int> a[100001];
int ind[100001];
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (i = 0; i < m; ++i) {
int from, to;
cin >> from >> to;
a[from].push_back(to);
++ind[to];
}
queue<int> q;
for (i = 1; i <= n; ++i) {
if (ind[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int num = q.front();
q.pop();
for (int i : a[num]) {
if(ind[i]>0) --ind[i];
if (ind[i] == 0) {
q.push(i);
}
}
cout << num << ' ';
}
return 0;
}
1766題集
行列との違いは가능하면 쉬운 문제부터 풀어야 한다です.問題番号は難易度順です.
시간 복잡도 : O(n)
int Find(int x){
if(x==parent[x]) return x;
else return Find(parent[x]);
}
시간 복잡도 : O(n)
int Union(int x,int y){
x=Find(x);
y=Find(y);
parent[y]=x;
}int Find(int x){
if(x==parent[x]) return x;
else {
int y = Find(parent[x]);
parent[x]=y;
return y;
}
}int Union(int x,int y){
x=Find(x);
y=Find(y);
if(x==y) return;
if(rank[x]<rank[y]) swap(x,y);
parent[y]=x;
if(rank[x]==rank[y]){
rank[x]=rank[y]+1;
}
}int par[100005];
int find(int a){
if(par[a]==a) return a;
return par[a] = find(par[a]);
}
void merge(int a,int b){
int p_a = find(a);
int p_b = find(b);
par[p_b]=p_a;
}
int main(void){
int n,m,x,y,z;
scanf("%d %d",&n,&m);
for(int i = 1;i<=n;++i){
par[i]=i;
}
for(int i = 0;i<m;++i){
scanf("%d %d %d",&x,&y,&z);
}
}#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
int ans, i, j,n,m;
int parent[1000001];
int rank_t[1000001];
int Find(int x) {
if (parent[x] == x) {
return x;
}
else {
return parent[x] = Find(parent[x]);
}
}
void Union(int x, int y) {
/* 부모를 찾는 부분 */
x = Find(x);
y = Find(y);
/* 같은 부모이면 스킵 */
if (x == y) return;
/* 랭크가 보다 높은 게 부모가 돰 : 랭크는 연결된 부모의 수를 의미*/
if (rank_t[x] < rank_t[y]) swap(x, y);
parent[y] = x;
/* 부모간 연결, 같은 자식 부모수이면 열결되는쪽 랭크를 증가 */
if (rank_t[x] == rank_t[y]) {
rank_t[x] = rank_t[y] + 1;
}
}
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 0; i <= n; i++) {
parent[i] = i;
rank_t[i] = 0;
}
while (m--) {
int w, x, y;
cin >> w >> x >> y;
if (w == 0) {
Union(x, y);
}
else {
x = Find(x);
y = Find(y);
if (x == y) {
cout << "YES" << '\n';
}
else {
cout << "NO" << '\n';
}
}
}
}生成ツリーの重み付けと最小のツリーを表します.すべての頂点を含むが重みの低い1本の幹線のみを使用して、すべての頂点を接続します.
1)幹線リストを入力します.
2)料金順に幹線明細書を並べ替える.
3) while(true){
幹線リスト回り
2つのifを接続
}
4)接続する幹線数が頂点数-1の場合に中断する.
ツリー幹線の数:頂点の数-1
グラフを木にすることを生成木と言います.
≪ツリーの生成｜Generate Tree｜oem_src≫:図形から幹線の一部を選択して作成したツリー
≪最小生成ツリー｜Minimum Generation Tree｜oem_src≫:ツリーで選択した幹線の重みの合計と最小のツリーを生成します.
プリムとクルーズアルゴリズムが存在し,ループを作成しないことが重要である.
クリーム
生成生成ツリーを生成する方法は、任意の頂点から開始し、接続された幹線で最小値を選択します.
頂点を選択するには、すべての接続された幹線から表示する必要があります.
O(VxE)、Eの最値はV^2なのでO(V^3)です.
質問する
1922ネットワーク接続
この問題を解決するために,優先キューを利用する方法がある.
すべての幹線は3種類に分けられる.選択された頂点と選択されていない頂点
したがって、1つを選択すると、すべての関係が線-線X、線-線形式になります.幹線に関する情報を優先順位キューに入れると、logEのみが幹線を選択できます.
従って,最終時間複雑度はO(ElogE)であった.
優先順位キューには(to,cost)のみが含まれます.fromが選択されているので意味がなく、別の配列も作成されます.
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
int ans, i, j,n,m;
struct Edge {
int to;
int cost;
bool operator < (const Edge& other) const {
return cost > other.cost;
}
};
vector<Edge> a[1001];
bool c[1001];
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
cin >> m;
for (i = 0; i < m; ++i) {
int from, to, cost;
cin >> from>>to >> cost;
a[from].push_back(Edge({ to, cost }));
a[to].push_back(Edge({ from, cost }));
}
priority_queue<Edge> q;
for (Edge ee : a[1]) {
q.push(ee);
}
c[1] = true;
while (!q.empty()) {
Edge num = q.top();
q.pop();
if (c[num.to]) continue;
c[num.to] = true;
ans += num.cost;
for (Edge ee : a[num.to]) {
q.push(ee);
}
}
cout << ans << '\n';
}クルースカ
3. DAG (Directed Acyclic Graph)
無循環方向図
この図を用いて複数のアルゴリズムが存在する.
位相位置合わせ
BFS>DFS
図の幹線u->vは,uがvより先にある場合に頂点順序を探すアルゴリズムを表し,この条件に違反しない方法を研究する.
上のグラフも[1,2,3,4,5,6,7,8,9]のようにすることができます.例えば、服を着る順番がどのように正しい順番なのかを知る方法があります.
位相整列アルゴリズムはBFSを適用して実現できる.
上記の関係がある場合、サブノードを1つずつ除去すると、vのin-dereは0になります.これは、このノードも一緒に削除できることを意味します.
位相整列では,最も重要なのは進入度が0の瞬間である.
BFS形式でノードをキューに入れ続け、マイナス記号を繰り返し、in degreeが0でない場合はキューを再挿入します.
ind[i]=iのin-dereを保存して続行します.
O(E) -> O(N+E)
必要成分3要素
1.優先キュー
2.度数を計算する変数
3.隣接リスト->BFSを使用してすべての接続を挿入
DFS形式で解くこともできます.
図のすべての幹線を反転してDFSを実行し、頂点がスタックから抜ける順序を記録すると、位相位置合わせの順序と同じになります.
例えば、上の図に示すように、DAGが8から始まる場合、1まで上がることができる.次に、位相を2、4、3、5、7、8、6、9の順に並べます.
質問する
2252キュー
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
int ans, i, j, n, m;
vector<int> a[100001];
int ind[100001];
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (i = 0; i < m; ++i) {
int from, to;
cin >> from >> to;
a[from].push_back(to);
++ind[to];
}
queue<int> q;
for (i = 1; i <= n; ++i) {
if (ind[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int num = q.front();
q.pop();
for (int i : a[num]) {
if(ind[i]>0) --ind[i];
if (ind[i] == 0) {
q.push(i);
}
}
cout << num << ' ';
}
return 0;
}
1766題集
行列との違いは가능하면 쉬운 문제부터 풀어야 한다です.問題番号は難易度順です.
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
int ans, i, j, n, m;
vector<int> a[100001];
int ind[100001];
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (i = 0; i < m; ++i) {
int from, to;
cin >> from >> to;
a[from].push_back(to);
++ind[to];
}
queue<int> q;
for (i = 1; i <= n; ++i) {
if (ind[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int num = q.front();
q.pop();
for (int i : a[num]) {
if(ind[i]>0) --ind[i];
if (ind[i] == 0) {
q.push(i);
}
}
cout << num << ' ';
}
return 0;
}
だから前のグラフは上と同じなので、先に解くことはできません.これらの問題を解決するためにmin-heapを使って問題を解くことができます.
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
int ans, i, j, n, m;
vector<int> a[100001];
int ind[100001];
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (i = 0; i < m; ++i) {
int from, to;
cin >> from >> to;
a[from].push_back(to);
++ind[to];
}
priority_queue<int> q;
for (i = 1; i <= n; ++i) {
if (ind[i] == 0) {
q.push(-i);
}
}
while (!q.empty()) {
int num = -q.top();
q.pop();
for (int i : a[num]) {
if(ind[i]>0) --ind[i];
if (ind[i] == 0) {
q.push(-i);
}
}
cout << num << ' ';
}
return 0;
}Reference
この問題について(5.グラフ(2)), 我々は、より多くの情報をここで見つけました https://velog.io/@tonyhan18/5.-그래프2テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol