Graphs

Fundamentals of Programming III

Overview

• Data Structures

• Lecture 10

• Topic: Graphs

Definitions of Graphs

• A graph is defined as a collection of objects.

  • Objects are called vertices (or nodes).

  • Vertices are interconnected by edges, representing relationships or links.

• Modeling Relationships:

  • Graphs illustrate how things are connected, e.g.,

  • Cities linked by roads.

  • People connected in a social network.

Graph Components

• G: Stands for Graph

• Mathematical Definition:

  • A graph can be mathematically defined as follows:

  • G = {V, E}

  • Where:

    • V = {v | v \text{ represents an item in } G}

    • E = {(vi, vj) | vi, vj \in V \text{ and } (vi, vj) \text{ is a relationship}}

• Characteristics of V and E:

  • Vertex set V does not need to denote physical locations; it can represent any data entity.

  • Edge set E signifies relationships and does not require physical connections or distances.

Adjacency

• Adjacent Vertices:

  • Vertices vi and vjVertices vivi and vjvj are termed adjacent if there exists an edge connecting them, denoted as (vi,vj)(vi,vj)

  • Adjacent vertices are considered neighbors.

• Graph Representation:

  • A graph serves as a representation of a collection of items and their inter-connections.

Path and Distance Definitions

• Path:

  • A sequence of edges running from vertex v0 to vn−1vn−1.

  • Denoted as vs \to vt .

• Path Length:

  • The number of edges within a specific path.

• Distance:

  • Denoted as D(v0 \to v{n-1}) .

  • Mathematically expressed as: \text{D}(v_0 \to v_{n-1}) = \min(\text{paths from } v_0 \to v_{n-1})

Example of a Graph

• Consider the following graph:

  • Edge set: E = {AB, AD, BC, BE, CE, DE, EF}

  • Paths:

  • A to F:

    • {ABEF, ADEF, ABCEF}

  • Distance:

  • A to F is 3 edges long.

  • Adjacent Vertices:

  • Set: {AB, AD, BC, BE, CE, DE, EF}, connecting vertices A, B, C, D, E, F.

Applications of Graphs

• Graphs are versatile and connect every aspect of:

  • Physical & Spatial Systems:

  • Geographic maps and navigation: Cities as vertices, roads as edges.

  • Electronic circuits: Directed, weighted graphs.

  • Hydraulic systems: Nodes for junctions, edges for flow paths.

  • Path optimization in logistics and GPS for finding efficient routes.

  • Transportation networks including railways and air routes.

• Information & Digital Networks:

  • World Wide Web (WWW): Web pages as vertices, hyperlinks as edges.

  • Operating System: Resource allocation graphs used for deadlock detection.

  • Computation flow networks: Nodes (operations), edges (data/control flow).

  • Blockchains: Each block referencing previous blocks forms a specialized type of graph.

  • Internet routing where routers and their connections are modeled as graphs.

• Knowledge & Intelligence:

  • Knowledge graphs used in AI depict links between concepts.

  • Neural networks structured with neurons connected by weighted edges.

  • Semantic web and ontology graphs facilitate search and recommendation systems.

• Biological & Natural Systems:

  • Studies on species interactions, food webs, and genetic trees.

  • Epidemiological graphs illustrate the spread of diseases across populations.

• Social & Behavioral Systems:

  • Networks such as LinkedIn, Facebook, and citation networks among researchers.

  • Product recommendation systems based on user purchase patterns.

  • Influence graphs show the propagation of trends and social information.

• Data Structures & Computer Science:

  • Specialized graphs: linked lists, trees, heaps.

  • Compiler dependency graphs utilized in build systems and topological sorting.

Representing Graphs

• Adjacency List:

  • Represents a graph as a collection of lists where each vertex has a list of its adjacent vertices.

  • Example from previous graph:

  • A: {B, D}

  • B: {A, C, E}

  • C: {B, E}

  • D: {A, E}

  • E: {B, C, D, F}

  • F: {E}

• Space Complexity:

  • O(V + E); effective for sparse graphs.

  • Adjacent determination in O(V) time.

    • O(V) = O(N)

Adjacency Matrix

• An adjacency matrix models graphs using a two-dimensional array.

  • Each cell (i, j) indicates if an edge exists between vertex i and vertex j.

  • Matrix Example (for V vertices):

  • Cell \text{VAM}[i][j] equals 0 or null if no connection.

  • Size: O(V^2), suited for dense graphs.

• Connection Lookup:

  • Executes in O(1) time.

Graph Traversal Techniques

• Unlike trees, graphs have no single root. Traversal can begin from any node.

  • Aim is to visit all vertices, denoting the terminal point (T) as where we stop.

Depth First Search (DFS)

• DFS algorithm execution on a specified graph:

  • Procedure:

  • Push the starting vertex onto a stack.

  • While the stack is not empty:

    • Pop the current vertex from the stack.

    • If not already visited, visit it.

    • Add the current vertex to a visited set.

    • For each adjacent vertex, push into the stack.

• Uses of DFS:

  • Pathfinding, maze-solving, route navigation, topological sorting, cycle detection, social network analysis, feedback loop detection in network design.

Breadth First Search (BFS)

• BFS algorithm execution on a specified graph:

  • Procedure:

  • Enqueue the start vertex into the search queue.

  • Add the start vertex to a discovered set.

  • While the queue is not empty:

    • Dequeue the current vertex.

    • Visit it and enqueue its neighbors if not discovered.

• Uses of BFS:

  • Finding the shortest path in non-weighted graphs, network connectivity, hierarchical processing in machine learning, organization chart handling.

Special Types of Graphs

Directed Graphs

• Definition:

  • Directed graphs consist of edges representing one-way relationships.

  • An edge from vi to vj (denoted vi \to vj ) does not imply a reciprocal edge.

• Adjacent Condition:

  • Vertex vj is adjacent to vi , and vice versa, but paths are strict directional.

• Path:

  • A sequence of directed edges runs from starting vertex vs\text{D}(v_0 \to v_t) = \min(\text{paths from } v_0 \to v_t)

• Cycle:

  • A path that loops back to the starting vertex.

• Terminologies:

  • Cyclic Graph: Contains cycles.

  • Acyclic Graph (DAG): Contains no cycles.

Weighted Graphs

• Definition:

  • Contains edges with associated weights or costs.

  • Can be directed or undirected.

• Path Length Calculation:

  • Path length is the sum of all weights along the path denoted as:
    \text{Path Length} = \sum{i=0}^{n} \text{weight}(vi \to v_{i+1})

  • Where v0 is the start vertex and vn is the end vertex.

• Shortest Path Condition**:

  • Finds the minimum path length from a start vertex to a terminal vertex.

• Negative Weight Cycles:

  • A cyclic graph with negative weights may not yield a valid shortest path if included in the graph path.

Common Graph Algorithms

Dijkstra's Shortest Path Algorithm

• Purpose: Finds the least costly path in weighted graphs with non-negative weights.

• Dijkstra's Implementation:

  • Initialize distances to infinity for each vertex except for the starting vertex (distance = 0).

  • Utilize a priority queue for the unvisited vertices.

  • Calculate minimum distances iteratively while updating predecessor vertices for route tracing.

  • Works by starting at the vector we’re trying to get to.

• Time Complexity:

  • O((V + E) \log V) for running Dijkstra efficiently with a priority queue.

Minimum Spanning Tree (MST)

• Definition:

  • A minimum spanning tree is a subgraph that connects all vertices with the minimum possible total edge weight.

    • Every subgraph is connected to another subgraph. Every node is available from some other node. 

  • Multiple MSTs possible for one graph.

• Common Algorithms to Find MST:

  • Prim's Algorithm

  • Kruskal's Algorithm

Steps:

* Pick a starting town. This town is the first part of your road network.

* Identify all roads leading out of this starting town.

Put all these roads (along with their costs) into a *'Potential Roads' list**.

2. Choose the Best Road

Repeatedly look at your *'Potential Roads' list** and select the road with the absolute lowest cost. This is the core greedy choice of the algorithm.

3. Validate the Road

* Check where this cheapest road leads.

* If the road connects to a town you've already included in your network, discard it. Adding it would create a loop (a cycle), which is wasteful.

* If the road connects to a new town, keep it!

4. Expand the Network

* Add the new road to your final MST network.

* Add the new town to your set of connected towns.

5. Update Potential Roads

Now that you have a new town, look at *all the roads leading out of this new town**.

* Add these new roads (with their costs) to your 'Potential Roads' list, but only if they lead to towns that are not yet connected.

6. Repeat and Finish

Go back to *Step 2** and repeat the process (find the new cheapest road, validate, expand) until all towns are included in your network.

The final set of roads you collected is the Minimum Spanning Tree—the cheapest way to connect all towns without any unnecessary loops.

Topological Sort

• Definition:

  • Topologically ordering the vertices of a Directed Acyclic Graph (DAG) ensuring that for every directed edge u \to v, vertex u precedes vertex v in the sequence.

• Indegree & Outdegree:

  • Indegree: Number of edges arriving to a vertex.

  • Outdegree: Number of edges leading from a vertex.

Bellman-Ford Shortest Path Algorithm

• Purpose: Finds the shortest path when the graph has negative edges, may not find the best path but it’ll find a good path.

• Operating Mechanism:

  • Relaxation of edges |V| - 1 times; checks for negative-weight cycles in the graph during iterations.

  • Doesn’t operate with cycles to avoid loops.

• Overall Complexity:

  • Time complexity of O(V \times E).

Comparison: Dijkstra vs. Bellman-Ford

# Conclusion

• The concept of graphs encompasses every structure and relationship within the interconnected realm of data.

• The discussion extends across various applications, representation techniques, traversal methods, and common algorithms utilized in digital systems and data structures.

• Understanding the complexities of graphs allows for improved pathfinding and relationship modeling in both computational and real-world scenarios.