Scribd
Upload
8 views17 pages

Graph

A graph is a data structure consisting of a set of nodes (vertices) and edges that connect them, used for modeling and solving problems. It can be directed or undirected, and includes terminology such as adjacent, degree, and cycle. Graphs can be implemented as matrices or linked lists, and common algorithms for pathfinding include Depth First Search (DFS) and Breadth First Search (BFS).

Uploaded by

mohamadqodosi1996
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views17 pages

Graph

A graph is a data structure consisting of a set of nodes (vertices) and edges that connect them, used for modeling and solving problems. It can be directed or undirected, and includes terminology such as adjacent, degree, and cycle. Graphs can be implemented as matrices or linked lists, and common algorithms for pathfinding include Depth First Search (DFS) and Breadth First Search (BFS).

Uploaded by

mohamadqodosi1996
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Graph

Mohammad Ghoddosi
Graph
What is a graph?

 A data structure
 Tool for modeling a problem
 Tool to solve problems
 Graph
 Set of nodes (Vertices)
 Set of edges (relate the nodes to each other)
Graph example
Graph example

TR

SY AF
LB
IQ IR

IL JO KW
PK
AE

SA
OM

YE
Graph example

TR AF
IR
LB
SY

PK
IQ

IL
AE
JO
SA

KW OM

YE
Königsberg
Königsberg
Formal Definition

 Graph is defined as:


 𝐺𝐺 = 𝑉𝑉, 𝐸𝐸
 𝑉𝑉 𝐺𝐺 : a finite nonempty set of vertices
 𝐸𝐸 𝐺𝐺 : a set of edges (pairs of vertices)
Formal Definition

 Graph is defined as:


 𝐺𝐺 = 𝑉𝑉, 𝐸𝐸
 𝑉𝑉 𝐺𝐺 : a finite nonempty set of vertices
 𝐸𝐸 𝐺𝐺 : a set of edges (pairs of vertices)
 Graph can be directed or undirected
 Graph can be weighte
Terminology

 Adjacent or neighbor (‫ ھﻤﺴﺎﯾﻪ‬،‫)ﻣﺠﺎور‬


 Degree (‫)درﺟﻪ‬
 Loop (‫ ﻃﻮﻗﻪ‬/ ‫)ﺣﻠﻘﻪ‬
 Path (‫)ﻣﺴﯿﺮ‬
 Cycle (‫)ﺣﻠﻘﻪ‬
 Complete graph (‫)ﮔﺮاف ﮐﺎﻣﻞ‬
 Distance (‫)ﻓﺎﺻﻠﻪ‬
 Connected (‫)ھﻤﺒﻨﺪ‬
Tree vs Graph

 Tree is a special graph


 Tree is a connected graph
 Tree doesn’t have any loops
Graph implementation

 As matrix
 We can define adjacency matrix
 Row I and column j is 1 on node I and j are connected
 As linked list
 Each node has a value and a list of links
Simple problems

 In a graph, what is the relationship between sum of degrees and number of vertices?
 If 10 people each shake hands with each other, how many handshakes took place?
 Among a group of 5 people, is it possible for everyone to be friends with exactly 2 of the
people in the group? What about 3 of the people in the group?
Graph path finding

 Depth first search (DFS)


 Travel as far as you can
 Back up as little as possible
 Search depth
 Stack
 Breadth first search (BFS)
 Look at all possible paths at the same depth
 Back up as far as possible
 queue
DFS (from IR)

TR AF
IR
LB
SY

PK
IQ

IL
AE
JO
SA

KW OM

YE
BFS (from IR)

TR AF
IR
LB
SY

PK
IQ

IL
AE
JO
SA

KW OM

YE

You might also like