flâneur

CS Academy

csacademy.com · 1,966 words · saved by 1 readers

Now that we've seen what graphs are and how we can represent them visually, we'll take a look on the ways we can write a program that uses them. We will present two methods of working with graphs and compare their advantages and disadvantages. Suppose we have a directed graph with 𝑁 N vertices. We can use 𝑁 ∗ 𝑁 N∗N binary matrix, where the element on row 𝑖 i and column 𝑗 j is 1 1 if the arc ( 𝑖 , 𝑗 ) (i,j) exists in the graph, and 0 0 otherwise. Below you can see a graph and its corresponding adjacency matrix: 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 Notice that in the example above the graph was directed, so each arc had a unique corresponding entry in the matrix. But what if the graph were undirected? How could it be represented using an adjacency matrix? The answer is simple, each edge ( 𝑖 , 𝑗 ) (i,j) will have two corresponding entries in the matrix, both cell ( 𝑖 , 𝑗 ) (i,j) and cell ( 𝑗 , 𝑖

Enter a valid username. This value may contain at most one consecutive separator( . or _ characters). Enter a valid username. This value may contain only letters,numbers and separators ( . or _ characters). Enter a valid username. This value may not start with a separator ( . or _ characters). Enter a valid username. This value may not end with a separator ( . or _ characters). Apasă butonul de mai jos pentru a deschide Codeforces (în altă fereastră), pentru a trimite codul: Puteți să vă autentificați folosind oricare din următoarele conturi de pe rețele sociale: Momentan nu aveți niciun cont

saved by

related reading