15,904,416 members

Python

def dfs(i): status[i] = "visited" # mark the current node as visited for j in range(1,n+1): # iterate over all nodes if Graph[j][i] == 1: # if there is an edge from node j to node i if status[j] == "unvisited": # if node j has not been visited yet dfs(j) # recursively call the dfs function on node j elif status[j] == "visited": # if node j has already been visited print("cycle detected") # a cycle has been detected exit(0) # exit the program status[i] = "finished" # mark the current node as finished print(i) # print the current node n = 5 # number of nodes in the graph Graph = [[0 for j in range(n+1)] for i in range(n+1)] # create a n x n matrix to represent the graph Graph[1][3] = 1 Graph[1][4] = 1 Graph[2][3] = 1 Graph[3][5] = 1 Graph[4][5] = 1 status = ["unvisited" for i in range(n+1)] # create a list to keep track of the status of each node (unvisited, visited, or finished) adjacent = [0 for i in range(n+1)] # create a list to keep track of the number of adjacent nodes for each node for i in range(1,n+1): # iterate over all nodes for j in range(1,n+1): # iterate over all nodes if Graph[i][j] == 1: # if there is an edge from node i to node j adjacent[i] += 1 # increment the number of adjacent nodes for node i for i in range(1,n+1): # iterate over all nodes if adjacent[i] == 0: # if node i has no adjacent nodes dfs(i) # call the dfs function on node i

so I have this assignment and my dr gave us the pseudo-code for it and told us to make it into an executable code.

I want the graph and output to be like this :

(1)->(3) /(1)->(4)/ (2)->(3)/ (3)->(5)/ (4)->(5)

1,2,3,4,5

and detect if there is a cycle I know that there is no cycle in this graph but if I wanted another graph I want to detect whether there is a cycle or not. I put a lot of comments to help you understand the code.

and thanks, guys.

here is the code that I wrote:

Comments

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject,
20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8
+1 (416) 849-8900

Progmatically walk the graph and output to screen or string.