Graphs Flashcards
What is a graph
Is a data structure that connects items in an interconnected network.
Strengths of a graph
Representing links. Graphs are ideal for cases where you’re working with things that connect to other things. Nodes and edges could, for example, respectively represent cities and highways, routers and ethernet cables, or Facebook users and their friendships.
Weaknesses of a graph
Scaling challenges. Most graph algorithms are O(n*lg(n)) or even slower. Depending on the size of your graph, running algorithms across your nodes may not be feasible.
Directed graph
Directed graphs have edges with direction. The edges indicate one-way relationship, in that edge can only be traversed in a single direction.
Undirected graph
Undirected graphs have edges that do not have a direction. The edges indicates a two-way relationship, in that each edge can be traversed in both directions.
Cyclic graph
Is a graph that has a cycle - an unbroken series of nodes with no repeating node or edges that connects back to itself.
Acyclic graph
Is a graph without cycles
Weighted graph
Is a graph where each edge has a “weight”. The weight could, for example, represent distance between two locations.
Unweighted graph
is a graph where each edge has not “weight”
Graph coloring
Is when you assign colors to each node in a graph
Legal coloring
Means that no adjacent nodes have the same color
Ilegal coloring
Means that some nodes have adjacent nodes with same color
Possible representations for graphs
- Edge list
- Adjacency list
- Adjacency matrix
Common algorithms for Graphs
- Breath-first search (BFS)
- Depth-first search (DFS)
Some graph algorithms
- Dijkstra’s Algorithm
- Topological Sort
- Minimum Spannin tree
