Algorithm Study #6 (Graph_Concept)
2019년 3월 12일
java algorithm study
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.
- This represents the relationship between vertices.
G = (V, E)
for example) on facebook
- friends are vertices
relationships are edges
Path in Graph
it has 5 Vertices and 7 Edges
Path from A to B
Cycle in Graph
This refers to a case where the origin and destination are the same.
- A to A
B to B
Cycle about A to A
what we usaully need in Graph
we usually need some shortest path
express conditions as a graph and solve it
Simple Path and Simple Cycle
Graph which is not visiting the same vertex more than once in a path or cycle
When nothing is mentioned, the commonly used path or cycle is this case.
if there is arrow at the end of the edges
in case of graph above
- A->C is possible
but C->A is impossible
there is no arrow at the end of the edges
it is also called Bidirected Graph
when it comes to code, write about two edges
there can be multiple edges between two vertices
if there are two edges which has different weight
- smaller weight one would be win and bigger weight one would be ignored
it also can be possible that one edge's start point and end point are the same.
- A -> A
when there is weight, it is a really important thing.
it is about how much it will cost or take...
if there is no weight, we can think that all weights get value of 1
Degree means edges of each vertice
if a has 3 edges, a's degree is also 3
in case of directed graph
- it is divided into indegree and outdegree
대전에 있는 (주) 아이와즈에서 풀스택 웹개발자로 일하고 있는 서진규입니다. 주로 Jake Seo라는 닉네임을 많이 씁니다.
Algorithm Study #5 (Sort And Its Application)
Algorithm Study #6 (Graph_Expression_How_To_Save_Graph)