Graphs and graph theory in computer science![]() By Alex Allain What is a graph?![]() Why are graphs useful? ![]() Another reason for using graphs is that many problems computers are used to solve involve representing relationships between objects, places, or concepts. Because graphs can be either directed or undirected, they are a flexible method of showing connections. For instance, you can describe who knows whom in a room as a collection of nodes, each representing a person, and directed edges, each representing that one person knows another. Because graphs are so often used and because they allow the representation of many problems in computer science, such as the Traveling Salesman Problem or something as simple as the relationships between people in a room, they are a convenient means of expressing problems with which many people are comfortable. This familiarity simplifies the process of creating mental models of problems, which ultimately leads to better problem solving. What are some important graph theory terms? Directed Graph: A directed graph is one in which edges connect nodes in only one direction. Undirected Graph: An undirected graph is one in which edges connect nodes bidirectionally (in both directions). Node: A node, usually drawn as a circle, represents an item that can be related to other items or nodes. Nodes are sometimes referred to as vertices. Edge: An edge represents a connection between nodes. Edges can be either directed or undirected, depending on the type of graph. Edges can also have weights, which may correspond to strength of relationship or distance between edges. (For instance, if a graph represents a map, then the weights of each edge will represent the distance between two nodes.) Connected: A graph is connected if from any node you can reach any other node. Disconnected: A graph is disconnected if certain groups of nodes form an island that has no connection to the rest of the graph. Related Articles Dijkstra's Algorithm for Finding Shortest Paths in Non-Negative Weight Graphs |