25-09-2013, 04:27 PM
DATA STRUCTURES USED IN NETWORK PROGRAMMING
AIM:
Representation of unidirectional,Directional weighted and unweighted graphs.
Definition:
A graph is a collection (nonempty set) of vertices and edges.
A path from vertex x to vertex y : a list of vertices in which successive vertices are
connected by edges.
Connected graph: There is a path between each two vertices.
Simple path: No vertex is repeated.
Cycle: Simple path except that the first vertex is equal to the last.
Loop: An edge that connects the vertex with itself.
Tree: A graph with no cycles.
Spanning tree of a graph: a subgraph that contains all the vertices, and no cycles.
Complete graphs: Graphs with all edges present – each vertex is connected to all other
vertices.
Weighted graphs – weights are assigned to each edge (e.g. road map with distances).
Directed graphs: The edges are oriented, they have a beginning and an end .
Algorithm
Initialize sorted list to be empty, and a counter to 0
Compute the indegrees of all nodes
Store all nodes with indegree 0 in a queue
While the queue is not empty
a. get a node U and put it in the sorted list. Increment the counter.
b. For all edges (U,V) decrement the indegree of V, and put V in the queue if the
updated indegree is 0.
5. If counter is not equal to the number of nodes, there is a cycle.