-
Notifications
You must be signed in to change notification settings - Fork 1
Home
We use graphs to represent connections between objects, that is, if we have a set of objects related to each other, then can represent them using graphs. Some applications of graph algorithms are on the internet, navigation software such as GPS as google maps, social networks, and packet routing protocols.
A lot of programming problems are solved by modeling the problem as a graph problem after which we apply an appropriate graph algorithm
A graph is composed of nodes and edges A path is an edge or a collection of edges from a source to a destination. In this visualization, we assume that all nodes have edges between them. The length of a path is the total of the length of all edges within that path.
A cycle exists if the first and last nodes in a path are the same. For example, we could have the following path: a -> b -> c -> d -> a. Here we start from node a and end at the same node. We say that a path is simple if each node in the path appears only once.
We say that a graph is connected if there exists a path between any two nodes in the graph. The parts of a connected graph are referred to as components A tree is a graph that is connected whereby there exists a unique path between every node in the tree. Edges An edge in a graph has two aspects to it. The first is the direction, it can be directed or undirected. Secondly, it can be weighted or unweighted.
A graph can be either directed or undirected. A directed graph has edges with directions meaning we can only traverse the graph in one direction. As an example, we look at two social networks. The first is Facebook, this is a practical example of an undirected graph whereby if party A is a friend of party B, then they are both mutual friends. This however is not the case for a social network such as Twitter, party A can follow party B but this does not mean party B automatically follows party A.
The edges in a graph can also have weights. A graph can either be weighted or unweighted. If weighted, each edge has a numerical value attached to it. This value can be negative or positive. In a practical example, weights can be the distance between two cities in the case of GPS navigational software or the cost. Such a model can be used to determine the shortest or cheapest path between two nodes. Unweighted graph practical examples. Unweighted graphs can also have weights but in such cases, the magnitude of a relationship between two nodes might be hard to determine Other graphs. We can use the two discuss graph aspects, that is weights and direction to derive four more types of graphs. These are:
- Directed and weighted
- Directed and unweighted.
- Undirected and weighted.
- Undirected and unweighted.
We say that two nodes are neighbors if there is an edge connecting them. The degree of a node is the number of neighbors the node has. The sum of degrees in a graph is always2x where x is the number of edges in the graph. This goes to show that the sum of degrees will always be an even number. We also have indegree which is the number of edges that end in a particular node and outdegree which is the number of edges that originate from a particular node.
We assign different colors to graphs such that no node in the graph has the same color. A chromatic number X(G) of a graph is the minimum number of colors where each node in the graph has a distinct color. We also have edge coloring where edges have distinct colors.
The following are applications of graph coloring:
- Register allocation in compiler design -> this is an optimization problem where we try to allocate a large number of variables to a limited number of registers.
- Map coloring whereby no two adjacent/neighboring countries have the same color.
- Checking if a graph is bipartite whereby if it can be colored using two colors it is bipartite, otherwise it is not.
- Mobile radio frequency assignment - When we assign frequencies to cell towers, we want to make sure that they are different for towers that are close to each other. Here we want to answer the question, What are the minimum number of frequencies needed to cover a whole region with the minimum cost.
How do we represent graphs in algorithms? There are three common ways. These are;
- Adjacency List, Here each node is assigned a list of adjacent nodes. That is, each node x has a list with all nodes adjacent to x.
- Adjacency Matrix, This is a 2D matrix that indicates edges contained in a graph.
- Edge List, Here we just list all edges in the graph. Here are the computational complexities of the three graph representations.
We use two well know algorithms to traverse graphs. These are Depth-first search and Breadth-first search algorithm
Here we select a starting node or are given a starting node and explore it fully, as 'deep' as possible before moving to the next. When done exploring the starting node, it goes to the next node and repeats this until the whole graph is explored.
Given a starting node, we explore the graph in increasing order of the distance from the starting node. This means that each node's distance is the distance from the starting node. We go level by level exploring a level before moving to the next until the whole graph is explored, we can compare it to a forest fire, it burns all things close to it and expands until the whole forest is burned.
Finding the shortest path from a source to the destination node is a problem with many applications. In this type of problem, we want to know the path from the source node to the destination node that gives us the minimum cost. We can solve such a problem using a breadth-first search assuming all edges weigh 1. If edges have different weights we need another algorithm. Common algorithms we use to solve this problem are bellman-ford algorithm Dijkstra's algorithm and Floyd-warshall algorithm
This algorithm finds the shortest path from the source node to all other nodes in the graph in a weighted graph. It is slower than Dijkstra's algorithm but can handle a graph with negative weights. It uses a relaxation principle whereby the shortest distance is gradually replaced with a more accurate value until an optimal solution is obtained. Dijkstra's algorithm. This is also used to find the shortest path. It has many variants one is finding the shortest path between two nodes, and another is finding the shortest path from the source node to all other nodes in the graph.
This is another shortest path algorithm that finds the shortest path in a directed weighted graph that has both positive and negative weights. The graph should also not have negative weight cycles.