Graph: Representation using Linked List | Graph Operation- BFS & DFS | Data Structure & Algorithm

LINKED REPRESENTATION OF A GRAPH

Let G be a directed graph with m nodes. The sequential representation of G in memory—i.e., the representation of G by its adjacency matrix A—has a number of major drawbacks. First of all, it may be difficult to insert and delete nodes in G. This is because the size of A may need to be changed and the nodes may need to be reordered, so there may be many, many changes in the matrix A. Furthermore, if the number of edges is O(m) or O(m log2 m), then the matrix A will be sparse (will contain many zeros): hence a great deal of space will be wasted. Accordingly, G is usually represented in memory by a linked representation, also called an adjacency structure. Consider the graph G. The table shows each node in G followed by its adjacency list, which is its list of adjacent nodes, also called its successors or neighbors. The linked representation will contain two lists (or files), a node list NODE and an edge list EDGE. (a) Node list Each element in the list NODE will correspond to a node in G, and it will be a record of the form: NODE NEXT ADJ Here NODE will be the name or key value of the node, NEXT will be a pointer to the next node in the list NODE and ADJ will be a pointer to the first element in the adjacency list of the node, which is maintained in the list EDGE (b) Edge list Each element in the list EDGE will correspond to an edge of G and will be a record of the form: DEST LINK The field DEST will point to the location in the list NODE of the destination or terminal node of the edge. The field LINK will link together the edges with the same initial node, that is, the nodes in the same adjacency list. TRAVERSING A GRAPH Many graph algorithms require one to systematically examine the nodes and edges of a graph C. There are two standard ways that this is done. One way is called a breadth-first search, and the other is called a depth-first search. The breadth-first search will use a queue as an auxiliary structure to hold nodes for future processing, and analogously, the depth-first search will use a stack. During the execution of our algorithms, each node N of G will be in one of three states, called the status of N, as follows: STATUS = 1: (Ready state.) The initial state of the node N STATUS = 2: (Waiting state.) The node N is on the queue or stack, waiting to be processed. STATUS = 3: (Processed state.) The node N has been processed. Breadth-First Search The general idea behind a breadth-first search beginning at a starting node A is as follows. First we examine the starting node A. Then we examine all the neighbors of A. Then we examine all the neighbors of the neighbors of A. And so on. Naturally, we need to keep track of the neighbors of a node, and we need to guarantee that no node is processed more than once. This is accomplished by using a queue to hold nodes that are waiting to be processed. and by using a field STATUS which tells us the current status of any node. The algorithm follows. Algorithm BFS: This algorithm executes a breadth-first search on a graph G beginning at a starting node A. 1. Initialize all nodes to the ready state (STATUS = 1). 2. Put the starting node A in QUEUE and change its status to the waiting state (STATUS = 2). 3. Repeat Steps 4 and 5 until QUEUE is empty: 4. Remove the front node N of QUEUE. Process N and change the status of N to the processed state (STATUS = 3). 5. Add to the rear of QUEUE all the neighbors of N that are in the steady state (STATUS = I). and change their status to the waiting state (STATUS = 2). [End of Step 3 loop. ) 6. Exit. Depth-First Search The general idea behind a depth-first search beginning at a starting node A is as follows. First we examine the starting node A. Then we examine each node N along a path P which begins at A; that is, we process a neighbor of A, then a neighbor of a neighbor of A, and so on. After coming to a "dead end," that is, to the end of the path P, we backtrack on P until we can continue along another, path P. And so on. The algorithm is very similar-to the breadth-first search except now we use a stack instead of the queue. Again, a field STATUS is used to tell us the current status of a node. The algorithm follows. Algorithm DFS: This algorithm executes a depth-first search on a graph G beginning at a starting node A. 1. Initialize all nodes to the ready state (STATUS = 1). 2. Push the starting node A onto STACK and change its status to the waiting state (STATUS = 2). 3. Repeat Steps 4 and 5 until STACK is empty. 4. Pop the top node N of STACK. Process N and change its status to the processed state (STATUS = 3). 5. Push onto STACK all the neighbors of N that are still in the ready state (STATUS = 1), and change their status to the waiting state (STATUS = 2). (End of Step 3 loop.] 6. Exit.

For more details click here