0

@jakeseo_me

대전에 있는 (주) 아이와즈에서 풀스택 웹개발자로 일하고 있는 서진규입니다. JS는 Jake Seo의 Abbreviation이며 가장 관심이 많은 분야입니다.

2019년 3월 12일

SERIES

16/18

- in case of this graph, it has 6 vertices and 8 edges
- it doesn't have direction so it is undirected graph
- vertices : {1, 2, 3, 4, 5, 6}
- edges : {(1, 2), (1, 5), (2, 5), (2, 3), (3, 4), (2, 4), (4, 5), (4, 6)}
- vertices are usually named just 1 to the amount of vertices
- so edges are important
- we only save the amount of vertices by using variable.

- if we just want to express graph, it is the same to just save the all of edges.
- edge can save effectively
- we can figure out the graph's representation

- edge can save effectively

- When you say the number of vertices is V
- We use 2 dimension array which has size of V * V

- A[i][j] = 1 (when there is edge connecting i to j), 0 (no edge)
- in case of graph at the top, it can be expressed like this
`/ 1 2 3 4 5 6 1 0 0 0 0 1 0 2 1 0 1 1 1 0 3 0 1 0 1 0 0 4 0 1 1 0 1 1 5 1 1 0 1 0 0 6 0 0 0 1 0 0`

- These numbers are symmetrical in relation of the diagonal
- it has dis-advantage
- it saves useless edges
- even if it doesn't have any edge, it saves 0 in that space

- it saves useless edges
- usually, V^2 >= E
- to solve easy problems, it is good way to express graph data structure.
`#include <cstdio> #include <vector> int a[10][10]; int main() { int n, m; scanf("%d %d", &n, &m); for (int i=0; i<m; i++){ int u, v; scanf("%d %d", &u, &v); a[u][v] = a[v][u] = 1; // it means undirected graph } }`

- it is similar to that of undirected grpah
- but when it is saved it doesn't just save 1 but its weight
- A[i][j] = w (there is edge connecting from i to j), 0 (no edge)
- if range of w is -9999 <= w <= 9999, we can make 2 arrays.
- one expresses edges connecting vertices
- another expresses weight of edges
- graph above can be expressed like this.
`/ 1 2 3 4 5 6 1 0 2 0 0 7 0 2 2 0 2 3 1 0 3 0 2 0 1 0 0 4 0 3 1 0 7 7 5 7 1 0 7 0 0 6 0 0 0 7 0 0`

- code
`#include <cstdio> #include <vector> int a[10][10]; int main() { int n, m; scanf("%d %d", &n, &m); for (int i=0; i<m; i++){ int u, v; scanf("%d %d", &u, &v); a[u][v] = a[v][u] = 1; // it means undirected graph } }`

- implement using linked-list
- in A[i], there are linked lists which is connected with 'i'
- in this case,
- A[1]: 2 5
- A[2]: 1 3 4 5
- A[3]: 2 4
- A[4]: 3 5 2 6
- A[5]: 1 2 4
- A[6]: 4
- the numbers in array actually doesn't mean vertex but edges
- the amount of its numbers means 'degree'

- it needs space of O(E)
- since LinkedList takes too much time to implement, it is usually implemented with vector in which length can be changed
- it is used to use space only needed
`#include <cstdio> #include <vector> using namespace std; vector<int> a[10]; // it is different from expression like a(10) // a[10] means 10 of 2 dimension array which has changable size int main() { int n, m; scanf("%d %d", &n, &m); for (int i=0; i<m; i++) { int u, v; scanf("%d %d", &u, &v); a[u].push_back(v); // it means undirected graph a[v].push_back(u); } }`

- it saves edges and weight like below
- A[1]: (2, 2) (5, 7)
- A[2]: (1, 2) (3, 2) (4, 3) (5, 1)
- A[3]: (2, 2) (4, 1)
- A[4]: (3, 1) (5, 7) (2, 3) (6, 7)
- A[5]: (1, 7) (2, 1) (4, 7)
- A[6]: (4, 7)

- implementation
`#include <cstdio> #include <vector> using namespace std; vector<pair<int, int>> a[10]; int main() { int n, m; scanf("%d %d", &n, &m); for (int i=0; i<m; i++) { int u, v, w; scanf("%d %d %d", &u, &v, &w); a[u].push_back(make_pair(v, w)); a[v].push_back(make_pair(u, w)); } }`

- Adjacency Matrix : O(V^2)
- Adjacency List : O(E)
- in most cases, we don't need much space for edges
- so adjacency list is usually right choice to use

- it is implemented by using array
- it saves all of edges
- for example)
- E[0] = 1 2
- E[1] = 1 5
- E[2] = 2 3
- ....
- each means start point of edge and end point of edge

- if there are 8 edges and the graph is undirected, to implement this, we need 16 spaces
- it should be sorted start point of edge first
- after sorting there should be array like this.
- i .... 0 1 2 3 4 5 6
- cnt[i] 0 2 4 2 4 3 1
- it means the number of edges in the graph

- implementation
`for (int i=0; i<m; i++) { cnt[e[i][0]] += 1; }`

- after getting the number of all edges to N
- accumulate like this again
- i .... 0 1 2 3 4 5 6
- cnt[i] 0 2 6 8 12 15 16

- implementation
`for (int i=1; i<=n; i++) { cnt[i] = cnt[i-1] + cnt[i]; }`

- after this, amazing thing happens
- the range from cnt[i-1] to cnt[i]-1 means that E[cnt[i-1] to E[cnt[i]-1] is the range of the edge number i
- for example)
- edges of vertex 1 exists from E[0] to E[1]
- 0 = cnt[i-1], 1 = cnt[i]-1

- edges of vertex 1 exists from E[0] to E[1]

- it means we want to save edges
- there are three ways
- adjacency matrix
- ineffective

- adjacency list
- edge list

- adjacency matrix

로그인 후 댓글을 작성 할 수 있습니다.

2019년 3월 15일

Connected Component connectedcomponent1.png - It is possible that graphs are divided into few pieces - like this, if graphs are separated, it is called connected component - There should be path to co...

2019년 3월 14일

Search of Graph - There are two kinds of way to search graph - DFS and BFS - DFS - Depth First Search Algorithm - Search graph as deeply and many as it can - It uses Stack - BFS - Breadth First S...

2019년 3월 12일

Representation of Graph Graph_Expression1.png - in case of this graph, it has 6 vertices and 8 edges - it doesn't have direction so it is undirected graph - vertices : {1, 2, 3, 4, 5, 6} - edges : {(1...

2019년 3월 12일

Graph ImageOfGraph.png - it's a type of datastructure - it has Node and Vertex(정점), Edge(간선) - Vertex and Node mean same thing. Circled ones in the image. - Edge means lines connecting circles. - T...

2019년 3월 9일

Card - boj/11652 - Junkyu has cards which contain a number between -2^62 and 2^62 - Which kind of card does Junkyu have the most? - It can be solved after sorted - After sorting cards, it can be solve...