instagram

Directed and Undirected Graph

This is small notes about graphs, There are two types of graphs, By just looking at below image you will understand the different of these two graphs.

DifferenceBetween_Directed_UnDirected_Graphs1

In a directed graph direction matters. i.e. edge V2->V3 means that edge is directed. There is only an edge from V2 to V3 and no edge from V3 to V2. Therefore you can go from vertex V2 to vertex V3 but not from V3 to V2.

In undirected graph V2-V3 means the edge has no direction, i.e. V2-V3 means you can go both from V2 to V3 and V3 to V2.

1. Java Example Of Creating Undirected Graph :


public static Graph generateGraph() {

		Graph graph = new Graph();

		Node a = new Node("A");
		Node b = new Node("B");
		Node c = new Node("C");
		Node d = new Node("D");
		Node q = new Node("Q");
		Node r = new Node("R");
		Node g = new Node("G");
		Node h = new Node("H");
		Node i = new Node("I");
		Node p = new Node("P");

		a.addAdjacent(c);

		b.addAdjacent(c);
		b.addAdjacent(p);

		c.addAdjacent(a);
		c.addAdjacent(b);
		c.addAdjacent(d);
		c.addAdjacent(q);

		p.addAdjacent(b);
		p.addAdjacent(r);

		q.addAdjacent(c);
		q.addAdjacent(r);

		r.addAdjacent(q);
		r.addAdjacent(p);

		d.addAdjacent(c);
		d.addAdjacent(h);
		d.addAdjacent(g);

		h.addAdjacent(d);

		g.addAdjacent(d);
		g.addAdjacent(i);

		i.addAdjacent(g);

		graph.addVertex(a);
		graph.addVertex(b);
		graph.addVertex(c);
		graph.addVertex(d);
		graph.addVertex(q);
		graph.addVertex(r);
		graph.addVertex(g);
		graph.addVertex(h);
		graph.addVertex(i);
		graph.addVertex(p);

		return graph;

	}

2. Java Example Of Creating Directed Graph :


public static Graph generateGraph() {

		Graph graph = new Graph();

		Node a = new Node("A");
		Node b = new Node("B");
		Node c = new Node("C");
		Node d = new Node("D");
		Node q = new Node("Q");
		Node r = new Node("R");
		Node g = new Node("G");
		Node h = new Node("H");
		Node i = new Node("I");
		Node p = new Node("P");

		a.addAdjacent(c);

		b.addAdjacent(c);
		b.addAdjacent(p);

		c.addAdjacent(d);
		c.addAdjacent(q);

		p.addAdjacent(r);

		q.addAdjacent(r);

		d.addAdjacent(h);
		d.addAdjacent(g);

		g.addAdjacent(i);

		graph.addVertex(a);
		graph.addVertex(b);
		graph.addVertex(c);
		graph.addVertex(d);
		graph.addVertex(q);
		graph.addVertex(r);
		graph.addVertex(g);
		graph.addVertex(h);
		graph.addVertex(i);
		graph.addVertex(p);

		return graph;

	}

Some Utility Classes Used In Above Example :


State.java

package com.omt.learn.algo.util.graph;

public enum State {

	VISITED, UNVISITED, FOUND
}

Node.java

package com.omt.learn.algo.util.graph;

import java.util.ArrayList;
import java.util.List;

public class Node {

	private List<Node> adjacent = new ArrayList<>();
	private String vertex = "";
	private State state = State.UNVISITED;

	public Node(String vertex) {
		this.vertex = vertex;
	}

	public void addAdjacent(Node node) {
		adjacent.add(node);
	}

	public boolean isVisited() {
		return getState() == State.VISITED;
	}

	public boolean isFoundAlready() {
		return getState() == State.FOUND;
	}

	public State getState() {
		return state;
	}

	public void setState(State state) {
		this.state = state;
	}

	public List<Node> getAdjacent() {
		return adjacent;
	}

	public String getVertex() {
		return vertex;
	}

}

Graph.java

package com.omt.learn.algo.util.graph;

import java.util.ArrayList;
import java.util.List;

public class Graph {

	private List<Node> vertices = new ArrayList<>();

	public void addVertex(Node node) {
		vertices.add(node);
	}

	public List<Node> getVertices() {
		return vertices;
	}

}

Share
1 Comment

Comments are closed.