II.1.1 Undirected Graphs
Algorithm II Week 1: Undirected Graphs
Graph
Graph. Set of vertices connected pairwise by edges.
Some Problems
Path. Is there a path between s and t ?
Shortest path. What is the shortest path between s and t ?
Cycle. Is there a cycle in the graph?
Euler tour. Is there a cycle that uses each edge exactly once?
Hamilton tour. Is there a cycle that uses each vertex exactly once.
Connectivity. Is there a way to connect all of the vertices?
MST. What is the best way to connect all of the vertices?
Biconnectivity. Is there a vertex whose removal disconnects the graph?
Planarity. Can you draw the graph in the plane with no crossing edges?
Graph isomorphism. Do two adjacency lists represent the same graph?
Graph API
Class Graph:
void add_edge(int v, int w)
list adj(inv)
int num_of_V()
int num_of_E()
str to_string()
Representation
Set-of-edges representation (linked list or array)
Adjancency-matrix representation (vertex-indexed array of lists)
public class Graph {
private final int V;
private Bag<Integer>[] adj;
public Graph(int V)
{
this.V = V;
adj = (Bag<Integer>[]) new Bag[V];
for (int v = 0; v < V; v++)
adj[v] = new Bag<Integer>();
}
public void addEdge(int v, int w)
{
adj[v].add(w);
adj[w].add(v);
}
public Iterable<Integer> adj(int v)
{ return adj[v]; }
}
Depth First Search & Breadth First Search
Getting out of a maze.
Last updated