Directed Graphs (digraphs)

      edges -> arcs

{1,2} == {2,1}      (1,2) =/= (2,1)


(1,2) v1 is adjacent to v2
        v2 is adjacent from v1

indegree of v2
        ( number of arcs having v2 as tail)

outdegree of v1
        (number of arcs having v1 as head)

Weakly/Strongly connected

A digraph is strongly connected if every vertex is reachable from every other
A digraph is weakly connected if its underlying graph is connected.

Adjacency Matrix

adjacency list:
  v1 -> 2 -> 3
  v2 -> 4
  v3 -> 2
  v4 -> 3

Incidence Matrix:

Changes in Digraph ADT?

    IsAdjacentFrom(w,v) (v,w)
    IsAdjacentTo(v,w) head tail

    IsIncidentFrom(v,e) <--head
    IsIncidentTo(w,e) <--tail

    AdjacentToSet(v)
    AdjacentFromSet(v)

    IncidentFromSet(v)
    IncidentToSet(w)

    Arc(v,w) -->
    VerticesTo(e)
    VerticesFrom(e)

Return to CIS 350 Index Page