adjaatiomatriisi

Adjaatiomatriisi, also known as an adjacency matrix, is a square matrix used in graph theory to represent a finite graph. The elements of the matrix indicate whether pairs of vertices in the graph are adjacent or not.

In a simple graph, the adjacency matrix is a symmetric matrix where the entries are usually 0 or 1. Specifically, for a graph with n vertices, the adjacency matrix A is an n x n matrix where A[i][j] is 1 if there is an edge between vertex i and vertex j, and 0 otherwise. If the graph is undirected, the matrix is symmetric, meaning A[i][j] = A[j][i] for all i and j. For directed graphs, the matrix is not necessarily symmetric, as an edge from i to j does not imply an edge from j to i. In this case, A[i][j] = 1 means there is a directed edge from vertex i to vertex j.

The adjacency matrix can also be used to represent weighted graphs. In this variation, A[i][j] stores the weight of the edge between vertex i and vertex j. If there is no edge, the value is often set to infinity or a special sentinel value like 0, depending on the context and the algorithm being used.

Adjacency matrices are a fundamental tool for various graph algorithms, including finding shortest paths, checking connectivity, and analyzing graph properties. However, for very large or sparse graphs, they can consume a significant amount of memory compared to other representations like adjacency lists.