Reading 35

Graphs

Graphs are non-linear data structures containing nodes, connected by edges.

1. Vertex - ‘node’, the data object
2. Edge - connection between vertices
3. Neighbor - adjacent node
4. Degree - number of edges connected to a vertex

Directed vs Undirected

Undirected

A graph where each edge is uni-directional or bi-directional. This means the edges do not POINT toward a particular direction.

Directed

Also called a Digraph, a directed graph contains edges which all point to a particular direction or node.

Complete, Connected, Disconnected

Complete - all nodes are connected with each other.

Connected - all nodes have at least one edge.

Disconnected - Some nodes may not be connected.

Cyclic vs Acyclic

Cyclic graphs can be traversed and arrive back where they started. Acyclic graphs have no cycles.

Adjacency Matrix

A two dimensional array that represents the connections between nodes. 0 means no connections. 1 represents a present connection.

Traversal

Breadth First

1. Enqueue the start node
2. Create while loop (while node: )
3. Dequeue first node
4. If dequeued node has unvisited children, add children to visited and insert into queue

ALGORITHM BreadthFirst(vertex)
    DECLARE nodes <-- new List()
    DECLARE breadth <-- new Queue()
    DECLARE visited <-- new Set()

    breadth.Enqueue(vertex)
    visited.Add(vertex)

    while (breadth is not empty)
        DECLARE front <-- breadth.Dequeue()
        nodes.Add(front)

        for each child in front.Children
            if(child is not visited)
                visited.Add(child)
                breadth.Enqueue(child)   

    return nodes;

Depth First

1. Push root into stack
2. While stack not empty:
3. Peek stack
4. If top node has unvisited children, mark top as visited and push unvisited children back into stack
5. If top has 0 unvisited children, Pop stack
6. Repeat until empty

source: https://codefellows.github.io/common_curriculum/data_structures_and_algorithms/Code_401/class-35/resources/graphs.html