자료구조/알고리즘 공부 소감-6

座右铭(좌우명)

이겨야 한다.

딸깍!ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

今天我复习了图论(그래프 이론)的相关知识，大体上并不是很难，因为我已经学习了一次离散数学，经历了考试的折磨，所以说现在复习图论很容易，毕竟是已经有了一个系统的知识网络。

图论的大致内容包含如下内容:

基本术语(기초 용어)

顶点集，边集(정점,엣지/간선)
有向图，无向图
有环图，无环图
二分图，完全图，简单图
点导出子图，边导出子图
...

이상과 같은 용어들은 산동대학 이산수학 교재에서 뜨던 것이다.그런 것 같다. 这些概念非常简单易于理解，相比于抽象的群论来说。
이러한 용어들은 이 글에서 뵈시면 좋겠습니다:개발자 강세영의 글

핵심 기초 알고리즘

邻接链表，邻接矩阵
邻接多重表，十字链表
깊이 우선 순회,너비 우선 순회

四种图的存储方法实际上最常用的是邻接链表和邻接矩阵，十字链表和邻接多重表在算法实现中应用较少。

반면에, dfs와 bfs는 제일 밑바탕이라 할 수 있는 알고리즘이만큼 이후에 두 알고리즘 논리가 자주 쓰이는 편이다.
1.DFS 구현

/*씨플플 구현*/ 
vector<vector<int>>graph;
vector<bool>is_visited;
int n;
void dfs(){
    dfs(graph,1);
    cout<<"\n";
}
void dfs(int start){
	cout<<start<<' ';
    for (int i = 1;i <= n;i++){
    	if (graph[start][i])
          if (!is_visited[i]){
              is_visited[i] = true;
              dfs(i);
          }
    }
}

"파이썬 구현 생략"

2.BFS 구현

vector<vector<int>>graph;
vector<bool>is_visited;
int n;
void bfs(int start){
	cout<<start<<" ";
    std::queue<int>q;q.push(start);
    is_visited[start] = true;
    
    while (!q.empty()){
    	int temp = q.front();q.pop();
       if (!is_visited[temp]){
          cout<<temp<<" ";
          is_visited[temp] = true;
          q.push(temp);
       }
    }
    cout<<"\n";
}

"""생략해도 되니?"""

다익스트라 알고리즘,플로이드 알고리즘
유니온 파인드,크루스칼 알고리즘

사실 Dijkstra나 플로이드나 크루스칼은 기초 지식을 파악하면서 자연스럽게 파악할 수 있는 것으로 나타난다.그렇기 때문에 유니온 파인드가 보다 중요하다는 부분이다.

유니온 파인드 씨플플 구현

#include <vector>
#include <algorithm>

class UnionFind{
	private:
    std::vector<int>ranks;	// 높이 또한 크기 배열 
    std::vector<int>parent;
    int n;
    
    public:
    UnionFind(int nn):n(nn){
    	ranks.assign(n+1,0);
        parent.resize(n+1);
        for (int i = 1;i <= n;i++){
			parent[i] = i;
		}
    }
    ~UnionFind(){}
    
    // 부모 노드 탐색(경로 압축)
    int find(int x){
    	if (x != parent[x]) parent[x] = find(parent[x]);
        return parent[x];
    }
    
    // 두 트리 합병
    void union_(int x,int y){
    	int px = find(x),py = find(y);
        if (px == py) return ;
        int rx = ranks[px],ry = ranks[py];
        if (rx > ry){
        	parent[py] = px;
        }else if (rx < ry){
        	parent[px] = py;
        }else{
        	parent[py] = px;
            ranks[px]++;
        }
    }
};

고급 알고리즘

拓扑排序(위상 정렬)
二分图判定(이분 그래프 판단)
...
계속 추가 중

마지막

따라서 그래프는 생각보다 쉽지 않은 부분이 아닙니다. 교재에 있는 추상적인 개념을 잘 이해하자 무슨 문제도 잘 풀 수 있게 될 겁니다.그러므로 다음 주도 최선을 다해 나가겠습니다.