Graph

25 Jul 2022 in Study / Computer science on Graph

Data Structure

• type of data structure
• == Node + Edge (간선)
• Edge can get the weight (가중치)

• Directed graph vs Undirected graph
  

• Complete graph (완전 그래프)
  • One node should be connected to all of other nodes
  • If the number of nodes is n, the number of edges is n(n-1)/2 (If the graph is directed graph, n(n-1))

• Bipartite graph (이분 그래프)
  • With 2 colors, it can be painted (One node should be painted by different color with neighbor nodes) : 2-colorable graph
    • That is, there should be no cycle between 3 nodes
  • Complete bipartite graph (완전 이분 그래프)
    • Complete graph + Bipartite graph
  • Example Problem This is the private repository where I can only review my notes
    Repository
• Planar graph (평면적 그래프), Plane graph (평면 그래프)
  • Planar graph : Given only several nodes (not edge), it can be called as planar graph if we can draw plane graph
  • Plane graph : All edges cannot be intersected
    • Edge < 3 x node
    • 4-colorable graph (at least 4 color)
• Eulerian graph (오일러 그래프)
  • If we can be back to start node through all of edges (node can be passed by multiple times), it can be called as Eulerian graph
• Tree
  • If we cannot be back to start node (node cannot be passed by multiple times), it can be called as tree
  • Edge = Node - 1
• Regular graph (정규 그래프)
  • All nodes have same degree
  • Degree (차수)
    • The number of edges which are connected to one node
• Directed acyclic graph (유향 비순환 그래프)
  • Directed graph
  • If we cannot be back to start node (node cannot be passed by multiple times), it can be called as acyclic graph

Representation

• Adjacency matrix
  • 2D array
  • Case 1: provide 2D information directly
    • Node == 1, Empty == 0
    • example
  • Case 2: provide 1D information
    • should convert to 2D information
• Adjacency list
  • In python, 2D lists are used for representing adjacency nodes of each node
  • These lists are used as linked list
• Comparison between matrix and list
  • Adjacency matrix
    • easily use
    • sensitivity for memory as the size of graph is bigger
    • Time Complexity of BFS & DFS
      • For searching neighbor nodes, we should search all of nodes
      • O(Node²)
  • Adjacency list
    • save the memory
    • hard
    • Time Complexity of BFS & DFS
      • There is no need to search all of nodes for finding neighbor nodes
      • O(Node + Edge)