# 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.

![Representation of undirected Graph](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-c451e99985ec27db18582d83fb3731dbbb10a702%2Fimage%20\(104\).png?alt=media)

## **Adjacency Matrix Representations**

**Algorithm**

Maintain a two dimensional $$v \* v$$ matrix boolean array

for each edge $$v - w$$ in graph: $$adj\[v]\[w] = adj\[w]\[v] = true$$

![Adjacency Matrix representation](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-9235c491cce5edd327d2af16c9969e12a190c134%2Fimage%20\(94\).png?alt=media)

**Note:** Adjacency matrix consumes more space.

{% hint style="success" %}

* **Space Complexity :** $$v^{2}$$
* **Add Edge:** 1
* Edge between $$v$$and $$w$$ is 1
* Iterate over vertices adjacent to $$v$$ : $$V$$
  {% endhint %}

## Adjacency List Representation

In this representation , If there is path exists between any two vertices, vertices are added to vertex list.

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-703cf5a67c79be648518269e92ecb944d8460f06%2Fimage%20\(99\).png?alt=media)

### Java Implementation

```java
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) {}
}
```

{% hint style="success" %}

* **Space Complexity :** $$E + V$$
* **Add Edge:** 1
* Edge between $$v$$and $$w$$ is $$degree(v)$$
* Iterate over vertices adjacent to $$v$$ - $$degree(v)$$
  {% endhint %}

## Depth First Search

### Algorithm

To visit a vertex $$v$$ :

* Mark vertex $$v$$ as visited.
* Recursively visit all unmarked vertices adjacent to $$v$$.

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-9de5e380f4007ac1963c09b13feb1455fa747a45%2Fimage%20\(101\).png?alt=media)

### Java Implementation

```java
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 $$v$$ from queue.
* Add to queue all unmarked vertices adjacent to $$v$$ and mark them.

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-80828599ce006625282792e79184a8ca1b1e5953%2Fimage%20\(102\).png?alt=media)

### Java Implementation

```java
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.

![Connected Components](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-5782be52bd4c2865c1ff4236c3b28d3972a5f110%2Fimage%20\(103\).png?alt=media)

### Algorithm

To visit a vertex v :

* Mark vertex v as visited.
* Recursively visit all unmarked vertices adjacent to v.

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-76a03feaa60bc2de2626d5e5ce3aeb9aa3babf87%2Fimage%20\(106\).png?alt=media)

### Java Implementation

```java
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**

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-f12d7e63f7ee5df6ce92335107cab91b5135354d%2Fimage%20\(108\).png?alt=media)