Variations of Graph ADTs
From
(→Weighted Graphs) |
(→Connected & Disconnected Graphs) |
||
| (7 intermediate revisions not shown) | |||
| Line 3: | Line 3: | ||
</noinclude> | </noinclude> | ||
<br/> | <br/> | ||
| - | ===Directed Graphs=== | + | == Directed & Undirected Graphs == |
| + | === Directed Graphs === | ||
[[Image:Directed.svg|125px|thumb|A directed graph.]] | [[Image:Directed.svg|125px|thumb|A directed graph.]] | ||
The number of edges with one endpoint on a given vertex is called that vertex's '''degree'''. In a directed graph, the number of edges that point ''to'' a given vertex is called its '''in-degree''', and the number that point ''from'' it is called its '''out-degree'''. Often, we may want to be able to distinguish between different nodes and edges. We can associate labels with either. We call such a graph '''labeled'''. | The number of edges with one endpoint on a given vertex is called that vertex's '''degree'''. In a directed graph, the number of edges that point ''to'' a given vertex is called its '''in-degree''', and the number that point ''from'' it is called its '''out-degree'''. Often, we may want to be able to distinguish between different nodes and edges. We can associate labels with either. We call such a graph '''labeled'''. | ||
| Line 35: | Line 36: | ||
In a directed graph, the edges point from one vertex to another, while in an '''undirected graph''', they merely connect two vertices. | In a directed graph, the edges point from one vertex to another, while in an '''undirected graph''', they merely connect two vertices. | ||
<br/><br/> | <br/><br/> | ||
| + | == Cyclic & Acyclic Graphs == | ||
| + | [[Image:Directed cycle.svg|thumb|A directed cycle. Without the arrows, it is just a cycle. This is not a simple cycle, since the blue vertices are used twice.]] | ||
| + | Graphs may or may not contain '''cycles'''; a cycle is a path in a graph that connects back to it's self (a looping path). Cycles can exist in both directed and undirected graphs. | ||
| - | ===Weighted Graphs | + | A graph is '''acyclic''' if it contains no cycles; unicyclic if it contains exactly one cycle; and pancyclic if it contains cycles of every possible length (from 3 to the order of the graph). |
| + | <br/><br/> | ||
| + | |||
| + | == Connected & Disconnected Graphs == | ||
| + | If it is possible to establish a path from any vertex to any other vertex of a graph, the graph is said to be '''connected'''; otherwise, the graph is '''disconnected'''. A graph is totally disconnected if there is no path connecting any pair of vertices. This is just another name to describe an empty graph or independent set. | ||
| + | <br/><br/> | ||
| + | |||
| + | == Weighted Graphs == | ||
We may also want to associate some cost or weight to the traversal of an edge. When we add this information, the graph is called '''weighted'''. An example of a weighted graph would be the distance between the capitals of a set of countries. | We may also want to associate some cost or weight to the traversal of an edge. When we add this information, the graph is called '''weighted'''. An example of a weighted graph would be the distance between the capitals of a set of countries. | ||
Current revision as of 12:53, 2 June 2009
| ← Representing Graphs | ↑ Contents: CS2 | Common Graph Algorithms → |
Contents |
Directed & Undirected Graphs
Directed Graphs
The number of edges with one endpoint on a given vertex is called that vertex's degree. In a directed graph, the number of edges that point to a given vertex is called its in-degree, and the number that point from it is called its out-degree. Often, we may want to be able to distinguish between different nodes and edges. We can associate labels with either. We call such a graph labeled.
Directed Graph Operations
make-graph(): graph- Create a new graph, initially with no nodes or edges.
make-vertex(graph G, element value): vertex- Create a new vertex, with the given value.
make-edge(vertex u, vertex v): edge- Create an edge between u and v. In a directed graph, the edge will flow from u to v.
get-edges(vertex v): edge-set- Returns the set of edges flowing from v
get-neighbors(vertex v): vertex-set- Returns the set of vertexes connected to v
[TODO: also need undirected graph abstraction in that section, and also find a better set of operations-- the key to finding good operations is seeing what the algorithms that use graphs actually need]
We can use graphs to represent relationships between objects. For example, the popular game "Six Degrees of Kevin Bacon" can be modeled by a graph, in particular, a labeled undirected graph. Each actor becomes a node, labeled by the actor's name. Nodes are connected by an edge when the two actors appeared together in some movie. We can label this edge by the name of the movie. Then the problem of finding a path from any actor to Kevin Bacon in six or less steps easily reduces to the Single Source Shortest Path problem found in the companion Algorithms book. The Oracle of Bacon at the University of Virginia has actually implemented this algorithm and can tell you the path from any actor to Kevin Bacon in a few clicks[1].
Undirected Graphs
In a directed graph, the edges point from one vertex to another, while in an undirected graph, they merely connect two vertices.
Cyclic & Acyclic Graphs
Graphs may or may not contain cycles; a cycle is a path in a graph that connects back to it's self (a looping path). Cycles can exist in both directed and undirected graphs.
A graph is acyclic if it contains no cycles; unicyclic if it contains exactly one cycle; and pancyclic if it contains cycles of every possible length (from 3 to the order of the graph).
Connected & Disconnected Graphs
If it is possible to establish a path from any vertex to any other vertex of a graph, the graph is said to be connected; otherwise, the graph is disconnected. A graph is totally disconnected if there is no path connecting any pair of vertices. This is just another name to describe an empty graph or independent set.
Weighted Graphs
We may also want to associate some cost or weight to the traversal of an edge. When we add this information, the graph is called weighted. An example of a weighted graph would be the distance between the capitals of a set of countries.
Directed and undirected graphs may both be weighted. The operations on a weighted graph are the same with addition of a weight parameter during edge creation:
Weighted Graph Operations (an extension of undirected/directed graph operations)
make-edge(vertex u, vertex v, weight w): edge- Create an edge between u and v with weight w. In a directed graph, the edge will flow from u to v.
CS2: Data Structures
Theory of Computation - ADT Preliminaries
Linear ADTs - Tree ADTs - Graph ADTs - Unordered Collection ADTs
