Undirected Graphs
Glossary
A self-loop is an edge that connects a vertex to itself.
Two edges are parallel if they connect the same pair of vertices.
When an edge connects two vertices, we say that the vertices are adjacent to one another and that the edge is incident on both vertices.
The degree of a vertex is the number of edges incident on it.
A subgraph is a subset of a graph's edges (and associated vertices) that constitutes a graph.
A path in a graph is a sequence of vertices connected by edges, with no repeated edges.
A simple path is a path with no repeated vertices.
A cycle is a path (with at least one edge) whose first and last vertices are the same.
A simple cycle is a cycle with no repeated vertices (other than the requisite repetition of the first and last vertices).
The length of a path or a cycle is its number of edges.
We say that one vertex is connected to another if there exists a path that contains both of them.
A graph is connected if there is a path from every vertex to every other vertex.
A graph that is not connected consists of a set of connected components, which are maximal connected subgraphs.
An acyclic graph is a graph with no cycles.
A tree is an acyclic connected graph.
A forest is a disjoint set of trees.
A spanning tree of a connected graph is a subgraph that contains all of that graph's vertices and is a single tree. A spanning forest of a graph is the union of the spanning trees of its connected components.
A bipartite graph is a graph whose vertices we can divide into two sets such that all edges connect a vertex in one set with a vertex in the other set.
Graph having two directions from any vertex in a path to another verted.

Adjacency Matrix Representations
Algorithm
Maintain a two dimensional matrix boolean array
for each edge in graph:

Note: Adjacency matrix consumes more space.
Space Complexity :
Add Edge: 1
Edge between and is 1
Iterate over vertices adjacent to :
Adjacency List Representation
In this representation , If there is path exists between any two vertices, vertices are added to vertex list.

Java Implementation
public class Graph {
private final int V;
private List<Integer>[] adj;
public Graph(int v) {
this.V = v;
adj = new List[v];
for (int i = 0; i < V; i++) {
adj[i] = new ArrayList<>();
}
}
public void addEdge(int v, int w) {
adj[v].add(w);
adj[w].add(v);
}
public Iterable<Integer> adj(int v) {
return adj[v];
}
public static void main(String[] args) {}
}
Space Complexity :
Add Edge: 1
Edge between and is
Iterate over vertices adjacent to -
Depth First Search
Algorithm
To visit a vertex :
Mark vertex as visited.
Recursively visit all unmarked vertices adjacent to .

Java Implementation
public class DepthFirstPaths
{
// marked[v] = true if v connected to s
private boolean[] marked;
// edgeTo[v] = previous vertex on path from s to v
private int[] edgeTo;
private int s;
public DepthFirstPaths(Graph G, int s)
{
// Initialize all the constructors
..............
dfs(G, s);
}
private void dfs(Graph G, int v)
{
marked[v] = true;
for (int w : G.adj(v)){
if (!marked[w])
{
dfs(G, w);
edgeTo[w] = v;
}
}
}
public boolean hasPathTo(int v)
{
return marked[v];
}
public Iterable<Integer> pathTo(int v)
{
if (!hasPathTo(v)) return null;
Stack<Integer> path = new Stack<Integer>();
for (int x = v; x != s; x = edgeTo[x])
path.push(x);
path.push(s);
return path;
}
}
Bredth First Search
Algorithm
Repeat until queue is empty
Remove vertex from queue.
Add to queue all unmarked vertices adjacent to and mark them.

Java Implementation
public class BreadthFirstPaths
{
private boolean[] marked;
private int[] edgeTo;
private void bfs(Graph G, int s)
{
Queue<Integer> q = new Queue<Integer>();
q.enqueue(s);
marked[s] = true;
while (!q.isEmpty())
{
int v = q.dequeue();
for (int w : G.adj(v))
{
if (!marked[w])
{
q.enqueue(w);
marked[w] = true;
edgeTo[w] = v;
}
}
}
}
}
Connected Components
A connected component is a maximal set of connected vertices.

Algorithm
To visit a vertex v :
Mark vertex v as visited.
Recursively visit all unmarked vertices adjacent to v.

Java Implementation
public class CC {
private boolean[] marked;
private int[] id;
private int count;
public CC(Graph G){
marked = new boolean[G.V()];
id = new int[G.V()];
for(int i=0;i<G.V();i++){
if(!marked[i])
{
dfs(G, i);
count++;
}
}
}
public int count()
{
return count;
}
public int id(int v)
{
return id[v];
}
// All vertices discovered in same call of dfs have same id
private void dfs(Graph G, int v)
{
marked[v] = true;
id[v] = count;
for (int w : G.adj(v))
if (!marked[w])
dfs(G, w);
}
}
Undirected Graph Applications

Last updated
Was this helpful?