Please enable JavaScript.
Coggle requires JavaScript to display documents.
Graphs, a - Coggle Diagram
Graphs
Definitions
A graph is a collection of nodes (vertices), some of them connected by edges (arcs). G = (V, E), where V is a finite nonempty set of items called vertices and E is a set of pairs of theses items called edges.
Path
The length of a path is the total number of vertices in the vertex sequence defining the path minus 1, which is the same as the number of edges in the path.
A path from vertex u to vertex v of a graph G can be defined as a sequence of adjacent (connected by an edge) vertices that starts with u and ends
with v. If all vertices of a path are distinct, the path is said to be simple.
A directed path is a sequence of vertices in which every consecutive pair of the vertices is connected by an edge directed from the vertex listed first to the vertex listed next.
Cycle
A cycle is a path of a positive length that starts and ends at the same vertex and does not traverse the same edge more than once. A graph with no cycles is said to be acyclic.
Connected Graph
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.
A connected component is a maximal (not expandable by including another vertex and an edge) connected subgraph of a given graph.
-
-
Weighted Graphs
A weighted graph (or weighted digraph) is a graph (or digraph) with numbers assigned to its edges. These numbers are called weights or costs.
-
Graph Traversal
DFS
Depth-first search (DFS) 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. This process continues until a dead end (a vertex with no adjacent unvisited vertices)
is encountered. At a dead end, the algorithm backs up one edge to the vertex it came from and tries to continue visiting unvisited vertices from there. The
algorithm eventually halts after backing up to the starting vertex, with the latter being a dead end.
-
BFS
Breadth-first search (BFS) 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.
-
-
If a graph tends to be a dense graph it better to represent it using a matrix, but if a graph tends to be a sparse graph is better to represent it using a list.
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).
-
Operations
-
-
-
int next(G g, int v, int w);
-
void setEdge(G g, int i, int j, int wt);
-
void delEdge(G g, int i, int j);
-
boolean isEdge(G g, int i, int j);
-
int weight(G g, int i, int j);
-
void setMark(G g, int v, int val);
-
int getMark(G g, int v);
Retorna a marca de um vértice v do grafo G, para saber se ele foi visitado ou não
-