[Slide 1]
Throughout this module, we have discussed key concepts and attributes of graphs. In this video, we will introduce another attribute or specific type of graph: directed graphs.
Directed graphs are graphs in which one or more edges have a direction. For example, we say that this edge goes from node A to node B. Up to this point, we have primarily seen directed graphs.
[Slide 2]
For example, trees are a type of directed graph. Recall that for trees, the direction of the edges were always pointing away from the root.
[Slide 3]
When talking about directed graphs, we should also discuss what it means to be an undirected graph. The term directed graph refer to graphs in which the edges have directions. The opposite of this is edges that don’t have a direction which we depict as an edge without an arrowhead.
In this example, we have an undirected edge. This means that we can traverse in both directions.
[Slide 4]
The previous graph with an undirected edge is equivalent to this graph with one edge from A to B and an edge from B to A.
[Slide 5]
Graphs can have a mix of directed and undirected edges. If the graph contains at least one edge, then it is considered to be a directed graph.
This graph is considered a directed graph. In this case, we can virtually go between any two nodes. The only exception is node E which has no outgoing edges.
In practice and real world applications, this would be referred to as a sink node. These can be used in circuitry and wiring diagrams when there is a component which only draws power and does not close the circuit.
[Slide 6]
In this video we officially defined directed graphs. For the most part up, we have dealt with directed graphs in the form of trees.
[Slide 7]
With the definition of directed graphs, we also examined what it meant to be undirected. When we have an undirected edge in our graph, this means that we can traverse to and from the nodes connected by the edge.