|
Arabic
Bengali
Chinese
English
French
German
Hebrew
Hindi
Italian
Japanese
Korean
Malay
Polish
Portuguese
Spanish
Turkish
Ukrainian
Vietnamese|
Lecture notes, cheat sheets
Computer science and information technology. Object data type (lecture notes)
Directory / Lecture notes, cheat sheets Table of contents (expand) LECTURE No. 10. Counts 1. The concept of a graph. Ways to represent a graph A graph is a pair G = (V,E), where V is a set of objects of an arbitrary nature, called vertices, and E is a family of pairs ei = (vil, vi2), vijOV, called edges. In the general case, the set V and/or the family E may contain an infinite number of elements, but we will consider only finite graphs, that is, graphs for which both V and E are finite. If the order of the elements included in ei matters, then the graph is called directed, abbreviated - digraph, otherwise - undirected. The edges of a digraph are called arcs. In what follows, we assume that the term "graph", used without specification (directed or undirected), denotes an undirected graph. If e = , then the vertices v and u are called the ends of the edge. Here we say that the edge e is adjacent (incident) to each of the vertices v and u. Vertices v and and are also called adjacent (incident). In the general case, edges of the form e = ; such edges are called loops. The degree of a vertex in a graph is the number of edges incident to that vertex, with loops being counted twice. Since each edge is incident to two vertices, the sum of the degrees of all vertices in the graph is equal to twice the number of edges: Sum(deg(vi), i=1...|V|) = 2 * |E|. A node's weight is a number (real, integer, or rational) assigned to a given node (interpreted as cost, throughput, etc.). Weight, edge length - a number or several numbers that are interpreted as length, bandwidth, etc. A path in a graph (or a route in a digraph) is an alternating sequence of vertices and edges (or arcs in a digraph) of the form v0, (v0,v1), v1..., (vn - 1,vn), vn. The number n is called the path length. A path without repeating edges is called a chain; a path without repeating vertices is called a simple chain. The path can be closed (v0 = vn). A closed path without repeating edges is called a cycle (or contour in a digraph); without repeating vertices (except for the first and last) - a simple loop. A graph is called connected if there is a path between any two of its vertices, and disconnected otherwise. A disconnected graph consists of several connected components (connected subgraphs). There are various ways to represent graphs. Let's consider each of them separately. 1. Incidence matrix. This is a rectangular matrix of dimension n x n, where n is the number of vertices, am is the number of edges. The values of the matrix elements are determined as follows: if the edge xi and the vertex vj are incident, then the value of the corresponding matrix element is equal to one, otherwise the value is zero. For directed graphs, the incidence matrix is constructed according to the following principle: the value of the element is equal to - 1 if edge xi comes from vertex vj, equal to 1 if edge xi enters vertex vj, and equal to XNUMX otherwise. 2. Adjacency matrix. This is a square matrix of dimensions n x n, where n is the number of vertices. If vertices vi and vj are adjacent, that is, if there is an edge connecting them, then the corresponding matrix element is equal to one, otherwise it is equal to zero. The rules for constructing this matrix for directed and undirected graphs are no different. The adjacency matrix is more compact than the incidence matrix. It should be noted that this matrix is also very sparse, but in the case of an undirected graph it is symmetrical with respect to the main diagonal, so you can store not the entire matrix, but only half of it (a triangular matrix). 3. List of adjacencies (incidents). It is a data structure that stores a list of adjacent vertices for each graph vertex. The list is an array of pointers, the i-th element of which contains a pointer to the list of vertices adjacent to the i-th vertex. An adjacency list is more efficient than an adjacency matrix because it eliminates the storage of null elements. 4. List of lists. It is a tree-like data structure in which one branch contains lists of vertices adjacent to each of the graph vertices, and the second branch points to the next graph vertex. This way of representing the graph is the most optimal. 2. Representation of a graph by an incidence list. Graph Depth Traversal Algorithm To implement a graph as an incidence list, you can use the following type: TypeList = ^S; S=record; inf: Byte; next : List; end; Then the graph is defined as follows: Var Gr : array[1..n] of List; Now let's turn to the graph traversal procedure. This is an auxiliary algorithm that allows you to view all the vertices of the graph, analyze all information fields. If we consider a graph traversal in depth, then there are two types of algorithms: recursive and non-recursive. With the recursive depth-first traversal algorithm, we take an arbitrary vertex and find an arbitrary unseen (new) vertex v adjacent to it. Then we take the vertex v as not new and find any new vertex adjacent to it. If some vertex does not have newer unseen vertices, then we consider this vertex to be used and return one level higher to the vertex from which we got to our used vertex. The traversal continues in this way until there are no new unscanned vertices in the graph. In Pascal, the depth-first traversal procedure would look like this: Procedure Obhod(gr : Graph; k : Byte); Var g : Graph; l:List; Begin nov[k] := false; g := gr; While g^.inf <> k do g := g^.next; l := g^.smeg; While l <> nil do begin If nov[l^.inf] then Obhod(gr, l^.inf); l := l^.next; End; End; Note In this procedure, when describing the Graph type, we meant the description of a graph by a list of lists. Array nov[i] is a special array whose i-th element is True if the i-th vertex is not visited, and False otherwise. A non-recursive traversal algorithm is also often used. In this case, recursion is replaced by a stack. Once a vertex has been viewed, it is pushed onto the stack, and it becomes used when there are no more new vertices adjacent to it. 3. Representation of a graph by a list of lists. Breadth Graph Traversal Algorithm A graph can be defined using a list of lists as follows: TypeList = ^Tlist; tlist=record inf: Byte; next : List; end; Graph = ^TGpaph; TGpaph = record inf: Byte; smeg:List; next: Graph; end; When traversing the graph in breadth, we select an arbitrary vertex and look through all the vertices adjacent to it at once. A queue is used instead of a stack. The breadth-first search algorithm is very handy for finding the shortest path in a graph. Here is a procedure for traversing a graph in width in pseudocode: Procedure Obhod2(v); {values spisok, nov - global} Begin queue = O; queue <= v; nov[v] = False; While queue <> O do Begin p <= queue; For u in spisok(p) do If new[u] then Begin nov[u] := False; queue <= u; End; End; End; Author: Tsvetkova A.V. << Back: Counts (The concept of a graph. Methods of representing a graph. Representation of a graph by a list of incidences. Depth-first traversal algorithm for a graph. Representation of a graph as a list of lists. Breadth-first traversal algorithm for a graph) >> Forward: Methods (Methods. Constructors and destructors. Destructors. Virtual methods. Object data fields and formal method parameters)
▪ Materials Science. Lecture notes ▪ Traumatology and orthopedics. Lecture notes ▪ State and municipal administration. Crib
The existence of an entropy rule for quantum entanglement has been proven
09.05.2024 Mini air conditioner Sony Reon Pocket 5
09.05.2024 Energy from space for Starship
08.05.2024
▪ Miniature efficient acoustic amplifier ▪ The reaction to a cigarette depends on the ideas about its composition.
▪ section of the site for those who like to travel - tips for tourists. Article selection ▪ article Crystal dream of my childhood. Popular expression ▪ article Which bird holds the record for diving depth? Detailed answer ▪ article Deputy General Director. Job description ▪ article Hidden message. Focus Secret
Home page | Library | Articles | Website map | Site Reviews
www.diagram.com.ua |
We recommend interesting articles Section 
See other articles Section 
Latest news of science and technology, new electronics:
All languages of this page