Skip to main content

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

  1. 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'.
  2. The function first checks if 'index' is within bounds and if the node has already been visited. If so, it returns false.
  3. If the sum of the path is greater than 'k', it returns true.
  4. Set the visited status of 'index' to true.
  5. Iterate through the neighbors of 'index'. For each neighbor, recursively call the function with updated values for 'index', 'visit', 'sum', and 'k'.
  6. After trying all neighbors, reset the visited status of 'index' and return false.
  7. Implement checkPathGreaterThanK(source, k) that initializes the visited array, then calls isLengthGreaterThanK() 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.





Comment

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







Sergey Ivanov     331 Day ago
I am from Ukraine, I am 81 years old. I really like your work. Thank you! I'm writing a textbook for students on data structures and algorithms. I use your programs, supplement them with explanatory illustrations It would be nice if you developed a golang implementation of Dijkstra's algorithm. What do you recommend?