Graphs I: Introduction to Graph Theory

Introduction to Graph Theory

Graph Representation Techniques

Key Graph Terms

• Vertex (Node): A fundamental unit in a graph that represents an entity
• Edge: A connection between two vertices representing a relationship
• Degree: The number of edges connected to a vertex
• Path: A sequence of vertices connected by edges
• Cycle: A path that starts and ends at the same vertex
• Connected Graph: A graph where there is a path between every pair of vertices
• Tree: A connected graph with no cycles
• Bipartite Graph: A graph whose vertices can be divided into two sets with no edges within each set

Java Implementation

import java.util.*;

public class Graph {
    private int V; // Number of vertices
    private List> adjList; // Adjacency list
    
    // Constructor
    public Graph(int vertices) {
        this.V = vertices;
        
        // Initialize adjacency list
        adjList = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adjList.add(new ArrayList<>());
        }
    }
    
    // Add an edge to the graph
    public void addEdge(int source, int destination) {
        // For an undirected graph, add edges in both directions
        adjList.get(source).add(destination);
        adjList.get(destination).add(source);
    }
    
    // Add directed edge to the graph
    public void addDirectedEdge(int source, int destination) {
        adjList.get(source).add(destination);
    }
    
    // Get the adjacency list for a specific vertex
    public List getNeighbors(int vertex) {
        return adjList.get(vertex);
    }
    
    // Print the graph representation
    public void printGraph() {
        for (int i = 0; i < V; i++) {
            System.out.print("Vertex " + i + " is connected to: ");
            for (Integer neighbor : adjList.get(i)) {
                System.out.print(neighbor + " ");
            }
            System.out.println();
        }
    }
    
    // Get the number of vertices
    public int getVertexCount() {
        return V;
    }
    
    // Example usage
    public static void main(String[] args) {
        // Create a graph with 5 vertices
        Graph graph = new Graph(5);
        
        // Add edges
        graph.addEdge(0, 1);
        graph.addEdge(0, 4);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);
        
        // Print the graph
        graph.printGraph();
    }
}

Guided Practice

For additional hands-on practice and exercises on graph theory, check out our comprehensive guided project:

• Guided Project: Introduction to Graphs

Java Implementation

public class GraphMatrix {
    private int V; // Number of vertices
    private boolean[][] adjMatrix; // Adjacency matrix
    
    // Constructor
    public GraphMatrix(int vertices) {
        this.V = vertices;
        adjMatrix = new boolean[V][V];
    }
    
    // Add an edge to the graph
    public void addEdge(int source, int destination) {
        // For an undirected graph, add edges in both directions
        adjMatrix[source][destination] = true;
        adjMatrix[destination][source] = true;
    }
    
    // Add directed edge to the graph
    public void addDirectedEdge(int source, int destination) {
        adjMatrix[source][destination] = true;
    }
    
    // Check if two vertices are connected
    public boolean isEdge(int source, int destination) {
        return adjMatrix[source][destination];
    }
    
    // Print the graph representation
    public void printGraph() {
        System.out.println("Graph representation using Adjacency Matrix:");
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                System.out.print(adjMatrix[i][j] ? "1 " : "0 ");
            }
            System.out.println();
        }
    }
    
    // Get the number of vertices
    public int getVertexCount() {
        return V;
    }
    
    // Example usage
    public static void main(String[] args) {
        // Create a graph with 5 vertices
        GraphMatrix graph = new GraphMatrix(5);
        
        // Add edges
        graph.addEdge(0, 1);
        graph.addEdge(0, 4);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);
        
        // Print the graph
        graph.printGraph();
    }
}