Flashcards
Graphs
Cards in this deck (18)
- 1define a graphA graph contains a set nodes. Each node has a reference to other nodes. For graphs, a reference from one node to another is called an edge.
The edges E in a graph is a set of ordered pairs of vertices. - 2directed vs undirected graphWhen the ordering of the vertices in an edge is important, we say that we have a directed graph.
graphs in which the edges do not have “arrows": undirected graph. - 3define outgoing vs incoming edges from vset of edges of the form (v;w) in E where w in V vs set of edges of the form (w; v) in E where w in V
- 4define in-degree of v vs out-degree of vnumber incoming edges to v vs number outgoing edges from v
- 5define path cyclepath: a sequence of vertices (v1;... ; vm) where (vi; vi+1) in E for each i. The length of a path in a graph is the number of edges in the path (not the number of vertices).
cycle: a path such that the first vertex is the same as the last vertex If there were an edge (v; v), then this would be considered as a cycle. Such edges are called loops. - 6define directed acyclic graph (DAG)Directed graph that has no cycles. Such graphs are used to capture dependencies between objects or events.
- 7define weighted graphgraph that has a number (weight) associated with each edge
- 8define adjacency listfor each vertex v in V , we represent a list of vertices w such that (v;w) in E.
the adjacency list for a vertex is a list of Edge objects and each edge is represented only by the end vertex of the edge - 9basic Graph class implementation
- 10map for graph
- 11define adjacency matrix
- 12depth first traversal for graphs alg
- 13depth first traversal example & call stack
- 14depth first traversal example
- 15non-recursive depth first traversal alg
- 16breadth first traversal alg
- 17—
- 18—
Information
- Description
- Computer Science Flashcards on Graphs, created by Virginie Gagné on 15/04/2022.
- Created by
- Virginie Gagné
- Views
- 0
- Rating