✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-097

Directed and Undirected Graphs

Directed and undirected graphs describe two different types of relationships. Directed graphs use edges with specific directions, while undirected graphs use edges that represent mutual connections without direction.

Explanation

Overview

A directed graph is a graph whose edges have orientations, whereas an undirected graph is a graph whose edges do not have orientations.

Key concepts

name: Core idea; description: The central focus of directed and undirected graphs is the capability described here: Directed and undirected graphs describe two different types of relationships. Directed graphs use edges with specific directions, while undirected graphs use edges that represent mutual connections without direction.; name: Problem context; description: Directed and Undirected Graphs is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using directed and undirected graphs, check its assumptions, input requirements, expected output, and resource constraints.

Example

scenario: A software feature needs to use directed and undirected graphs.; task: Design a small, testable solution that demonstrates directed and undirected graphs while satisfying the requirements described in this entry.; approach: Identify the input and expected output, apply the central idea of directed and undirected graphs, and trace the result with a small representative dataset.; learningPoint: This directed and undirected graphs example should be checked with ordinary inputs, boundary conditions, and a case that could expose an incorrect assumption.

Applications

Network analysis tasks that use directed and undirected graphs.; Dependency and infrastructure models requiring directed and undirected graphs.; Scheduling or resource-allocation workflows involving directed and undirected graphs.

Limitations

When applying directed and undirected graphs, verify graph-specific requirements such as edge-weight restrictions, direction rules, or capacity assumptions.; An implementation of directed and undirected graphs can fail if its boundary conditions, data representation, or required invariants are handled incorrectly.; For directed and undirected graphs, evaluate representative and unusually difficult inputs; a single small demonstration is not enough to establish reliability.

Common mistakes

Assuming every directed edge has a reverse edge.; Treating indegree and outdegree as interchangeable.; Ignoring direction when searching a directed graph.; Assuming an undirected relationship represents a one-way dependency.

Related concepts

Vertices and Edges; Weighted Graphs; Graph Connectivity; Directed Acyclic Graphs; Graph Traversal

Example or application

Scenario

A software feature needs to use directed and undirected graphs.

Task

Design a small, testable solution that demonstrates directed and undirected graphs while satisfying the requirements described in this entry.

Approach

Identify the input and expected output, apply the central idea of directed and undirected graphs, and trace the result with a small representative dataset.

Learning Point

This directed and undirected graphs example should be checked with ordinary inputs, boundary conditions, and a case that could expose an incorrect assumption.

Definition

A directed graph is a graph whose edges have orientations, whereas an undirected graph is a graph whose edges do not have orientations.

Directed Graph

Definition

A directed graph, also called a digraph, contains edges represented as ordered pairs of vertices.

Notation

(u, v)

Meaning

An edge (u, v) indicates a connection from vertex u to vertex v.

Direction

The direction of an edge matters. An edge from A to B does not automatically imply an edge from B to A.

Example Edges

    • A

    • B

    • B

    • C

    • C

    • A

Applications

  • One-way road networks

  • Website hyperlinks

  • Social media following relationships

  • Task dependencies

  • Data-flow relationships

Undirected Graph

Definition

An undirected graph contains edges represented as unordered pairs of vertices.

Notation

{u, v}

Meaning

An edge between A and B represents a mutual connection.

Direction

The relationship works in both directions.

Example Edges

    • A

    • B

    • B

    • C

    • A

    • C

Applications

  • Two-way road connections

  • Mutual friendships

  • Undirected communication links

  • Collaboration networks

  • Physical connection networks

Comparison

Edge Representation

Directed

Ordered pair (u, v)

Undirected

Unordered pair {u, v}

Edge Direction

Directed

Has a direction

Undirected

Has no direction

Adjacency

Directed

May not be symmetric

Undirected

Always symmetric

Vertex Degree

Directed

Uses indegree and outdegree

Undirected

Uses total degree

Edge Traversal

Directed

Must respect edge direction

Undirected

Can traverse an edge in either direction

Directed Degree

Indegree

Number of incoming edges.

Outdegree

Number of outgoing edges.

Formula

Total indegree = Total outdegree = Number of directed edges.

Undirected Degree

Definition

The number of edges incident to a vertex.

Formula

Σ deg(v) = 2|E|

Graph Variations

  • Directed acyclic graph (DAG)

  • Directed cyclic graph

  • Simple undirected graph

  • Multigraph

  • Pseudograph

Self Loops

A self-loop is an edge connecting a vertex to itself. Whether self-loops are permitted depends on the graph model.

Parallel Edges

Parallel edges are multiple edges connecting the same pair of vertices. They are allowed in multigraphs but not in simple graphs.

Algorithm Considerations

  • BFS and DFS follow the graph's edge directions when operating on directed graphs.

  • A directed graph may contain vertices that cannot reach one another.

  • An undirected graph's connected components describe mutually reachable groups.

  • Some algorithms require directed graphs, while others are designed for undirected graphs.

Common Mistakes

  • Assuming every directed edge has a reverse edge.

  • Treating indegree and outdegree as interchangeable.

  • Ignoring direction when searching a directed graph.

  • Assuming an undirected relationship represents a one-way dependency.

Real World Example

A social network can use a directed graph for following relationships because one person may follow another without being followed back. A mutual friendship network is better represented by an undirected graph.

Related Concepts

  • Vertices and Edges

  • Weighted Graphs

  • Graph Connectivity

  • Directed Acyclic Graphs

  • Graph Traversal

Key Concepts

NameDescription

Core idea

The central focus of directed and undirected graphs is the capability described here: Directed and undirected graphs describe two different types of relationships. Directed graphs use edges with specific directions, while undirected graphs use edges that represent mutual connections without direction.

Problem context

Directed and Undirected Graphs is relevant when a computational task requires the behavior or capability described by this topic.

Correct use

Before using directed and undirected graphs, check its assumptions, input requirements, expected output, and resource constraints.

Applications

  • Network analysis tasks that use directed and undirected graphs.

  • Dependency and infrastructure models requiring directed and undirected graphs.

  • Scheduling or resource-allocation workflows involving directed and undirected graphs.

Limitations

  • When applying directed and undirected graphs, verify graph-specific requirements such as edge-weight restrictions, direction rules, or capacity assumptions.

  • An implementation of directed and undirected graphs can fail if its boundary conditions, data representation, or required invariants are handled incorrectly.

  • For directed and undirected graphs, evaluate representative and unusually difficult inputs; a single small demonstration is not enough to establish reliability.

Practice Questions

QuestionAnswer

What is the main purpose of directed and undirected graphs?

Directed and undirected graphs describe two different types of relationships. Directed graphs use edges with specific directions, while undirected graphs use edges that represent mutual connections without direction.

What should be checked before applying directed and undirected graphs?

For directed and undirected graphs, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints.

How can an implementation of directed and undirected graphs be validated?

Trace a representative directed and undirected graphs case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline.

Learning Objectives

  • Explain the central idea and purpose of directed and undirected graphs.

  • Identify the assumptions, inputs, and conditions relevant to directed and undirected graphs.

  • Evaluate an application of directed and undirected graphs for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Scienexy Computer Science Reference

Suggest a correction or source · More in Algorithms & Data Structures