# Graphs

**Graph:** A graph is a data structure that consists of the following two components:\
**1.** A finite set of vertices also called as nodes.\
**2.** A finite set of ordered pair of the form (u, v) called as edge. The pair is ordered because (u, v) is not the same as (v, u) in case of a directed graph(di-graph). The pair of the form (u, v) indicates that there is an edge from vertex u to vertex v. The edges may contain weight/value/cost.

## **Terminology**

* **Path**: Sequence of vertices connected by edges.
* **Cycle**: Path whose first and last vertices are the same.
* **Degree**: Number of connected vertices for a node.
* **Euler Tour**: Cycle that uses each edge exactly once.
* **Hamilton tour:** Cycle that uses each vertex exactly once.
* **Biconnectivity:** Vertex whose removal disconnects the graph.

![](/files/4QMB5fZOYaGxg3D8ArKC)

## **Graph API**

```java
public class Graph{

    // Initialize the graph with v vertices
    Graph(int v);
    
    // Add an edge between vertex v and vertex w
    void addEdge(int v , int w);
    
    // Vertices adjacent to v
    Iteratable<Integer> adj(int v);
    
    // Number of Vertices
    int V();
    
    // Number of Edges
    int E();

}
```

## **Graph Utility**

### **Degree**

\*\*\*\*Number of vertices connected to $$v$$

```java
public static int degree(Graph G, int v){
    int degree = 0;
    for(int w : G.adj(v) ){
        degree++;
    } 
    return degree;
}
```

### **Max Degree**

```java
public static int maxDegree(Graph G){
    int max = 0;
    for( int v=0; v < G.V(); v++ ){
        max = Math.max(degree(G, v), max);
    } 
    return max;
}
```

### **Average Degree**

```java
public static double averageDegree(Graph G){
    return 2.0 * G.E() / G.V();
}
```

### Self Loops

```java
public static int countSelfLoops(Graph G){
    int count = 0;
    for(int v=0;v<G.V(); v++){
        for(int w: G.adj(v)){
            if(v == w) {
                count++; 
            }
        }
    }
    return count/2; // Each edge counted twice
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.sunilgudivada.dev/notebook/data-structures-and-algorithms/topics/graphs.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.