Graphs

Question 1

What are graphs?

Answer 1

A general, non-linear data structure consisting of nodes (vertices) and edges between nodes.
G = (V, E)

Question 2

Undirected Graph

Answer 2

There is no order to how the edges connect vertices.

Question 3

Directed Graph

Answer 3

Each edge has a source vertex and target vertex.

Question 4

Loop

Answer 4

An edge that connects a vertex to itself.

Question 5

Path

Answer 5

A sequence of vertices such that each adjacent pair of vertices are connected by an edge.

Question 6

Cycle

Answer 6

A simple path with no repeated vertices or edges other than the starting and ending vertices.

Question 7

Directed Cycle

Answer 7

A cycle in a directed graph.

Question 8

Weighted Graph

Answer 8

Has values on its edges.

Question 9

Connected Graph

Answer 9

A graph that has a path between every pair of distinct vertices.

Question 10

Complete Graph

Answer 10

A graph that has an edge between every pair of distinct vertices.

Question 11

Disconnected Graph

Answer 11

Any graph that lacks a path between at least one pair of vertices.

Question 12

Adjacent Vertices

Answer 12

Undirected: joined by an edge.
Directed: A is adjacent to B if the edge begins at B and ends at A.

Question 13

Max # of edges (undirected)

Answer 13

n(n-1)/2

Question 14

Max # of edges (directed)

Answer 14

n(n-1)

Question 15

Adjacency Matrix

Answer 15

Array implementation of ADT graph. A square (n x n) grid of true/false values representing edges of the graph.

Question 16

Adjacency List

Answer 16

List implementation of ADT graph.

Question 17

Adjacency Matrix Implementation

Answer 17

2-D array of Booleans. True = edge exists between vertex i to vertex j, otherwise false.

Question 18

Adjacency List Implementation

Answer 18

Directed: n linked lists represent the edges of n vertices.