Please enable JavaScript.
Coggle requires JavaScript to display documents.
Graphs, depth-first search (DFS) and breadth-first search (BFS).,…
Graphs
Definição
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.”
adjacent
we say that the vertices (u) and (v) are adjacent when they are conected to each other and that they are connected by the undirected edge
endpoints
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) to the vertex (v). A graph whose every edge is directed is called directed
Graph Representations
Graphs for computer algorithms are usually represented in one of two ways: the adjacency matrix and adjacency lists.
Weighted Graphs
A weighted graph is a graph with numbers assigned to its edges. These numbers are called weights or costs.
Paths and Cycles
A path from vertex u to vertex v of a graph G can be defined as a sequence of adjacent vertices that starts with u and ends with v.
-
topological sorting
In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.
For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks.