Transcript And this is a graph - Computer Science Department

CSE 214 – Computer Science II
Graphs
Source: http://orange.math.buffalo.edu/241/graph_paper.gif
What kind of data structure is the Internet?
Ref: http://personalpages.manchester.ac.uk/staff/m.dodge/cybergeography/atlas/historical.html
What kind of data structure is used by game AI for pathfinding?
You guessed it, Graphs!
• What is a graph?
– a non-linear data structure
– consists of nodes & links between nodes
– nodes can be linked in any pattern, not necessarily
hierarchical
– nodes can be directed, or undirected
– can be weighted
This is a tree
A
B
D
C
E
F
G
This is a graph
A
B
D
C
E
F
G
And this is a graph
A
B
D
C
E
F
G
And this is a graph
A
B
D
C
E
F
G
And this is a graph
A
B
D
C
E
F
G
Undirected Graphs
• A set of nodes
– vertices
• And a set of links between the nodes
– edges
• Each edge connects two vertices
• Graph walkers (like travelers) may move across
undirected edges in both directions
An undirected graph
A
B
C
F
E
G
D
Directed Graphs
• A set of nodes
– vertices
• And a set of links between the nodes
– edges
• Each edge is associated with 2 vertices:
– a source vertex
– a target vertex
• Graph walkers (like travelers) may move across
directed edges only from source to target
A directed graph
A
B
C
F
E
G
D
A weighted graph
• Can be an undirected or direct graph
• Each edge is weighted with some value
– represents cost of edge
• Cost of what?
– depends on application
• Might be:
– distance, resistance, money. Etc.
A weighted graph
A
5
6
B
C
3
7
8
9
F
5
12
E
G
4
11
D
How can we define a graph?
• Many options
– nodes (we’ve seen this already, similar to trees)
– an adjacency matrix
– edge sets
Adjacency Matrix
• A 2D table
– 2D array
– row for each node
– column for each node
• Values in cells can be
– boolean denoting are they connected
OR
– numeric representing weighting of connections
Adjacency Matrix
A
5
6
9
B
C
7
3
D
A
B
C
D
A
0
5
6
0
B
5
0
9
3
C
6
9
0
7
D
0
3
7
0
Edge sets
• List all the edges in a graph
• Advantage:
– more efficient data management
• For what?
– Graph walking
– Graph manipulation
• Ex, 3D meshes:
– vertex buffers & index buffers
– render mesh needs graph traversal
3D Models/Meshes are textured graphs
Ref: http://www.cubixstudio.com/HTML/Product/MaleContentPackMoreInfo.htm
Walking graphs
• Many problems:
–
–
–
–
Shortest path problems
Traveling salesman problems
Chinese postman problems
Etc.
• Many algorithms for calculating solutions:
– Greedy, Djikstra’s algorithm, A*, etc.
Want to learn more?
•
•
•
•
•
AMS 301: Finite Mathematical Structures
CSE 352: Artificial Intelligence
CSE 373: Analysis of Algorithms
CSE 380: Computer Game Programming
CSE 381: Advanced Game Programming