Graph-Implementation

[Manish4Kumar]

Pls merge my pr's

[Manish4Kumar]

A graph is a non-linear data structure. A graph can be defined as a collection of Nodes which are also called “vertices” and “edges” that connect two or more vertices.

A graph can also be seen as a cyclic tree where vertices do not have a parent-child relationship but maintain a complex relationship among them.

1. Vertex: Each node of the graph is called a vertex. In the above graph, A, B, C, and D are the vertices of the graph.

2. Edge: The link or path between two vertices is called an edge. It connects two or more vertices. The different edges in the above graph are AB, BC, AD, and DC.

3. Adjacent node: In a graph, if two nodes are connected by an edge then they are called adjacent nodes or neighbors. In the above graph, vertices A and B are connected by edge AB. Thus A and B are adjacent nodes.

4. Degree of the node: The number of edges that are connected to a particular node is called the degree of the node. In the above graph, node A has a degree 2.

5. Path: The sequence of nodes that we need to follow when we have to travel from one vertex to another in a graph is called the path. In our example graph, if we need to go from node A to C, then the path would be A->B->C.

6. Closed path: If the initial node is the same as a terminal node, then that path is termed as the closed path.

7. Simple path: A closed path in which all the other nodes are distinct is called a simple path.

8. Cycle: A path in which there are no repeated edges or vertices and the first and last vertices are the same is called a cycle. In the above graph, A->B->C->D->A is a cycle.

9. Connected Graph: A connected graph is the one in which there is a path between each of the vertices. This means that there is not a single vertex which is isolated or without a connecting edge. The graph shown above is a connected graph.

10. Complete Graph: A graph in which each node is connected to another is called the Complete graph. If N is the total number of nodes in a graph then the complete graph contains N(N-1)/2 number of edges.

11.Weighted graph: A positive value assigned to each edge indicating its length (distance between the vertices connected by an edge) is called weight. The graph containing weighted edges is called a weighted graph. The weight of an edge e is denoted by w(e) and it indicates the cost of traversing an edge.

12. Diagraph: A digraph is a graph in which every edge is associated with a specific direction and the traversal can be done in specified direction only.

C++ Graph Implementation Using Adjacency List

Here we are going to display the adjacency list for a weighted directed graph. We have used two structures to hold the adjacency list and edges of the graph. The adjacency list is displayed as (start_vertex, end_vertex, weight).

The C++ program is as follows:

include

using namespace std; // stores adjacency list items struct adjNode { int val, cost; adjNode next; }; // structure to store edges struct graphEdge { int start_ver, end_ver, weight; }; class DiaGraph{ // insert new nodes into adjacency list from given graph adjNode getAdjListNode(int value, int weight, adjNode head) { adjNode newNode = new adjNode; newNode->val = value; newNode->cost = weight;

    newNode->next = head;   // point new node to current head
    return newNode;
}
int N;  // number of nodes in the graph

public: adjNode *head; //adjacency list as array of pointers // Constructor DiaGraph(graphEdge edges[], int n, int N) { // allocate new node head = new adjNode[N](); this->N = N; // initialize head pointer for all vertices for (int i = 0; i < N; ++i) head[i] = nullptr; // construct directed graph by adding edges to it for (unsigned i = 0; i < n; i++) { int start_ver = edges[i].start_ver; int end_ver = edges[i].end_ver; int weight = edges[i].weight; // insert in the beginning adjNode* newNode = getAdjListNode(end_ver, weight, head[start_ver]);

                    // point head pointer to new node
        head[start_ver] = newNode;
         }
}
  // Destructor
 ~DiaGraph() {
for (int i = 0; i < N; i++)
    delete[] head[i];
    delete[] head;
 }

}; // print all adjacent vertices of given vertex void display_AdjList(adjNode* ptr, int i) { while (ptr != nullptr) { cout << "(" << i << ", " << ptr->val << ", " << ptr->cost << ") "; ptr = ptr->next; } cout << endl; } // graph implementation int main() { // graph edges array. graphEdge edges[] = { // (x, y, w) -> edge from x to y with weight w {0,1,2},{0,2,4},{1,4,3},{2,3,2},{3,1,4},{4,3,3} }; int N = 6; // Number of vertices in the graph // calculate number of edges int n = sizeof(edges)/sizeof(edges[0]); // construct graph DiaGraph diagraph(edges, n, N); // print adjacency list representation of graph cout<<"Graph adjacency list "<<endl<<"(start_vertex, end_vertex, weight):"<<endl; for (int i = 0; i < N; i++) { // display adjacent vertices of vertex i display_AdjList(diagraph.head[i], i); } return 0; } Output:

Output:

Graph adjacency list

(start_vertex, end_vertex, weight):

(0, 2, 4) (0, 1, 2)

(1, 4, 3)

(2, 3, 2)

(3, 1, 4)

(4, 3, 3)

[Manish4Kumar]

pls accept my pr