Sahni's ch.16 Graphs

maetel 2009. 6. 11. 20:36

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