Graph, Vertices, and Edges

• A graph is a collection of vertices, and a collection of edges connecting pairs of vertices.
• Two kinds of graphs: directed and undirected
• Different between graph and tree: graph allow multiple parent (parent in the graph is not unique)

Degree, indegree, outdegree

• A degree of a vertex is the number of lines incident to it.
• The outdegree of a vertex is a digraph is the number of arcs leaving the vertex.
• The indegree of a vertex is the number of arcs entering the vertex.
• ถ้าถามแค่ว่า Degree เป็นเท่าไหร่— ให้เอา Indegree + Outdegree

A path and a cycle

• A path is a sequence of vertices and edges that starts at a vertex and ends at a vertex such that each edge is incident to it predecessor and successor vertex.
  • A path from A → F = {AB, BE, BF} (not unique)
• A cycle is a path that starts from a given vertex and ends at the same vertex

Example

• A path A → B → C goes from A to C
• A path A → B → C → A makes a cycle in this graph
  

Undirected vs Directed Graphs

• Undirected graphs
  • no directions on edges
  • the directed edge can be used to represent a two way road
  • Undirected Graph จริง ๆ แล้วมันคือ ไป-กลับ ($\leftrightarrow$) แต่ว่าไม่เขียนแค่นั้นเอง
• Directed graphs
  • edge has a direction showing what node that it comes from and what node that it goes to
  • the directed edge can be used to represent a one way road

Weighted vs Unweighted Graphs

• Unweighted graph
  • the edge has no weight
  • the weight can be used in the applications that the weights of the edges are no important and/or the weight are equal.
• Weighted graph
  • the edge has the weight
  • the weight can be used in the applications of cost, distance, time, etc.

Tree vs Graph

• A tree is a graph in which each vertex has only one predecessor (parent).
• However, the graph isn’t a tree. A vertex in graph can be originated from multiple predecessors.
• ==Tree $\subset$ Graph— All trees are graphs but all graphs are not tree==

Graph Storage Structures

How do we make a graph?

• There are two common storage structures
  1. Adjacency matrix
  2. Adjacency list

Adjacency Matrix

• It uses a vector or a one-dimensional array for the vertices and the matrix to store the edges.
• If two vertices are adjacent, the matrix has the value of 1. If not, it has 0.
• สำหรับ Undirected Graph มันจะ Symmetry (แปลว่าสามารถพับลงมาได้ แล้วยังเหมือนกัน)
  • แต่ถ้าเป็น Directed Graph มันจะไม่มี Symmetric Characteristics นะ!
• ถ้าสมมติว่าเกิดมี Weight ขึ้นมา ก็เขียนใน Matrix เป็น Weight นั้น ๆ ได้เลย แต่อันนี้แค่ดูว่ามีเส้นเชื่อมมั้ย

Adjacency List

• It uses a 2D ragged array to store the edges

• A vertex list is a singly linked list of the vertices in the list to keeps the vertex entries.

• Adjacency list is a linked list of edges from the vertex
  

• To read row 2 for example, we say ‘there are edges BA, BC, BE (starting from B)’

• จำนวน Ending Vertices (Adjacency List ในรูป) จะเท่ากับ Outdegree of the vertex in the row

Some facts about a graph

• Given a graph G with $n$ vertices and e edges
  • The outgoing edges of a vertex is at most $n-1$
  • The total number of edges e of graph is at most $(n-1)(n)$
    • มาจากแต่ละตัวก็มี Edges ได้ $n-1$ ใช่มั้ย แล้วมีทั้งหมด $n$ ตัว ดังนั้นก็ $(n-1)(n)$

Performance Analysis of Graph’s Operations (Big-O)

Insert a Vertex

• มีค่าเท่ากับ addLast ของ SList

Insert an Edge

• Traversing คือ Cost มากสุด ไปถึง $n$ ดังนั้น $O(n)$
  

Search for a Vertex

Delete an Edge

Delete a vertex

Traversing a graph

Depth First Traversal (DFS)

• starts at the starting point and explores as far as possible along each branch before backtracking
• ใช้ Stack— pop print push
  • จะเริ่มจากตรงไหนก็ได้! Node ไหนก็ได้เลยนะ
  • pop print ก็ทำปกติ
  • แต่เวลาจะ push (สมมติว่าเริ่มที่ A) ก็ดูว่า A สามารถไปไหนได้บ้าง ในที่นี้ B, C, D ก็ push เข้า Stack ไปได้เลย Order จะเป็นแบบไหนก็ได้ ไม่สนใจนะ
    • Highlight ที่เลือกไปแล้วก็ดีนะ เพราะว่าถ้าจะ push รอบต่อไป ห้ามเลือกตัวซ้ำ

Breadth First Traversal (BFS)

• The BFS begins at a root node and inspect all the neighboring nodes. Then for each of those neighbor nodes in turn, it inspects their neighbor nodes which were unvisited, and so on.
• ใช้ Queue— dequeue print enqueue
  • เหมือนเดิมเลยก็คือ จะเริ่มจาก Node ไหนก็ได้
  • dequeue print ทำปกติ
  • เวลา push ก็เลือกลูกที่เชื่อมอยู่ของตัวนั้น ๆ (ไม่ซ้ำ) คล้าย ๆ เดิม

The spanning tree

• A spanning tree is a sub-tree of a graph that contains all vertices of an undirected graph. A spanning tree must contain no cycles.
• Spanning tree of a graph with $n$ nodes has $n-1$ branches.
• Spanning trees are NOT unique.
• Spanning trees สามารถสร้างได้จาก DFS, BFS ได้นะ

Minimum Spanning Tree

• A minimum spanning tree (MST) is the spanning tree of which the total sum of the edges’ weights is minimum
• If the weights in a graph G is not distinct, then the minimum spanning tree is not unique.

MST Algorithms for Undirected Graphs

• สุดท้ายถ้าถามว่า MST Weight คืออะไร ก็ให้เอาเลขมาบวกกันนะ!

Prim-Jarnik’s Algorithm

1. Choose an arbitrary start vertex — เริ่มจาก Node (Vertex) ไหนก็ได้เลยเหมือนเดิม
2. Grow the tree by one edge: of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree.— เลือก Weight ที่น้อยที่สุด
3. Repeat step 2 (until all vertices are in the tree)

Kruskal Algorithm

1. List all edges of the graph in the increasing order of weights— เขียน List ออกมาเลยว่าแต่ละ Weight จากไหนไปไหนเป็นเท่าไหร่ แล้วต้อง Sort ด้วย
2. Select the smallest edge from the list
   • if the inclusion of this smallest edge doesn’t make a cycle, add it into the spanning tree (initially it is empty)
   • If the selected edge with the smallest weight form a cycle, remove it from the list

• Repeat Steps 2-3 until the tree contains $n-1$ edges or list is empty
• If the tree contain less than $n-1$ edges and the list is empty, no spanning tree is possible for the graph

The Shortest Path Problem

• Given a starting point u and the ending point v in a graph, find the path from u to v that gives the smallest distance.
• Dijkstra Algorithm can be used to find the shortest path problem.

Dijkstra Algorithm

• The idea of the algorithm is to continuously calculate the shortest distance beginning from a starting point, and to exclude longer distances when making an update.

• Prim compared only adjacent, where อันนี้ compare shortest distance with connected edges