Scribd
Upload
12 views3 pages

Graph Data Structure

A graph is a data structure consisting of vertices and edges that define relationships between the vertices. Graphs can be directed or undirected, and terminology includes paths, adjacent nodes, and complete graphs. Graph traversal can be performed using Depth-First Search (DFS) or Breadth-First Search (BFS) algorithms.

Uploaded by

mekdim292
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
12 views3 pages

Graph Data Structure

A graph is a data structure consisting of vertices and edges that define relationships between the vertices. Graphs can be directed or undirected, and terminology includes paths, adjacent nodes, and complete graphs. Graph traversal can be performed using Depth-First Search (DFS) or Breadth-First Search (BFS) algorithms.

Uploaded by

mekdim292
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Graph Data Structure

What is a graph?
A data structure that consists of a set of nodes (vertices) and a set of edges that
relate the nodes to each other. The set of edges describes relationships among the
vertices.

F
ormal Definition of Graph
A graph G is defined as follows:
G=(V,E)
V(G): a finite, nonempty set of vertices
E(G): a set of edges (pairs of vertices)

Directed vs. undirected graphs


* When the edges in a graph have no direction, the graph is called undirected

* When the edges in a graph have a direction, the graph is called directed (or digraph)
Warning: if the graph is directed, the order of the vertices in each edge is important !!

Graph Terminology
- Path: a sequence of vertices that connect two nodes in a graph
- Adjacent nodes: two nodes are adjacent if they are connected by an edge

5 is adjacent to 7
7 is adjacent from 5
- Complete graph: a graph in which every vertex is directly connected to every other
vertex
What is the number of edges in a complete directed graph with N vertices?
N * (N-1)

What is the number of edges in a complete undirected graph with N vertices?


N * (N-1) / 2

Weighted graph: a graph in which each edge carries a value


Graph Traversing
1. Depth-First-Search (DFS)
What is the idea behind DFS?
Travel as far as you can down a path
Back up as little as possible when you reach a "dead end" (i.e., next vertex has been
"marked" or there is no next vertex)
DFS can be implemented efficiently using a
stack
Algorithm for DFS
Set found to false
stack.Push(startVertex)
DO
stack.Pop(vertex)
IF vertex == endVertex
Set found to true
ELSE
Push all adjacent vertices onto stack
WHILE !stack.IsEmpty() AND !found
IF(!found)
Write "Path does not exist"

2. Breadth-First-Search (BFS)
What is the idea behind BFS?
Look at all possible paths at the same depth before you go at a deeper level
Back up as far as possible when you reach a "dead end" (i.e., next vertex has been
"marked" or there is no next vertex)
BFS can be implemented efficiently using a queue
Algorithm for BFS
Set found to false
queue.Enqueue(startVertex)
DO
queue.Dequeue(vertex)
IF vertex == endVertex
Set found to true
ELSE
Enqueue all adjacent vertices onto queue
WHILE !queue.IsEmpty() AND !found
IF(!found)
Write "Path does not exist

You might also like