Graph

Many real world problem can be solved using the Graph.

A Graph

G=(V,E)G=(V, E)

where is (V, E) is a ordered pair of Vertices(Nodes) and Edges.

Basic Graph Terminologies

Directed vs Undirected Graph

  • Directed Graph : Edges Only 1 Way
  • Undirected : Edges are Bidirectional

Weighted vs Unweighted Graph

  • Weighted Graph : There is weight on each edge
  • Unweighted Graph : No weight on each edge (or same weight on each edge)

Adjacent Vertices

  • The 2 Vertices connected by the same Edge are Adjacent vertices.

Adjacent Edges

  • The 2 or more Edges connected by the same Vertex are Adjacent Edges.

Incident

  • An Edge in the graph that Join 2 Vertices. That Edge is called Incident of the 2 Vertices.

Degree

  • The number of edges that are incident of (or connected to) the particular vertex.

Neighbor

  • 2 Vertices/Edges are called Neighbor if they are adjacent.

Loop

  • There is a Loop if the edge of the vertex link back to the vertex itself.

Cycle

  • A graph which has a close path that start from a vertex and end in the same vertex.

Parallel edge

  • 2 Vertices are connected with 2 or more edges then the edges are called Parallel edge.

Simple Graph

  • No Loop
  • No Parallel edges

Complete graph

  • Fully Connected (Every Vertex is connect to all other vertices)
  • A Complete graph must be a Connected graph
    • A Complete graph is a Connected graph that Fully connected
  • The number of edges in a complete graph of n vertices = n(n−1)2\frac{n(n-1)}{2}
  • Full

Connected graph

  • A Path exist (Don’t have to be fully connected)

Tree / Spanning Tree

The Data Structure Tree is actually a type of Graph.

  • No Cycle

Representing Graphs

There are many ways to represent a graph.

Representing Vertices

1
String[] vertices = {"Peter", "Jane", "Mark", "Wendy", "Cindy"};

Representing Graph: Vertices + Edge Array

1
2
String[] vertices = {"Peter", "Jane", "Mark", "Wendy", "Cindy"};
int[][] edges = {{0,2}, {1,2}, {2,4}, {3,4}};

Representing Edges: Edge Objects

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Edge {
	int u, v;
	public Edge(int u, int v) {
		this.u = u;
		this.v = v; 
	}
}

List<Edge> list = new ArrayList<>(); 
list.add(new Edge(0, 1)); //Seattle to San Francisco
list.add(new Edge(0, 3)); //Seattle to Denver
list.add(new Edge(0, 5)); //Seattle to Chicago
//...

Representing Edges: Adjacency Matrices

1
2
3
4
5
6
7
int[][] adjacencyMatrix = {
{0,0,1,0,0}, //Peter
{0,0,1,0,0}, //Jane
{0,0,0,0,1}, //Mark
{0,0,0,0,1}, //Cindy
{0,0,0,0,0}, //Wendy
};

Representing Graph : Adjacency Edge List + Adjacency Vertex List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
List < ArrayList < Edge >> neighbors = new ArrayList < > ();
neighbors.add(new ArrayList < Edge > ());
neighbors.get(0).add(new Edge(0, 1)); //Seattle to San Francisco
neighbors.get(0).add(new Edge(0, 3)); //Seattle to Denver
neighbors.get(0).add(new Edge(0, 5)); //Seattle to Chicago
neighbors.add(new ArrayList < Edge > ());
neighbors.get(1).add(new Edge(1, 0)); //San Francisco to Seattle
neighbors.get(1).add(new Edge(1, 2)); //San Francisco to Los Angeles
neighbors.get(1).add(new Edge(1, 3)); //San Francisco to Denver
//... 
neighbors.add(new ArrayList<Edge>());
neighbors.get(11).add(new Edge(11, 8)); //Houston to Atlanta
neighbors.get(11).add(new Edge(11, 9)); //Houston to  Miami
neighbors.get(11).add(new Edge(11, 10)); //Houston to Dallas

Graph Traversals

Common operations of graphs are defined in the interface and concrete classes define concrete graphs.

The UnweightedGraph has 2 Traversal methods:

  • Depth-first search (dfs)
  • Breadth-first search (bfs)
  • Both traversals result in a spanning tree, which can be modeled using a class.

Depth-first search (DFS)

  • The search can start from any vertex.

Since each edge and each vertex is visited only once, the time complexity of the dfs method is O(|E| + |V|), where |E| denotes the number of edges and |V| the number of vertices.

  • Detecting whether a graph is connected.
    • Search the graph starting from any vertex. If the number of vertices searched is the same as the number of vertices in the graph, the graph is connected. Otherwise, the graph is not connected.
  • Detecting whether there is a path between two vertices.
  • Finding a path between two vertices.
  • Finding all connected components.
    • A connected component is a maximal connected subgraph in which every pair of vertices are connected by a path.
  • Detecting whether there is a cycle in the graph.
  • Finding a cycle in the graph.

Breadth-first search (BFS)

  • Breadth-first search visits a node, then its neighbors, then its neighbors’s neighbors, and so on.

Since each edge and each vertex is visited only once, the time complexity of the bfs method is O(|E| + |V|) where |E| denotes the number of edges and |V| the number of vertices.

  • Detecting whether a graph is connected.
    • A graph is connected if there is a path between any two vertices in the graph.
  • Detecting whether there is a path between two vertices.
  • Finding a shortest path between two vertices.
    • You can prove that the path between the root and any node in the BFS tree is the shortest path between the root and the node.
  • Finding all connected components.
    • A connected component is a maximal connected subgraph in which every pair of vertices are connected by a path.
  • Detecting whether there is a cycle in the graph.
  • Finding a cycle in the graph.