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.
      • This represents the relationship between vertices.
  • G = (V, E)
  • for example) on facebook
    • friends are vertices
    • relationships are edges

Path in Graph

ImageOfGraph2.png

  • it has 5 Vertices and 7 Edges
  • Path from A to B
    • A->C->D->E->B
    • A->B
    • A->C->B
    • A->C->E->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
    • A->C->B->A
    • A->C->E->B->A
    • A->C->D->E->B->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.

Directed Graph

  • if there is arrow at the end of the edges
  • in case of graph above
    • A->C is possible
    • but C->A is impossible

Undirected Graph

  • 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

Mutiple Edge

  • 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

Loop edge

  • it also can be possible that one edge's start point and end point are the same.
    • A -> A

Weight

  • 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

  • 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