Please enable JavaScript.
Coggle requires JavaScript to display documents.
Graphs - Coggle Diagram
Graphs
Topological Sorting
A directed graph, or digraph for short, is a graph with directions specified for all its edges
tree edges
back edges
forward edges
cross edges
A directed cycle in a digraph is a sequence of three or more of its vertices that starts and ends with the same vertex and in which every vertex is connected to its immediate predecessor by an edge directed from the predecessor to the successor.
topological sorting.
if a DFS forest of a digraph has no back
edges, the digraph is a dag, an acronym for directed acyclic graph.
depth-first search (DFS)
depth-first search forest
tree edge
back edge
breadth-first search (BFS).
breadth-first search forest.
tree edge.
cross edge.
vertices
adjacent
to each other and that they are connected by the
undirected edge
incident
We call the vertices u and v endpoints of the edge (u, v) and say that u and v are incident to this edge; we also say that the edge (u, v) is incident to its endpoints u and v.
directed
If a pair of vertices (u, v) is not the same as the pair (v, u), we say that the edge (u, v) is directed from the vertex u, called the edge’s tail, to the vertex v, called the edge’s head.
Directed graphs are also
called digraphs.
Graph Representations Graphs for computer algorithms are usually repre-
sented in one of two ways: the adjacency matrix and adjacency lists.
adjacency matrix
The adjacency matrix of a graph with n vertices is an n × n boolean matrix with one row and one column for each of the graph’s vertices.
adjacency lists
The adjacency lists of a graph or a digraph is a collection of linked lists,
one for each vertex, that contain all the vertices adjacent to the list’s vertex
undirected
if every edge in it is undirected.
A weighted graph (or weighted digraph) is a graph (or di-graph) with numbers assigned to its edges. These numbers are called weights or costs.
weight matrix or cost matrix.
a graph is informally thought of as
a collection of points in the plane called “vertices” or “nodes,” some of them connected by line segments called “edges” or “arcs.”
the definition of a graph does not forbid loops, or edges connecting vertices
to themselves.
A graph with every pair of its vertices connected by an edge is called complete.
A graph with relatively few possible edges missing is called dense; a graph with few edges relative to the number of its vertices is called sparse.
A graph with no cycles is said to
be acyclic.
A graph is said to be connected if for every pair of its vertices u and v there
is a path from u to v.