Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

algorithms > graphs > Flashcards

graphs Flashcards

1
Q

what is graph

A

A Graph is a data structure which consists of a set of vertices, and a set of edges that connect (some of) them or all of them

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

G = ( V, E )

A

G graph
v= set of vertices
E=set of edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

graphs application in general

A

1-0 computer networks
2- electrical circut
3-road maps

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

graphs uses in computer sciences

A

1-Social network (Facebook, LinkedIn)
2-Computer networks
3-Transportation network
4-Wireless sensors

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Graph Categorization

A

1-➢ A Directed Graph or Digraph is a graph where each edge has a direction
The edges in a digraph are called Arcs or Directed Edges
.
2-➢ An Undirected Graph is a graph where the edges have no directions
The edges in an undirected graph are called Undirected Edges

3-A Weighted Graph is a graph where all the edges are assigned weights.

4-multi graph If the same pair of vertices have more than one edge, that graph is called

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

when do we call a graph multi-graph

A

If the same pair of vertices have more than one edge, that graph is called multi-graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

a dircted graph :
(1, 4) = 1→4 where ….. is the tail and …… is the head vertics

A

1 and 4

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

name of edges in dircted and undircted graphs

A

The edges in a digraph are called Arcs or Directed Edges

the edges in undircted graph are called Undirected Edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

what is digraph

A

dircted graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

graph terminoalgy define all below
1- adjacent vertices
2-incidents
3-loop or(……complete)
4-simple graph

A

1- they are called adjecnt when theere is edge that connects thm like (1,4)
2-where there is edge like (1,4)its called an incident
3-loop or self edge when there is an edge thats connected to itself like (4,4) in the last graph
4- A graph that is undirected and does not have any loops or multiple edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

graph terminoalgy(part2) define all below
1-path
2-reachable vertices
3-simple bath

A

1-path : sequnce of edges in the graph
2-its reachable if there was a path between the two vertices
3-simple path is path where each node is visted once

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

graph terminoalgy part 3
define whats below
1-length
2-circut
3-cycle

A

length : sum of the lengtrh of the edges on the path
Circuit: A path whose first and last vertices are the same.
➢➢ The path 3,2,1,4,5,3 is a circuit
➢ Cycle: A circuit where all the vertices are distinct except for the first (and the last) vertex.
➢➢ 1,4,5,3,1 is a cycle, but 1,4,5,4,1 is not a cycle.
➢ Hamiltonian Cycle: A Cycle that contains all the vertices of the graph.
➢➢ 1,4,5,3,2,1 is a Hamiltonian Cycle.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

T or F: there can be morew than one path between two vertices

A

T

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

graph terminoalgy part 4
define whats below
1-degree of the vertics
2-in-degree
3-out-degree
4-subgraph
5connected graph

A

1- degree in undircted graph is the number of edges or incicdents
2-in-degree in DIgraph the number of edges entering the vertex
3-out degree the number of edges leaving the vertex
4-sub graph ➢ A Subgraph of graph G=(V,E) is a graph H=(U,F) such that U Є V and F Є E
5-A graph is said to be Connected if there is at least one path from every vertex to every other vertex in the graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

what is the subgraph of this graph

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

graph terminoalgy (Last part)
1- connected graph
2- tree
3-forest

A

1-connected graph : if there was at least one path between every vertex in the graph
2-tree :Connected Undircted graph that contains no cycle
3-forest: graph that dose not contain a cycle

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

is this a forest or tree and why

A

its forest since tree needs to be connected

17
Q

The Spanning Tree of a Graph G is a …………………

A

subgraph of G that is a tree and contains all the vertices of G.

18
Q

The Adjacency Matrix A=(ai,j) of a graph G=(V,E) with n nodes is an ……. matrix
Each element of A is either ……, depending on the adjacency of the nodes

A

➢➢ The Adjacency Matrix A=(ai,j) of a graph G=(V,E) with n nodes is an nXn matrix
➢➢ Each element of A is either 0 or 1, depending on the adjacency of the nodes

19
Q

➢ Example: Find the adjacency matrices of the following graphs.

A
20
Q
A
21
Q
A
22
Q

how to draw Adjacency Matrix of a Weighted Graph

A

➢➢ The weight of the edge can be shown in the matrix when the vertices are adjacent
➢➢ A nil value (0 or ∞) depending on the problem is used when they are not adjacent

23
Q

➢➢ |Draw the matrix for this graph

A
24
Q

a graph can be a set of …..

A

trees

24
Q

how to build a tree on the graph

A

Pick a vertex as the root
Choose certain edges to produce a tree
Note: might also build a forest if graph is not connected

24
Q

goal of graph searching is
BFS
DFS

A

methodically explore every vertex and every edge

24
Q

what is ➢ Adjacency List

and what happens to ➢ Adjacency List
in wighted graphs

A

➢➢ An Adjacency list is an array of lists, each list showing the vertices a given vertex is adjacent to.

in weighted graph its included in the list

25
Q

how to do Breadth first Search (BFS)

A

“Explore” a graph
■ One vertex at a time.
■ Expand frontier of explored vertices across the breadth of the frontier.
Associate vertex with “colors” to guide the algorithm
■ White vertices have not been discovered
All vertices start out white
.
■ Grey vertices are discovered but not fully explored
They may be adjacent to white vertices
.
Black vertices are discovered and fully explored
They are adjacent only to black and gray vertices
.
Explore vertices by scanning adjacency list of grey vertices

26
Q

write pusodocode for BFS

A
26
Q

what kind of queue is implemented in bfs

A

FIFO

27
Q

analysis of BFS

A

The operations of enqueuing and dequeuing take O(1) time. So the total time devoted to queue operations is O(V).
Because the adjacency list of each vertex is scanned only when the vertex is dequeued, each adjacency list is scanned at most once.
Since the sum of the lengths of all the adjacency lists is Θ(E), the total time spent in scanning adjacency lists is O(E).
The overhead for initialization is O(V), and thus the total
running time of BFS is O(V + E).
Thus breadth-first search runs in time linear in the size of the adjacency-list representation of G.

28
Q

BFS: Properties

A

BFS calculates the shortest-path distance to the source node
Shortest-path distance δ(s,v) = minimum number of edges from s to v, or ∞ if v not reachable from s.
.
BFS builds breadth-first tree, in which paths to root represent shortest paths in G.
Thus can use BFS to calculate shortest path from one vertex to another in O(V+E) time.

29
Q

what type of search :Edges are explored out of the most recently discovered vertex v that still has unexplored edges.

A

DFS

29
Q

which search algo Expand deepest unexpanded node.

A

DFS

30
Q

DFS charsterstics

A

1-It searches deeper the graph when possible
2-Edges are explored out of the most recently discovered vertex v that still has unexplored edges.
3-When all of vʼs edges have been explored, backtrack to the vertex from which v was discovered.
4-Also records timestamps for each vertex
d[v] when the vertex is first discovered
f[v] when the vertex is finished
5-Vertices go through white, gray and black stages of color.
2 in other words: Starts at the selected node and explores as far as possible along each branch before backtracking.

31
Q

how is space complextiy in BFS compared to DFS and what is the time complexty in both

A

Space complexity of DFS is lower than that of BFS.
Time complexity of both is same – O(|V|+|E|).

.
Diffrent space complexity same time complexity

31
Q

BFS and DFS - comparisons

A

BFS produces a single tree that includes all vertices reachable from s.
DFS may produce multiple trees, forming a forest. This is because DFS explores as far as possible along a branch before backtracking, and disconnected components are treated as separate trees.

both can generate MST

32
Q

which (search) algorthim can produce minmum spanning tree

A

BFS and DFS both are able to generate MST

33
Q

write psuodocode for DFS algorthim

A
34
Q

what is Strongly Connected Components

A

algorithms (5 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions