- 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

- 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

- 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 - usually, V^2 >= E
- to solve easy problems, it is good way to express graph data structure. }

- 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.

- another expresses weight of edges

- code

- 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'

- the numbers in array actually doesn't mean vertex but edges

- 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

- 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

- 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

- 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

- 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

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

- adjacency matrix

- ineffective- adjacency list
- edge list