Sahni's ch.16 Graphs

Sahni
Data Structures, Algorithms and Applications in C++, 2nd ed.
: Chapter 16 Graphs

graph data structure

terminology:
vertex, edge, adjacent, incident, degree, cycle, path, connected component, and spanning tree

types:
undirected / directed / weighted

representation:
adjacent matrix / array adjacency lists /  linked adjacency lists

standard graph search methods:
breadth-first / depth-first search

algorithms:

16.1 Definitions

graph
: an ordered pair of finite sets of vertices (or nodes or points) and edges (or arcs or lines)

http://en.wikipedia.org/wiki/Graph_(data_structure)

loop
: self-edge

digraph
: directed graph

network
: weighted undirected graph or digraph

16.2 Applications and More Definitions

example 16.1: path problems

example 16.2: spanning trees

A graph is connected iff there is a path between every pair of vertices in the graph.

cycle
: simiple path with the same start and end vertex

tree
: a connected undirected graph that contains no cycles

spanning tree
: a subgraph of a graph that contains all the vertices of the graph and is a tree

example 16.3: interpreters

bipartite graphs

16.3 Properties

http://en.wikipedia.org/wiki/List_of_graph_theory_topics

in-degree
out-degree

complete digraph

16.4 The ADT graph

ADT graph = Abstract Data type graph

http://en.wikipedia.org/wiki/Abstract_data_type


http://en.wikipedia.org/wiki/Pure_virtual_method

16.5 Representation of Unweighted Graphs

adjacency matrix
linked adjacency list
array adjacency list

http://en.wikipedia.org/wiki/Adjacency_matrix

http://en.wikipedia.org/wiki/Adjacency_list

http://en.wikipedia.org/wiki/Graph_theory
 

16.6 Representation of Weighted Graphs

cost-adjacency-matrix

16.7 Class Implementations

 

16.8 Graph Search Methods

Breadth-First Search (BFS)
http://en.wikipedia.org/wiki/Breadth_first_search

queue
http://cplusplus.com/reference/stl/queue/
http://en.wikipedia.org/wiki/Queue_(data_structure)

cf. stack
http://cplusplus.com/reference/stl/stack/

list
http://cplusplus.com/reference/stl/list/

cp. level-order traversal of a binary tree
http://en.wikipedia.org/wiki/Binary_search_tree#Traversal

Depth-First Search (DFS)
http://en.wikipedia.org/wiki/Depth-first_search

cp. pre-order traversal of a binary tree

 

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

 

http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm