Please enable JavaScript.
Coggle requires JavaScript to display documents.
Graphs - Coggle Diagram
Graphs
Path
A path (u,v) is a sequence of adjacent vertices from u to v
A graph is connected if every pair of vertices has a path
A cycle is a path that starts and ends in the same vertex
Representation
Adjacency matrix
more efficient for dense graphs
Θ(V^2)
Adjacency list
more efficient for sparse graphs
Θ(V+E)
Weighted Graph
a graph that has a number associated with every edge
Trees
a connected acyclic graph
Depth-first Search
Mark every vertex as not visited
For every node in the graph
If node wasn't visited already
Mark node as visited
Increase counter by 1
For every node adjacent to the current one
Breath-first Search
Mark every vertex as not visited
For every node in the graph
If node wasn't visited already
Mark node as visited
Increase counter by one
Add vertice to queue
While queue is not empty
For every vertex adjacent to the first one in queue
3 more items...
a collection of vertices and edges connecting them