Find if there is a path of more than k length from a source
The problem you're addressing is to find whether there exists a path of more than a given length 'k' starting from a given source node in a graph. The graph is represented as an adjacency list where each vertex is connected to other vertices with associated lengths.
Problem Statement and Example
Given a graph with vertices and edges, you need to determine if there is a path starting from a specified source node such that the sum of lengths of the edges along the path is greater than a specified value 'k'. For example, consider the following graph:
Vertices: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Edges: (0,1,9), (0,2,10), (0,9,4), (1,3,6), (1,9,5), (2,4,3), (2,7,7), (2,9,2), (3,5,5), (3,7,4), (3,9,3), (4,6,4), (5,6,3), (5,7,8), (6,7,8), (6,8,4)
In this graph, you're required to find if there is a path of length greater than 'k' starting from a specified source node.
Idea to Solve
To solve this problem, you can perform Depth-First Search (DFS) starting from the source node. During the DFS traversal, you'll keep track of the length of the path. If the length exceeds 'k', you can immediately return 'true'. You'll also maintain a visited array to avoid revisiting nodes that are already part of the current path.
Pseudocode
function isLengthGreaterThanK(index, visit, sum, k)
if index is out of bounds
return false
if visit[index] is true
return false
if sum > k
return true
set visit[index] to true
for each neighbor of index
if isLengthGreaterThanK(neighbor, visit, sum + length of edge, k)
return true
set visit[index] to false
return false
function checkPathGreaterThanK(source, k)
create visit array of size equal to number of vertices
set all elements of visit array to false
if isLengthGreaterThanK(source, visit, 0, k)
print "Result: YES"
else
print "Result: NO"
Algorithm Explanation
- Implement a recursive function
isLengthGreaterThanK(index, visit, sum, k)
that checks whether there is a path starting from 'index' with a length greater than 'k'. - The function first checks if 'index' is within bounds and if the node has already been visited. If so, it returns false.
- If the sum of the path is greater than 'k', it returns true.
- Set the visited status of 'index' to true.
- Iterate through the neighbors of 'index'. For each neighbor, recursively call the function with updated values for 'index', 'visit', 'sum', and 'k'.
- After trying all neighbors, reset the visited status of 'index' and return false.
- Implement
checkPathGreaterThanK(source, k)
that initializes the visited array, then callsisLengthGreaterThanK()
for the source node. Print the result.
Program Solution
/*
Java Program for
Find if there is a path of more than k length from a source
*/
class AjlistNode
{
// Vertices node key
public int id;
public int length;
public AjlistNode next;
public AjlistNode(int id, int length)
{
// Set value of node key
this.id = id;
this.length = length;
this.next = null;
}
}
class Vertices
{
public int data;
public AjlistNode next;
public Vertices(int data)
{
this.data = data;
this.next = null;
}
}
public class Graph
{
// Number of Vertices
public int size;
public Vertices[] node;
public Graph(int size)
{
//set value
this.size = size;
this.node = new Vertices[size];
this.setData();
}
// Set initial node value
public void setData()
{
if (node == null)
{
System.out.println("\nEmpty Graph");
}
else
{
for (int index = 0; index < size; index++)
{
node[index] = new Vertices(index);
}
}
}
// Connect two nodes
public void connect(int start, int last, int length)
{
AjlistNode new_edge = new AjlistNode(last, length);
if (node[start].next == null)
{
node[start].next = new_edge;
}
else
{
AjlistNode temp = node[start].next;
while (temp.next != null)
{
temp = temp.next;
}
temp.next = new_edge;
}
}
// Add edge of two nodes
public void addEdge(int start, int last, int length)
{
if (start >= 0 && start < size && last >= 0 &&
last < size && node != null)
{
connect(start, last, length);
if (start == last)
{
// Self looping situation
return;
}
connect(last, start, length);
}
else
{
System.out.println("\nHere Something Wrong");
}
}
public void printGraph()
{
if (size > 0 && node != null)
{
// Print graph ajlist Node value
for (int index = 0; index < size; ++index)
{
System.out.print("\nAdjacency list of vertex " +
index + " :");
AjlistNode temp = node[index].next;
while (temp != null)
{
System.out.print(" " + node[temp.id].data);
// visit to next edge
temp = temp.next;
}
}
}
}
public boolean isLengthGreaterThanK(
int index, boolean[] visit, int sum, int k)
{
if (index < 0 || index >= this.size)
{
return false;
}
if (visit[index] == true)
{
// When node is already includes in current path
return false;
}
if (sum > k)
{
// When length sum is greater than k
return true;
}
// Here modified the value of visited node
visit[index] = true;
// This is used to iterate nodes edges
AjlistNode temp = node[index].next;
while (temp != null)
{
if (isLengthGreaterThanK(temp.id,
visit, sum + (temp.length), k))
{
// Found path with length greater than k
return true;
}
// Visit to next edge
temp = temp.next;
}
// Reset the value of visited node status
visit[index] = false;
return false;
}
public void checkPathGreaterThanK(int source, int k)
{
boolean[] visit = new boolean[this.size];
// Set initial visited node status
for (int i = 0; i < size; ++i)
{
visit[i] = false;
}
System.out.print("\n Source node : " + source);
System.out.print("\n Length k : " + k);
if (isLengthGreaterThanK(source, visit, 0, k))
{
System.out.print("\n Result : YES\n");
}
else
{
System.out.print("\n Result : NO\n");
}
}
public static void main(String[] args)
{
// 10 implies the number of nodes in graph
Graph g = new Graph(10);
g.addEdge(0, 1, 9);
g.addEdge(0, 2, 10);
g.addEdge(0, 9, 4);
g.addEdge(1, 3, 6);
g.addEdge(1, 9, 5);
g.addEdge(2, 4, 3);
g.addEdge(2, 7, 7);
g.addEdge(2, 9, 2);
g.addEdge(3, 5, 5);
g.addEdge(3, 7, 4);
g.addEdge(3, 9, 3);
g.addEdge(4, 6, 4);
g.addEdge(5, 6, 3);
g.addEdge(5, 7, 8);
g.addEdge(6, 7, 8);
g.addEdge(6, 8, 4);
// print graph element
g.printGraph();
// Test A
int source = 0;
int k = 48;
g.checkPathGreaterThanK(source, k);
// Test B
source = 0;
k = 51;
g.checkPathGreaterThanK(source, k);
// Test C
source = 8;
k = 54;
g.checkPathGreaterThanK(source, k);
}
}
Output
Adjacency list of vertex 0 : 1 2 9
Adjacency list of vertex 1 : 0 3 9
Adjacency list of vertex 2 : 0 4 7 9
Adjacency list of vertex 3 : 1 5 7 9
Adjacency list of vertex 4 : 2 6
Adjacency list of vertex 5 : 3 6 7
Adjacency list of vertex 6 : 4 5 7 8
Adjacency list of vertex 7 : 2 3 5 6
Adjacency list of vertex 8 : 6
Adjacency list of vertex 9 : 0 1 2 3
Source node : 0
Length k : 48
Result : YES
Source node : 0
Length k : 51
Result : NO
Source node : 8
Length k : 54
Result : YES
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program for
Find if there is a path of more than k length from a source
*/
class AjlistNode
{
public:
// Vertices node key
int id;
int length;
AjlistNode *next;
AjlistNode(int id, int length)
{
// Set value of node key
this->id = id;
this->length = length;
this->next = NULL;
}
};
class Vertices
{
public: int data;
AjlistNode *next;
Vertices()
{
this->data = 0;
this->next = NULL;
}
Vertices(int data)
{
this->data = data;
this->next = NULL;
}
};
class Graph
{
public:
// Number of Vertices
int size;
Vertices *node;
Graph(int size)
{
//set value
this->size = size;
this->node = new Vertices[size];
this->setData();
}
// Set initial node value
void setData()
{
if (this->node == NULL)
{
cout << "\nEmpty Graph" << endl;
}
else
{
for (int index = 0; index < this->size; index++)
{
this->node[index].data = index;
}
}
}
// Connect two nodes
void connect(int start, int last, int length)
{
AjlistNode *new_edge = new AjlistNode(last, length);
if (this->node[start].next == NULL)
{
this->node[start].next = new_edge;
}
else
{
AjlistNode *temp = this->node[start].next;
while (temp->next != NULL)
{
temp = temp->next;
}
temp->next = new_edge;
}
}
// Add edge of two nodes
void addEdge(int start, int last, int length)
{
if (start >= 0 && start < this->size &&
last >= 0 && last < this->size && this->node != NULL)
{
this->connect(start, last, length);
if (start == last)
{
// Self looping situation
return;
}
this->connect(last, start, length);
}
else
{
cout << "\nHere Something Wrong" << endl;
}
}
void printGraph()
{
if (this->size > 0 && this->node != NULL)
{
// Print graph ajlist Node value
for (int index = 0; index < this->size; ++index)
{
cout << "\nAdjacency list of vertex " << index << " :";
AjlistNode *temp = this->node[index].next;
while (temp != NULL)
{
cout << " " << this->node[temp->id].data;
// visit to next edge
temp = temp->next;
}
}
}
}
bool isLengthGreaterThanK(int index, bool visit[], int sum, int k)
{
if (index < 0 || index >= this->size)
{
return false;
}
if (visit[index] == true)
{
// When node is already includes in current path
return false;
}
if (sum > k)
{
// When length sum is greater than k
return true;
}
// Here modified the value of visited node
visit[index] = true;
// This is used to iterate nodes edges
AjlistNode *temp = this->node[index].next;
while (temp != NULL)
{
if (this->isLengthGreaterThanK(
temp->id, visit, sum + (temp->length), k))
{
// Found path with length greater than k
return true;
}
// Visit to next edge
temp = temp->next;
}
// Reset the value of visited node status
visit[index] = false;
return false;
}
void checkPathGreaterThanK(int source, int k)
{
bool visit[this->size];
// Set initial visited node status
for (int i = 0; i < this->size; ++i)
{
visit[i] = false;
}
cout << "\n Source node : " << source;
cout << "\n Length k : " << k;
if (this->isLengthGreaterThanK(source, visit, 0, k))
{
cout << "\n Result : YES\n";
}
else
{
cout << "\n Result : NO\n";
}
}
};
int main()
{
// 10 implies the number of nodes in graph
Graph *g = new Graph(10);
g->addEdge(0, 1, 9);
g->addEdge(0, 2, 10);
g->addEdge(0, 9, 4);
g->addEdge(1, 3, 6);
g->addEdge(1, 9, 5);
g->addEdge(2, 4, 3);
g->addEdge(2, 7, 7);
g->addEdge(2, 9, 2);
g->addEdge(3, 5, 5);
g->addEdge(3, 7, 4);
g->addEdge(3, 9, 3);
g->addEdge(4, 6, 4);
g->addEdge(5, 6, 3);
g->addEdge(5, 7, 8);
g->addEdge(6, 7, 8);
g->addEdge(6, 8, 4);
// print graph element
g->printGraph();
// Test A
int source = 0;
int k = 48;
g->checkPathGreaterThanK(source, k);
// Test B
source = 0;
k = 51;
g->checkPathGreaterThanK(source, k);
// Test C
source = 8;
k = 54;
g->checkPathGreaterThanK(source, k);
return 0;
}
Output
Adjacency list of vertex 0 : 1 2 9
Adjacency list of vertex 1 : 0 3 9
Adjacency list of vertex 2 : 0 4 7 9
Adjacency list of vertex 3 : 1 5 7 9
Adjacency list of vertex 4 : 2 6
Adjacency list of vertex 5 : 3 6 7
Adjacency list of vertex 6 : 4 5 7 8
Adjacency list of vertex 7 : 2 3 5 6
Adjacency list of vertex 8 : 6
Adjacency list of vertex 9 : 0 1 2 3
Source node : 0
Length k : 48
Result : YES
Source node : 0
Length k : 51
Result : NO
Source node : 8
Length k : 54
Result : YES
// Include namespace system
using System;
/*
Csharp Program for
Find if there is a path of more than k length from a source
*/
public class AjlistNode
{
// Vertices node key
public int id;
public int length;
public AjlistNode next;
public AjlistNode(int id, int length)
{
// Set value of node key
this.id = id;
this.length = length;
this.next = null;
}
}
public class Vertices
{
public int data;
public AjlistNode next;
public Vertices(int data)
{
this.data = data;
this.next = null;
}
}
public class Graph
{
// Number of Vertices
public int size;
public Vertices[] node;
public Graph(int size)
{
//set value
this.size = size;
this.node = new Vertices[size];
this.setData();
}
// Set initial node value
public void setData()
{
if (this.node == null)
{
Console.WriteLine("\nEmpty Graph");
}
else
{
for (int index = 0; index < this.size; index++)
{
this.node[index] = new Vertices(index);
}
}
}
// Connect two nodes
public void connect(int start, int last, int length)
{
AjlistNode new_edge = new AjlistNode(last, length);
if (this.node[start].next == null)
{
this.node[start].next = new_edge;
}
else
{
AjlistNode temp = this.node[start].next;
while (temp.next != null)
{
temp = temp.next;
}
temp.next = new_edge;
}
}
// Add edge of two nodes
public void addEdge(int start, int last, int length)
{
if (start >= 0 && start < this.size && last >= 0 &&
last < this.size && this.node != null)
{
this.connect(start, last, length);
if (start == last)
{
// Self looping situation
return;
}
this.connect(last, start, length);
}
else
{
Console.WriteLine("\nHere Something Wrong");
}
}
public void printGraph()
{
if (this.size > 0 && this.node != null)
{
// Print graph ajlist Node value
for (int index = 0; index < this.size; ++index)
{
Console.Write("\nAdjacency list of vertex " + index + " :");
AjlistNode temp = this.node[index].next;
while (temp != null)
{
Console.Write(" " + this.node[temp.id].data);
// visit to next edge
temp = temp.next;
}
}
}
}
public Boolean isLengthGreaterThanK(int index,
Boolean[] visit, int sum, int k)
{
if (index < 0 || index >= this.size)
{
return false;
}
if (visit[index] == true)
{
// When node is already includes in current path
return false;
}
if (sum > k)
{
// When length sum is greater than k
return true;
}
// Here modified the value of visited node
visit[index] = true;
// This is used to iterate nodes edges
AjlistNode temp = this.node[index].next;
while (temp != null)
{
if (this.isLengthGreaterThanK(temp.id,
visit, sum + (temp.length), k))
{
// Found path with length greater than k
return true;
}
// Visit to next edge
temp = temp.next;
}
// Reset the value of visited node status
visit[index] = false;
return false;
}
public void checkPathGreaterThanK(int source, int k)
{
Boolean[] visit = new Boolean[this.size];
// Set initial visited node status
for (int i = 0; i < this.size; ++i)
{
visit[i] = false;
}
Console.Write("\n Source node : " + source);
Console.Write("\n Length k : " + k);
if (this.isLengthGreaterThanK(source, visit, 0, k))
{
Console.Write("\n Result : YES\n");
}
else
{
Console.Write("\n Result : NO\n");
}
}
public static void Main(String[] args)
{
// 10 implies the number of nodes in graph
Graph g = new Graph(10);
g.addEdge(0, 1, 9);
g.addEdge(0, 2, 10);
g.addEdge(0, 9, 4);
g.addEdge(1, 3, 6);
g.addEdge(1, 9, 5);
g.addEdge(2, 4, 3);
g.addEdge(2, 7, 7);
g.addEdge(2, 9, 2);
g.addEdge(3, 5, 5);
g.addEdge(3, 7, 4);
g.addEdge(3, 9, 3);
g.addEdge(4, 6, 4);
g.addEdge(5, 6, 3);
g.addEdge(5, 7, 8);
g.addEdge(6, 7, 8);
g.addEdge(6, 8, 4);
// print graph element
g.printGraph();
// Test A
int source = 0;
int k = 48;
g.checkPathGreaterThanK(source, k);
// Test B
source = 0;
k = 51;
g.checkPathGreaterThanK(source, k);
// Test C
source = 8;
k = 54;
g.checkPathGreaterThanK(source, k);
}
}
Output
Adjacency list of vertex 0 : 1 2 9
Adjacency list of vertex 1 : 0 3 9
Adjacency list of vertex 2 : 0 4 7 9
Adjacency list of vertex 3 : 1 5 7 9
Adjacency list of vertex 4 : 2 6
Adjacency list of vertex 5 : 3 6 7
Adjacency list of vertex 6 : 4 5 7 8
Adjacency list of vertex 7 : 2 3 5 6
Adjacency list of vertex 8 : 6
Adjacency list of vertex 9 : 0 1 2 3
Source node : 0
Length k : 48
Result : YES
Source node : 0
Length k : 51
Result : NO
Source node : 8
Length k : 54
Result : YES
package main
import "fmt"
/*
Go Program for
Find if there is a path of more than k length from a source
*/
type AjlistNode struct {
// Vertices node key
id int
length int
next * AjlistNode
}
func getAjlistNode(id int, length int) * AjlistNode {
var me *AjlistNode = &AjlistNode {}
// Set value of node key
me.id = id
me.length = length
me.next = nil
return me
}
type Vertices struct {
data int
next * AjlistNode
}
func getVertices(data int) * Vertices {
var me *Vertices = &Vertices {}
me.data = data
me.next = nil
return me
}
type Graph struct {
// Number of Vertices
size int
node []*Vertices
}
func getGraph(size int) * Graph {
var me *Graph = &Graph {}
//set value
me.size = size
me.node = make([]*Vertices, size)
me.setData()
return me
}
// Set initial node value
func(this *Graph) setData() {
if this.node == nil {
fmt.Println("\nEmpty Graph")
} else {
for index := 0 ; index < this.size ; index++ {
this.node[index] = getVertices(index)
}
}
}
// Connect two nodes
func(this *Graph) connect(start, last, length int) {
var new_edge * AjlistNode = getAjlistNode(last, length)
if this.node[start].next == nil {
this.node[start].next = new_edge
} else {
var temp * AjlistNode = this.node[start].next
for (temp.next != nil) {
temp = temp.next
}
temp.next = new_edge
}
}
// Add edge of two nodes
func(this *Graph) addEdge(start, last, length int) {
if start >= 0 && start < this.size && last >= 0 &&
last < this.size && this.node != nil {
this.connect(start, last, length)
if start == last {
// Self looping situation
return
}
this.connect(last, start, length)
} else {
fmt.Println("\nHere Something Wrong")
}
}
func(this Graph) printGraph() {
if this.size > 0 && this.node != nil {
// Print graph ajlist Node value
for index := 0 ; index < this.size ; index++ {
fmt.Print("\nAdjacency list of vertex ", index, " :")
var temp * AjlistNode = this.node[index].next
for (temp != nil) {
fmt.Print(" ", this.node[temp.id].data)
// visit to next edge
temp = temp.next
}
}
}
}
func(this Graph) isLengthGreaterThanK(
index int, visit[] bool, sum int, k int) bool {
if index < 0 || index >= this.size {
return false
}
if visit[index] == true {
// When node is already includes in current path
return false
}
if sum > k {
// When length sum is greater than k
return true
}
// Here modified the value of visited node
visit[index] = true
// This is used to iterate nodes edges
var temp * AjlistNode = this.node[index].next
for (temp != nil) {
if this.isLengthGreaterThanK(temp.id,
visit, sum + (temp.length), k) {
// Found path with length greater than k
return true
}
// Visit to next edge
temp = temp.next
}
// Reset the value of visited node status
visit[index] = false
return false
}
func(this Graph) checkPathGreaterThanK(source, k int) {
// Set initial visited node status
var visit = make([] bool, this.size)
fmt.Print("\n Source node : ", source)
fmt.Print("\n Length k : ", k)
if this.isLengthGreaterThanK(source, visit, 0, k) {
fmt.Print("\n Result : YES\n")
} else {
fmt.Print("\n Result : NO\n")
}
}
func main() {
// 10 implies the number of nodes in graph
var g * Graph = getGraph(10)
g.addEdge(0, 1, 9)
g.addEdge(0, 2, 10)
g.addEdge(0, 9, 4)
g.addEdge(1, 3, 6)
g.addEdge(1, 9, 5)
g.addEdge(2, 4, 3)
g.addEdge(2, 7, 7)
g.addEdge(2, 9, 2)
g.addEdge(3, 5, 5)
g.addEdge(3, 7, 4)
g.addEdge(3, 9, 3)
g.addEdge(4, 6, 4)
g.addEdge(5, 6, 3)
g.addEdge(5, 7, 8)
g.addEdge(6, 7, 8)
g.addEdge(6, 8, 4)
// print graph element
g.printGraph()
// Test A
var source int = 0
var k int = 48
g.checkPathGreaterThanK(source, k)
// Test B
source = 0
k = 51
g.checkPathGreaterThanK(source, k)
// Test C
source = 8
k = 54
g.checkPathGreaterThanK(source, k)
}
Output
Adjacency list of vertex 0 : 1 2 9
Adjacency list of vertex 1 : 0 3 9
Adjacency list of vertex 2 : 0 4 7 9
Adjacency list of vertex 3 : 1 5 7 9
Adjacency list of vertex 4 : 2 6
Adjacency list of vertex 5 : 3 6 7
Adjacency list of vertex 6 : 4 5 7 8
Adjacency list of vertex 7 : 2 3 5 6
Adjacency list of vertex 8 : 6
Adjacency list of vertex 9 : 0 1 2 3
Source node : 0
Length k : 48
Result : YES
Source node : 0
Length k : 51
Result : NO
Source node : 8
Length k : 54
Result : YES
<?php
/*
Php Program for
Find if there is a path of more than k length from a source
*/
class AjlistNode
{
// Vertices node key
public $id;
public $length;
public $next;
public function __construct($id, $length)
{
// Set value of node key
$this->id = $id;
$this->length = $length;
$this->next = NULL;
}
}
class Vertices
{
public $data;
public $next;
public function __construct($data)
{
$this->data = $data;
$this->next = NULL;
}
}
class Graph
{
// Number of Vertices
public $size;
public $node;
public function __construct($size)
{
//set value
$this->size = $size;
$this->node = array_fill(0, $size, NULL);
$this->setData();
}
// Set initial node value
public function setData()
{
if ($this->node == NULL)
{
echo("\nEmpty Graph\n");
}
else
{
for ($index = 0; $index < $this->size; $index++)
{
$this->node[$index] = new Vertices($index);
}
}
}
// Connect two nodes
public function connect($start, $last, $length)
{
$new_edge = new AjlistNode($last, $length);
if ($this->node[$start]->next == NULL)
{
$this->node[$start]->next = $new_edge;
}
else
{
$temp = $this->node[$start]->next;
while ($temp->next != NULL)
{
$temp = $temp->next;
}
$temp->next = $new_edge;
}
}
// Add edge of two nodes
public function addEdge($start, $last, $length)
{
if ($start >= 0 && $start < $this->size &&
$last >= 0 && $last < $this->size && $this->node != NULL)
{
$this->connect($start, $last, $length);
if ($start == $last)
{
// Self looping situation
return;
}
$this->connect($last, $start, $length);
}
else
{
echo("\nHere Something Wrong\n");
}
}
public function printGraph()
{
if ($this->size > 0 && $this->node != NULL)
{
// Print graph ajlist Node value
for ($index = 0; $index < $this->size; ++$index)
{
echo("\nAdjacency list of vertex ".$index." :");
$temp = $this->node[$index]->next;
while ($temp != NULL)
{
echo(" ".$this->node[$temp->id]->data);
// visit to next edge
$temp = $temp->next;
}
}
}
}
public function isLengthGreaterThanK($index, $visit, $sum, $k)
{
if ($index < 0 || $index >= $this->size)
{
return false;
}
if ($visit[$index] == true)
{
// When node is already includes in current path
return false;
}
if ($sum > $k)
{
// When length sum is greater than k
return true;
}
// Here modified the value of visited node
$visit[$index] = true;
// This is used to iterate nodes edges
$temp = $this->node[$index]->next;
while ($temp != NULL)
{
if ($this->isLengthGreaterThanK($temp->id,
$visit, $sum + ($temp->length), $k))
{
// Found path with length greater than k
return true;
}
// Visit to next edge
$temp = $temp->next;
}
// Reset the value of visited node status
$visit[$index] = false;
return false;
}
public function checkPathGreaterThanK($source, $k)
{
$visit = array_fill(0, $this->size, false);
echo("\n Source node : ".$source);
echo("\n Length k : ".$k);
if ($this->isLengthGreaterThanK($source, $visit, 0, $k))
{
echo("\n Result : YES\n");
}
else
{
echo("\n Result : NO\n");
}
}
}
function main()
{
// 10 implies the number of nodes in graph
$g = new Graph(10);
$g->addEdge(0, 1, 9);
$g->addEdge(0, 2, 10);
$g->addEdge(0, 9, 4);
$g->addEdge(1, 3, 6);
$g->addEdge(1, 9, 5);
$g->addEdge(2, 4, 3);
$g->addEdge(2, 7, 7);
$g->addEdge(2, 9, 2);
$g->addEdge(3, 5, 5);
$g->addEdge(3, 7, 4);
$g->addEdge(3, 9, 3);
$g->addEdge(4, 6, 4);
$g->addEdge(5, 6, 3);
$g->addEdge(5, 7, 8);
$g->addEdge(6, 7, 8);
$g->addEdge(6, 8, 4);
// print graph element
$g->printGraph();
// Test A
$source = 0;
$k = 48;
$g->checkPathGreaterThanK($source, $k);
// Test B
$source = 0;
$k = 51;
$g->checkPathGreaterThanK($source, $k);
// Test C
$source = 8;
$k = 54;
$g->checkPathGreaterThanK($source, $k);
}
main();
Output
Adjacency list of vertex 0 : 1 2 9
Adjacency list of vertex 1 : 0 3 9
Adjacency list of vertex 2 : 0 4 7 9
Adjacency list of vertex 3 : 1 5 7 9
Adjacency list of vertex 4 : 2 6
Adjacency list of vertex 5 : 3 6 7
Adjacency list of vertex 6 : 4 5 7 8
Adjacency list of vertex 7 : 2 3 5 6
Adjacency list of vertex 8 : 6
Adjacency list of vertex 9 : 0 1 2 3
Source node : 0
Length k : 48
Result : YES
Source node : 0
Length k : 51
Result : NO
Source node : 8
Length k : 54
Result : YES
/*
Node JS Program for
Find if there is a path of more than k length from a source
*/
class AjlistNode
{
constructor(id, length)
{
// Set value of node key
this.id = id;
this.length = length;
this.next = null;
}
}
class Vertices
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
class Graph
{
constructor(size)
{
//set value
this.size = size;
this.node = Array(size).fill(null);
this.setData();
}
// Set initial node value
setData()
{
if (this.node == null)
{
console.log("\nEmpty Graph");
}
else
{
for (var index = 0; index < this.size; index++)
{
this.node[index] = new Vertices(index);
}
}
}
// Connect two nodes
connect(start, last, length)
{
var new_edge = new AjlistNode(last, length);
if (this.node[start].next == null)
{
this.node[start].next = new_edge;
}
else
{
var temp = this.node[start].next;
while (temp.next != null)
{
temp = temp.next;
}
temp.next = new_edge;
}
}
// Add edge of two nodes
addEdge(start, last, length)
{
if (start >= 0 && start < this.size &&
last >= 0 && last < this.size && this.node != null)
{
this.connect(start, last, length);
if (start == last)
{
// Self looping situation
return;
}
this.connect(last, start, length);
}
else
{
console.log("\nHere Something Wrong");
}
}
printGraph()
{
if (this.size > 0 && this.node != null)
{
// Print graph ajlist Node value
for (var index = 0; index < this.size; ++index)
{
process.stdout.write("\nAdjacency list of vertex " +
index + " :");
var temp = this.node[index].next;
while (temp != null)
{
process.stdout.write(" " + this.node[temp.id].data);
// visit to next edge
temp = temp.next;
}
}
}
}
isLengthGreaterThanK(index, visit, sum, k)
{
if (index < 0 || index >= this.size)
{
return false;
}
if (visit[index] == true)
{
// When node is already includes in current path
return false;
}
if (sum > k)
{
// When length sum is greater than k
return true;
}
// Here modified the value of visited node
visit[index] = true;
// This is used to iterate nodes edges
var temp = this.node[index].next;
while (temp != null)
{
if (this.isLengthGreaterThanK(
temp.id, visit, sum + (temp.length), k))
{
// Found path with length greater than k
return true;
}
// Visit to next edge
temp = temp.next;
}
// Reset the value of visited node status
visit[index] = false;
return false;
}
checkPathGreaterThanK(source, k)
{
// Set initial visited node status
var visit = Array(this.size).fill(false);
process.stdout.write("\n Source node : " + source);
process.stdout.write("\n Length k : " + k);
if (this.isLengthGreaterThanK(source, visit, 0, k))
{
process.stdout.write("\n Result : YES\n");
}
else
{
process.stdout.write("\n Result : NO\n");
}
}
}
function main()
{
// 10 implies the number of nodes in graph
var g = new Graph(10);
g.addEdge(0, 1, 9);
g.addEdge(0, 2, 10);
g.addEdge(0, 9, 4);
g.addEdge(1, 3, 6);
g.addEdge(1, 9, 5);
g.addEdge(2, 4, 3);
g.addEdge(2, 7, 7);
g.addEdge(2, 9, 2);
g.addEdge(3, 5, 5);
g.addEdge(3, 7, 4);
g.addEdge(3, 9, 3);
g.addEdge(4, 6, 4);
g.addEdge(5, 6, 3);
g.addEdge(5, 7, 8);
g.addEdge(6, 7, 8);
g.addEdge(6, 8, 4);
// print graph element
g.printGraph();
// Test A
var source = 0;
var k = 48;
g.checkPathGreaterThanK(source, k);
// Test B
source = 0;
k = 51;
g.checkPathGreaterThanK(source, k);
// Test C
source = 8;
k = 54;
g.checkPathGreaterThanK(source, k);
}
main();
Output
Adjacency list of vertex 0 : 1 2 9
Adjacency list of vertex 1 : 0 3 9
Adjacency list of vertex 2 : 0 4 7 9
Adjacency list of vertex 3 : 1 5 7 9
Adjacency list of vertex 4 : 2 6
Adjacency list of vertex 5 : 3 6 7
Adjacency list of vertex 6 : 4 5 7 8
Adjacency list of vertex 7 : 2 3 5 6
Adjacency list of vertex 8 : 6
Adjacency list of vertex 9 : 0 1 2 3
Source node : 0
Length k : 48
Result : YES
Source node : 0
Length k : 51
Result : NO
Source node : 8
Length k : 54
Result : YES
# Python 3 Program for
# Find if there is a path of more than k length from a source
class AjlistNode :
# Vertices node key
def __init__(self, id, length) :
# Set value of node key
self.id = id
self.length = length
self.next = None
class Vertices :
def __init__(self, data) :
self.data = data
self.next = None
class Graph :
# Number of Vertices
def __init__(self, size) :
# set value
self.size = size
self.node = [None] * (size)
self.setData()
# Set initial node value
def setData(self) :
if (self.node == None) :
print("\nEmpty Graph")
else :
index = 0
while (index < self.size) :
self.node[index] = Vertices(index)
index += 1
# Connect two nodes
def connect(self, start, last, length) :
new_edge = AjlistNode(last, length)
if (self.node[start].next == None) :
self.node[start].next = new_edge
else :
temp = self.node[start].next
while (temp.next != None) :
temp = temp.next
temp.next = new_edge
# Add edge of two nodes
def addEdge(self, start, last, length) :
if (start >= 0 and start < self.size and
last >= 0 and last < self.size and self.node != None) :
self.connect(start, last, length)
if (start == last) :
# Self looping situation
return
self.connect(last, start, length)
else :
print("\nHere Something Wrong")
def printGraph(self) :
if (self.size > 0 and self.node != None) :
index = 0
# Print graph ajlist Node value
while (index < self.size) :
print("\nAdjacency list of vertex ",
index ," :", end = "")
temp = self.node[index].next
while (temp != None) :
print(" ", self.node[temp.id].data, end = "")
# visit to next edge
temp = temp.next
index += 1
def isLengthGreaterThanK(self, index, visit, sum, k) :
if (index < 0 or index >= self.size) :
return False
if (visit[index] == True) :
# When node is already includes in current path
return False
if (sum > k) :
# When length sum is greater than k
return True
# Here modified the value of visited node
visit[index] = True
# This is used to iterate nodes edges
temp = self.node[index].next
while (temp != None) :
if (self.isLengthGreaterThanK(
temp.id, visit, sum + (temp.length), k)) :
# Found path with length greater than k
return True
# Visit to next edge
temp = temp.next
# Reset the value of visited node status
visit[index] = False
return False
def checkPathGreaterThanK(self, source, k) :
# Set initial visited node status
visit = [False] * (self.size)
print("\n Source node : ", source, end = "")
print("\n Length k : ", k, end = "")
if (self.isLengthGreaterThanK(source, visit, 0, k)) :
print("\n Result : YES")
else :
print("\n Result : NO")
def main() :
# 10 implies the number of nodes in graph
g = Graph(10)
g.addEdge(0, 1, 9)
g.addEdge(0, 2, 10)
g.addEdge(0, 9, 4)
g.addEdge(1, 3, 6)
g.addEdge(1, 9, 5)
g.addEdge(2, 4, 3)
g.addEdge(2, 7, 7)
g.addEdge(2, 9, 2)
g.addEdge(3, 5, 5)
g.addEdge(3, 7, 4)
g.addEdge(3, 9, 3)
g.addEdge(4, 6, 4)
g.addEdge(5, 6, 3)
g.addEdge(5, 7, 8)
g.addEdge(6, 7, 8)
g.addEdge(6, 8, 4)
# print graph element
g.printGraph()
# Test A
source = 0
k = 48
g.checkPathGreaterThanK(source, k)
# Test B
source = 0
k = 51
g.checkPathGreaterThanK(source, k)
# Test C
source = 8
k = 54
g.checkPathGreaterThanK(source, k)
if __name__ == "__main__": main()
Output
Adjacency list of vertex 0 : 1 2 9
Adjacency list of vertex 1 : 0 3 9
Adjacency list of vertex 2 : 0 4 7 9
Adjacency list of vertex 3 : 1 5 7 9
Adjacency list of vertex 4 : 2 6
Adjacency list of vertex 5 : 3 6 7
Adjacency list of vertex 6 : 4 5 7 8
Adjacency list of vertex 7 : 2 3 5 6
Adjacency list of vertex 8 : 6
Adjacency list of vertex 9 : 0 1 2 3
Source node : 0
Length k : 48
Result : YES
Source node : 0
Length k : 51
Result : NO
Source node : 8
Length k : 54
Result : YES
# Ruby Program for
# Find if there is a path of more than k length from a source
class AjlistNode
# Define the accessor and reader of class AjlistNode
attr_reader :id, :length, :next
attr_accessor :id, :length, :next
# Vertices node key
def initialize(id, length)
# Set value of node key
self.id = id
self.length = length
self.next = nil
end
end
class Vertices
# Define the accessor and reader of class Vertices
attr_reader :data, :next
attr_accessor :data, :next
def initialize(data)
self.data = data
self.next = nil
end
end
class Graph
# Define the accessor and reader of class Graph
attr_reader :size, :node
attr_accessor :size, :node
# Number of Vertices
def initialize(size)
# set value
self.size = size
self.node = Array.new(size) {nil}
self.setData()
end
# Set initial node value
def setData()
if (self.node == nil)
print("\nEmpty Graph", "\n")
else
index = 0
while (index < self.size)
self.node[index] = Vertices.new(index)
index += 1
end
end
end
# Connect two nodes
def connect(start, last, length)
new_edge = AjlistNode.new(last, length)
if (self.node[start].next == nil)
self.node[start].next = new_edge
else
temp = self.node[start].next
while (temp.next != nil)
temp = temp.next
end
temp.next = new_edge
end
end
# Add edge of two nodes
def addEdge(start, last, length)
if (start >= 0 && start < self.size &&
last >= 0 && last < self.size && self.node != nil)
self.connect(start, last, length)
if (start == last)
# Self looping situation
return
end
self.connect(last, start, length)
else
print("\nHere Something Wrong", "\n")
end
end
def printGraph()
if (self.size > 0 && self.node != nil)
index = 0
# Print graph ajlist Node value
while (index < self.size)
print("\nAdjacency list of vertex ", index ," :")
temp = self.node[index].next
while (temp != nil)
print(" ", self.node[temp.id].data)
# visit to next edge
temp = temp.next
end
index += 1
end
end
end
def isLengthGreaterThanK(index, visit, sum, k)
if (index < 0 || index >= self.size)
return false
end
if (visit[index] == true)
# When node is already includes in current path
return false
end
if (sum > k)
# When length sum is greater than k
return true
end
# Here modified the value of visited node
visit[index] = true
# This is used to iterate nodes edges
temp = self.node[index].next
while (temp != nil)
if (self.isLengthGreaterThanK(
temp.id, visit, sum + (temp.length), k))
# Found path with length greater than k
return true
end
# Visit to next edge
temp = temp.next
end
# Reset the value of visited node status
visit[index] = false
return false
end
def checkPathGreaterThanK(source, k)
# Set initial visited node status
visit = Array.new(self.size) {false}
print("\n Source node : ", source)
print("\n Length k : ", k)
if (self.isLengthGreaterThanK(source, visit, 0, k))
print("\n Result : YES\n")
else
print("\n Result : NO\n")
end
end
end
def main()
# 10 implies the number of nodes in graph
g = Graph.new(10)
g.addEdge(0, 1, 9)
g.addEdge(0, 2, 10)
g.addEdge(0, 9, 4)
g.addEdge(1, 3, 6)
g.addEdge(1, 9, 5)
g.addEdge(2, 4, 3)
g.addEdge(2, 7, 7)
g.addEdge(2, 9, 2)
g.addEdge(3, 5, 5)
g.addEdge(3, 7, 4)
g.addEdge(3, 9, 3)
g.addEdge(4, 6, 4)
g.addEdge(5, 6, 3)
g.addEdge(5, 7, 8)
g.addEdge(6, 7, 8)
g.addEdge(6, 8, 4)
# print graph element
g.printGraph()
# Test A
source = 0
k = 48
g.checkPathGreaterThanK(source, k)
# Test B
source = 0
k = 51
g.checkPathGreaterThanK(source, k)
# Test C
source = 8
k = 54
g.checkPathGreaterThanK(source, k)
end
main()
Output
Adjacency list of vertex 0 : 1 2 9
Adjacency list of vertex 1 : 0 3 9
Adjacency list of vertex 2 : 0 4 7 9
Adjacency list of vertex 3 : 1 5 7 9
Adjacency list of vertex 4 : 2 6
Adjacency list of vertex 5 : 3 6 7
Adjacency list of vertex 6 : 4 5 7 8
Adjacency list of vertex 7 : 2 3 5 6
Adjacency list of vertex 8 : 6
Adjacency list of vertex 9 : 0 1 2 3
Source node : 0
Length k : 48
Result : YES
Source node : 0
Length k : 51
Result : NO
Source node : 8
Length k : 54
Result : YES
/*
Scala Program for
Find if there is a path of more than k length from a source
*/
class AjlistNode(
// Vertices node key
var id: Int,
var length: Int,
var next: AjlistNode)
{
def this(id: Int, length: Int)
{
// Set value of node key
this(id,length,null);
}
}
class Vertices(var data: Int,var next: AjlistNode)
{
def this(data: Int)
{
this(data,null);
}
}
class Graph(
// Number of Vertices
var size: Int,
var node: Array[Vertices])
{
def this(size: Int)
{
//set value
this(size,Array.fill[Vertices](size)(null));
this.setData();
}
// Set initial node value
def setData(): Unit = {
if (node == null)
{
println("\nEmpty Graph");
}
else
{
var index: Int = 0;
while (index < size)
{
node(index) = new Vertices(index);
index += 1;
}
}
}
// Connect two nodes
def connect(start: Int, last: Int, length: Int): Unit = {
var new_edge: AjlistNode = new AjlistNode(last, length);
if (node(start).next == null)
{
node(start).next = new_edge;
}
else
{
var temp: AjlistNode = node(start).next;
while (temp.next != null)
{
temp = temp.next;
}
temp.next = new_edge;
}
}
// Add edge of two nodes
def addEdge(start: Int, last: Int, length: Int): Unit = {
if (start >= 0 && start < size && last >= 0 &&
last < size && node != null)
{
connect(start, last, length);
if (start == last)
{
// Self looping situation
return;
}
connect(last, start, length);
}
else
{
println("\nHere Something Wrong");
}
}
def printGraph(): Unit = {
if (size > 0 && node != null)
{
var index: Int = 0;
// Print graph ajlist Node value
while (index < size)
{
print("\nAdjacency list of vertex " + index + " :");
var temp: AjlistNode = node(index).next;
while (temp != null)
{
print(" " + node(temp.id).data);
// visit to next edge
temp = temp.next;
}
index += 1;
}
}
}
def isLengthGreaterThanK(
index: Int,
visit: Array[Boolean],
sum: Int, k: Int): Boolean = {
if (index < 0 || index >= this.size)
{
return false;
}
if (visit(index) == true)
{
// When node is already includes in current path
return false;
}
if (sum > k)
{
// When length sum is greater than k
return true;
}
// Here modified the value of visited node
visit(index) = true;
// This is used to iterate nodes edges
var temp: AjlistNode = node(index).next;
while (temp != null)
{
if (isLengthGreaterThanK(
temp.id, visit,
sum + (temp.length), k))
{
// Found path with length greater than k
return true;
}
// Visit to next edge
temp = temp.next;
}
// Reset the value of visited node status
visit(index) = false;
return false;
}
def checkPathGreaterThanK(source: Int, k: Int): Unit = {
// Set initial visited node status
var visit: Array[Boolean] = Array.fill[Boolean](this.size)(false);
print("\n Source node : " + source);
print("\n Length k : " + k);
if (isLengthGreaterThanK(source, visit, 0, k))
{
print("\n Result : YES\n");
}
else
{
print("\n Result : NO\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// 10 implies the number of nodes in graph
var g: Graph = new Graph(10);
g.addEdge(0, 1, 9);
g.addEdge(0, 2, 10);
g.addEdge(0, 9, 4);
g.addEdge(1, 3, 6);
g.addEdge(1, 9, 5);
g.addEdge(2, 4, 3);
g.addEdge(2, 7, 7);
g.addEdge(2, 9, 2);
g.addEdge(3, 5, 5);
g.addEdge(3, 7, 4);
g.addEdge(3, 9, 3);
g.addEdge(4, 6, 4);
g.addEdge(5, 6, 3);
g.addEdge(5, 7, 8);
g.addEdge(6, 7, 8);
g.addEdge(6, 8, 4);
// print graph element
g.printGraph();
// Test A
var source: Int = 0;
var k: Int = 48;
g.checkPathGreaterThanK(source, k);
// Test B
source = 0;
k = 51;
g.checkPathGreaterThanK(source, k);
// Test C
source = 8;
k = 54;
g.checkPathGreaterThanK(source, k);
}
}
Output
Adjacency list of vertex 0 : 1 2 9
Adjacency list of vertex 1 : 0 3 9
Adjacency list of vertex 2 : 0 4 7 9
Adjacency list of vertex 3 : 1 5 7 9
Adjacency list of vertex 4 : 2 6
Adjacency list of vertex 5 : 3 6 7
Adjacency list of vertex 6 : 4 5 7 8
Adjacency list of vertex 7 : 2 3 5 6
Adjacency list of vertex 8 : 6
Adjacency list of vertex 9 : 0 1 2 3
Source node : 0
Length k : 48
Result : YES
Source node : 0
Length k : 51
Result : NO
Source node : 8
Length k : 54
Result : YES
/*
Swift 4 Program for
Find if there is a path of more than k length from a source
*/
class AjlistNode
{
// Vertices node key
var id: Int;
var length: Int;
var next: AjlistNode? ;
init(_ id: Int, _ length: Int)
{
// Set value of node key
self.id = id;
self.length = length;
self.next = nil;
}
}
class Vertices
{
var data: Int;
var next: AjlistNode? ;
init(_ data: Int)
{
self.data = data;
self.next = nil;
}
}
class Graph
{
// Number of Vertices
var size: Int;
var node: [Vertices? ];
init(_ size: Int)
{
//set value
self.size = size;
self.node = Array(repeating: nil, count: size);
self.setData();
}
// Set initial node value
func setData()
{
var index: Int = 0;
while (index < self.size)
{
self.node[index] = Vertices(index);
index += 1;
}
}
// Connect two nodes
func connect(_ start: Int, _ last: Int, _ length: Int)
{
let new_edge: AjlistNode = AjlistNode(last, length);
if (self.node[start]!.next == nil)
{
self.node[start]!.next = new_edge;
}
else
{
var temp: AjlistNode? = self.node[start]!.next;
while (temp!.next != nil)
{
temp = temp!.next;
}
temp!.next = new_edge;
}
}
// Add edge of two nodes
func addEdge(_ start: Int, _ last: Int, _ length: Int)
{
if (start >= 0 && start < self.size &&
last >= 0 && last < self.size && self.size > 0)
{
self.connect(start, last, length);
if (start == last)
{
// Self looping situation
return;
}
self.connect(last, start, length);
}
else
{
print("\nHere Something Wrong");
}
}
func printGraph()
{
if (self.size > 0)
{
var index: Int = 0;
// Print graph ajlist Node value
while (index < self.size)
{
print("\nAdjacency list of vertex ",
index, " :", terminator: "");
var temp: AjlistNode? = self.node[index]!.next;
while (temp != nil)
{
print(" ",
self.node[temp!.id]!.data, terminator: "");
// visit to next edge
temp = temp!.next;
}
index += 1;
}
}
}
func isLengthGreaterThanK(
_ index: Int, _ visit: inout[Bool],
_ sum: Int, _ k: Int) -> Bool
{
if (index < 0 || index >= self.size)
{
return false;
}
if (visit[index] == true)
{
// When node is already includes in current path
return false;
}
if (sum > k)
{
// When length sum is greater than k
return true;
}
// Here modified the value of visited node
visit[index] = true;
// This is used to iterate nodes edges
var temp: AjlistNode? = self.node[index]!.next;
while (temp != nil)
{
if (self.isLengthGreaterThanK(
temp!.id, &visit, sum + (temp!.length), k))
{
// Found path with length greater than k
return true;
}
// Visit to next edge
temp = temp!.next;
}
// Reset the value of visited node status
visit[index] = false;
return false;
}
func checkPathGreaterThanK(_ source: Int, _ k: Int)
{
// Set initial visited node status
var visit: [Bool] = Array(repeating: false, count: self.size);
print("\n Source node : ", source, terminator: "");
print("\n Length k : ", k, terminator: "");
if (self.isLengthGreaterThanK(source, &visit, 0, k))
{
print("\n Result : YES");
}
else
{
print("\n Result : NO");
}
}
}
func main()
{
// 10 implies the number of nodes in graph
let g: Graph = Graph(10);
g.addEdge(0, 1, 9);
g.addEdge(0, 2, 10);
g.addEdge(0, 9, 4);
g.addEdge(1, 3, 6);
g.addEdge(1, 9, 5);
g.addEdge(2, 4, 3);
g.addEdge(2, 7, 7);
g.addEdge(2, 9, 2);
g.addEdge(3, 5, 5);
g.addEdge(3, 7, 4);
g.addEdge(3, 9, 3);
g.addEdge(4, 6, 4);
g.addEdge(5, 6, 3);
g.addEdge(5, 7, 8);
g.addEdge(6, 7, 8);
g.addEdge(6, 8, 4);
// print graph element
g.printGraph();
// Test A
var source: Int = 0;
var k: Int = 48;
g.checkPathGreaterThanK(source, k);
// Test B
source = 0;
k = 51;
g.checkPathGreaterThanK(source, k);
// Test C
source = 8;
k = 54;
g.checkPathGreaterThanK(source, k);
}
main();
Output
Adjacency list of vertex 0 : 1 2 9
Adjacency list of vertex 1 : 0 3 9
Adjacency list of vertex 2 : 0 4 7 9
Adjacency list of vertex 3 : 1 5 7 9
Adjacency list of vertex 4 : 2 6
Adjacency list of vertex 5 : 3 6 7
Adjacency list of vertex 6 : 4 5 7 8
Adjacency list of vertex 7 : 2 3 5 6
Adjacency list of vertex 8 : 6
Adjacency list of vertex 9 : 0 1 2 3
Source node : 0
Length k : 48
Result : YES
Source node : 0
Length k : 51
Result : NO
Source node : 8
Length k : 54
Result : YES
/*
Kotlin Program for
Find if there is a path of more than k length from a source
*/
class AjlistNode
{
// Vertices node key
var id: Int;
var length: Int;
var next: AjlistNode ? ;
constructor(id: Int, length: Int)
{
// Set value of node key
this.id = id;
this.length = length;
this.next = null;
}
}
class Vertices
{
var data: Int;
var next: AjlistNode ? ;
constructor(data: Int)
{
this.data = data;
this.next = null;
}
}
class Graph
{
// Number of Vertices
var size: Int;
var node: Array < Vertices?> ;
constructor(size: Int)
{
//set value
this.size = size;
this.node = Array(size)
{
null
};
this.setData();
}
// Set initial node value
fun setData(): Unit
{
if (this.size <= 0)
{
println("\nEmpty Graph");
}
else
{
var index: Int = 0;
while (index < this.size)
{
this.node[index] = Vertices(index);
index += 1;
}
}
}
// Connect two nodes
fun connect(start: Int, last: Int, length: Int): Unit
{
val new_edge: AjlistNode = AjlistNode(last, length);
if (this.node[start]?.next == null)
{
this.node[start]?.next = new_edge;
}
else
{
var temp: AjlistNode ? = this.node[start]!!.next;
while (temp?.next != null)
{
temp = temp.next;
}
temp!!.next = new_edge;
}
}
// Add edge of two nodes
fun addEdge(start: Int, last: Int, length: Int): Unit
{
if (start >= 0 && start < this.size && last >= 0 && last < this.size && this.size > 0)
{
this.connect(start, last, length);
if (start == last)
{
// Self looping situation
return;
}
this.connect(last, start, length);
}
else
{
println("\nHere Something Wrong");
}
}
fun printGraph(): Unit
{
if (this.size > 0)
{
var index: Int = 0;
// Print graph ajlist Node value
while (index < this.size)
{
print("\nAdjacency list of vertex " + index + " :");
var temp: AjlistNode ? = this.node[index]?.next;
while (temp != null)
{
print(" " + this.node[temp.id]?.data);
// visit to next edge
temp = temp.next;
}
index += 1;
}
}
}
fun isLengthGreaterThanK(index: Int, visit: Array < Boolean > , sum: Int, k: Int): Boolean
{
if (index < 0 || index >= this.size)
{
return false;
}
if (visit[index] == true)
{
// When node is already includes in current path
return false;
}
if (sum > k)
{
// When length sum is greater than k
return true;
}
// Here modified the value of visited node
visit[index] = true;
// This is used to iterate nodes edges
var temp: AjlistNode ? = this.node[index]?.next;
while (temp != null)
{
if (this.isLengthGreaterThanK(
temp.id, visit, sum + (temp.length), k))
{
// Found path with length greater than k
return true;
}
// Visit to next edge
temp = temp.next;
}
// Reset the value of visited node status
visit[index] = false;
return false;
}
fun checkPathGreaterThanK(source: Int, k: Int): Unit
{
// Set initial visited node status
var visit: Array < Boolean > = Array(this.size)
{
false
};
print("\n Source node : " + source);
print("\n Length k : " + k);
if (this.isLengthGreaterThanK(source, visit, 0, k))
{
print("\n Result : YES\n");
}
else
{
print("\n Result : NO\n");
}
}
}
fun main(args: Array < String > ): Unit
{
// 10 implies the number of nodes in graph
val g: Graph = Graph(10);
g.addEdge(0, 1, 9);
g.addEdge(0, 2, 10);
g.addEdge(0, 9, 4);
g.addEdge(1, 3, 6);
g.addEdge(1, 9, 5);
g.addEdge(2, 4, 3);
g.addEdge(2, 7, 7);
g.addEdge(2, 9, 2);
g.addEdge(3, 5, 5);
g.addEdge(3, 7, 4);
g.addEdge(3, 9, 3);
g.addEdge(4, 6, 4);
g.addEdge(5, 6, 3);
g.addEdge(5, 7, 8);
g.addEdge(6, 7, 8);
g.addEdge(6, 8, 4);
// print graph element
g.printGraph();
// Test A
var source: Int = 0;
var k: Int = 48;
g.checkPathGreaterThanK(source, k);
// Test B
source = 0;
k = 51;
g.checkPathGreaterThanK(source, k);
// Test C
source = 8;
k = 54;
g.checkPathGreaterThanK(source, k);
}
Output
Adjacency list of vertex 0 : 1 2 9
Adjacency list of vertex 1 : 0 3 9
Adjacency list of vertex 2 : 0 4 7 9
Adjacency list of vertex 3 : 1 5 7 9
Adjacency list of vertex 4 : 2 6
Adjacency list of vertex 5 : 3 6 7
Adjacency list of vertex 6 : 4 5 7 8
Adjacency list of vertex 7 : 2 3 5 6
Adjacency list of vertex 8 : 6
Adjacency list of vertex 9 : 0 1 2 3
Source node : 0
Length k : 48
Result : YES
Source node : 0
Length k : 51
Result : NO
Source node : 8
Length k : 54
Result : YES
Resultant Output Explanation
It performs a Depth-First Search (DFS) and checks if there is a path of length greater than 'k' starting from a given source node. The output explains the results for various test cases by printing "Result: YES" if a suitable path is found and "Result: NO" otherwise.
Time Complexity
The time complexity of the algorithm depends on the number of vertices and edges in the graph. In the worst case, it's O(V + E), where 'V' is the number of vertices and 'E' is the number of edges. The algorithm visits each vertex once and explores all its outgoing edges, making it a linear-time operation.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment