Please enable JavaScript.
Coggle requires JavaScript to display documents.
Mapa Mental 11 - Coggle Diagram
Mapa Mental 11
Graph
As we mentioned in the previous section, a graph is informally thought of as a collection of points in the plane called “vertices” or “nodes,”
-
-
-
-
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
Graphs for computer algorithms are usually repre-
sented in one of two ways: the adjacency matrix and adjacency lists.
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, in which the element in the ith row and the j th column is equal to 1 if there is an edge from the ith vertex to the j th vertex, and equal to 0 if there is no such edge.
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 (i.e., all the vertices connected to it by an edge).
Weighted Graphs
a graph (or di- graph) with numbers assigned to its edges. These numbers are called weights or costs.
Paths and Cycles
Among the many properties of graphs, two are important for a great number of applications: connectivity and acyclicity. Both are based on the notion of a path.
Depth-First Search
Depth-first search starts a graph’s traversal at an arbitrary vertex by marking it as visited. On each iteration, the algorithm proceeds to an unvisited vertex that is adjacent to the one it is currently in.
Breadth-First Search
If depth-first search is a traversal for the brave (the algorithm goes as far from “home” as it can), breadth-first search is a traversal for the cautious. It proceeds in a concentric manner by visiting first all the vertices that are adjacent to a starting vertex, then all unvisited vertices two edges apart from it, and so on, until all the vertices in the same connected component as the starting vertex are visited. If there still remain unvisited vertices, the algorithm has to be restarted at an arbitrary vertex of another connected component of the graph.
Topological Sorting
Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge u v, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG. For example, a topological sorting of the following graph is “5 4 2 3 1 0”. There can be more than one topological sorting for a graph. For example, another topological sorting of the following graph is “4 5 2 3 1 0”. The first vertex in topological sorting is always a vertex with in-degree as 0 (a vertex with no incoming edges).