1. The degree, inDegree, and outDegree methods return the count of neighbors for a given node by traversing the adjacency list or matrix.
2. The density method calculates the ratio of existing edges to possible edges in the graph.
3. The adjacent method checks if two nodes are connected by traversing the graph in a breadth-first search.
1. The degree, inDegree, and outDegree methods return the count of neighbors for a given node by traversing the adjacency list or matrix.
2. The density method calculates the ratio of existing edges to possible edges in the graph.
3. The adjacent method checks if two nodes are connected by traversing the graph in a breadth-first search.
1. The degree, inDegree, and outDegree methods return the count of neighbors for a given node by traversing the adjacency list or matrix.
2. The density method calculates the ratio of existing edges to possible edges in the graph.
3. The adjacent method checks if two nodes are connected by traversing the graph in a breadth-first search.
1. The degree, inDegree, and outDegree methods return the count of neighbors for a given node by traversing the adjacency list or matrix.
2. The density method calculates the ratio of existing edges to possible edges in the graph.
3. The adjacent method checks if two nodes are connected by traversing the graph in a breadth-first search.
Download as DOCX, PDF, TXT or read online from Scribd
Download as docx, pdf, or txt
You are on page 1/ 5
CN5005 – Data Structure and
Algorithms Labs Week 10 - Author: Paolo Falcarin
1. Graphs Given the following directed graph, draw the adjacency list and draw the adjacency matrix:
Adjacency Matrix: A B C D E F A 0 1 0 0 0 0 B 0 0 1 0 0 0 C 0 0 0 0 1 0 D 0 1 0 0 0 0 E 0 0 0 1 0 1 F 0 0 0 0 0 0
Adjacency List: AB BC CE EDF DB
2. More Graphs Would you use the adjacency list structure or the adjacency matrix structure in the following cases? Justify your choice. 2a. The graph has 10000 vertices and 20000 edges, and it is important to use as little space as possible Ans: In this case adjacency list structure is used as per me because adjacency matrix structure takes a lot of space and results in memory wastage. Using Adjacency matrix structure will result in 100,000,000 edges in graph but the graph has only 20000 edges. So, adjacency list matrix is used for this.
2b. You need to answer whether two vertices of the graph are adjacent as fast as possible, no matter how much space you use. Ans: The adjacency matrix is preferred here because we can check two edges are adjacent by areAdjacent() operation in O(1) time irrespective of number of edges and nodes.
3. Graphs in Java Download the CN5005-W10-Graph.zip eclipse project containing an implementation of the Graph class and some text files representing different graphs. The text files have the following format: the first line contains the number of nodes of the graph and the type, and then each line represents a single edge, respectively identified by the starting node, the ending node and the weight of the edge ( if no weight is specified then the graph is unweighted). For example, the edge going from A to B is represented by the line "A B 10", while if we would add an edge of weight 7 from B to A the line would have been "B A 7".
5 5, directed B D A B 10 AC3 A D 20 CB2 11 BD5 A C E 15 D E 11
C E
Now try to implement the following methods in the Graph class:
1. int degree(String node) : return the degree of a given node.
public int degree(String node)
{ int deg=0; int n = Integer.parseInt(node); for(int i=0;i<size;i++) { if(m[n][i]==1) { deg++; } } return deg;
} 2. int inDegree(String node): return the in-degree of a node in a di-graph.
public int inDegree(String node)
{ Map<V,Integer> res = new HashMap<V,Integer>(); for(V v:neighbours.keySet()) { res.put(v, 0); } for(V from:neighbours.keySet()) { for(V to:neighbours.get(from)) { res.put(to, res.get(to)+1); } } int x=0; if(res.containsKey(node)) { x = res.get(node); } return x;
3. int outDegree(String node): return the out-degree of a node in a di-graph.
public int outDegree(String node)
{ Map<V,Integer> res1 = new HashMap<V,Integer>(); for(V v:neighbours.keySet()) { res1.put(v, neighbours.get(v).size()); } int y=0; if(res1.containsKey(node)) { y = res1.get(node); } return y;
4. double density() : return the density of the graph.
public double density() { double d; int arr1 = m.length; int arr2 = m[0].length; d = (arr2) / ((arr1)*(arr1-1)); return d;
5. boolean adjacent(String n1, String n2) return true if two nodes are adjacent, false otherwise.
boolean adjacent(String n1,String n2)
{ int n3 = Integer.parseInt(n1); int n4 = Integer.parseInt(n2); boolean visited[] = new boolean[V]; LinkedList<Integer> q = new LinkedList<Integer>(); visited[n3]=true; q.add(n3); Iterator<Integer> i; while(q.size()!=0) { n3 = q.poll(); int n; i=adj[n3].listIterator(); while(i.hasNext()) { n=i.next(); if(n==n4) { return true; } if(!visited[n]) { visited[n]=true; q.add(n); } } } return false;
6. boolean isComplete() : return true if the graph is complete, false otherwise
