Graph-terminology.pptx

graph terminology , MFC

1. GRAPH-TERMINOLOGY

2. CONTENTS: 1.Overview of Graphs in Data Structure 2. Graph Terminologies in Data Structure 3. Types of Graphs in Data Structure

3. Overview of Graphs in Data Structure Let us understand what is a graph in the data structure. Graphs are non-linear data structures that are made up of a set of nodes (or vertices), connected by edges (or arcs). Nodes are entities where the data is stored and their relationships are expressed using edges. Edges may be directed or undirected. Graphs demonstrate complicated relationships with ease and are used to solve many real-life problems.

4. For example, Facebook uses a graph data structure that consists of a group of entities and their relationships. On Facebook, every user, photo, post, page, place, etc. that has data is represented with a node. Every edge from one node to another represents their relationships, friendships, ownerships, tags, etc. Whenever a user posts a photo, comments on a post, etc., a new edge is created for that relationship. Both nodes and edges have meta-data associated with them.

5. Graph Terminologies in Data Structure: Vertex               Every individual data element is called a vertex or a node. In the above image, A, B, C, D & E are the vertices. Edge (Arc)            It is a connecting link between two nodes or vertices. Each edge has two ends and is represented as starting Vertex , ending Vertex . 5

6. Directed Edge It is a unidirectional edge. Weighted Edge An edge with value (cost) on it. Degree The total number of edges connected to a vertex in a graph. Indegree The total number of incoming edges connected to a vertex. Outdegree The total number of outgoing edges connected to a vertex. Self-loop An edge is called a self-loop if its two endpoints coincide with each other. Adjacency Vertices are said to be adjacent to one another if there is an edge connecting them

7. Types of Graphs in Data Structure The most common types of graphs in the data structure are mentioned below:

8. DIRECTED - GRAPH A directed graph (or digraph) is a set of vertices and a collection of directed edges that each connects an ordered pair of vertices. We say that a directed edge points from the first vertex in the pair and points to the second vertex in the pair. We use the names 0 through V-1 for the vertices in a V-vertex graph.

9. UNDIRECTED-GRAPH An undirected graph is  graph , i.e., a set of objects (called vertices or nodes) that are connected together, where all the edges are bidirectional. An undirected graph is sometimes called an undirected  network . In contrast, a graph where the edges point in a direction is called a  directed graph . When drawing an undirected graph, the edges are typically drawn as lines between pairs of nodes, as illustrated in the following figure.

10. WEIGHTED-GRAPH In many applications, each edge of a graph has an associated numerical value, called a weight. Usually, the edge weights are nonnegative integers. Weighted graphs may be either directed or undirected. The weight of an edge is often referred to as the "cost" of the edge. In applications, the weight may be a measure of the length of a route, the capacity of a line, the energy required to move between locations along a route, etc.

11. WEIGHTED GRAPH It is not mandatory in a weighted graph that all nodes have distinct weight, i.e. some edges may have same weights.

12. UNWEIGHTED-GRAPH

13. UNWEIGHTED GRAPH Advantages of Unweighted Graph: Unweighted graphs can be used to implement tree data structures. Unweighted graphs are used in many algorithms like DFS and BFS. Helps in optimal visualization of interrelated problems which are not related in terms of magnitude.  Disadvantages: The unweighted graphs do not have edge weight. Hence, cannot be used for shortest path evaluation or applications which require the distance between the nodes.