Click here to Skip to main content
15,881,872 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
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


What I have tried:

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:
Posted
Comments
Graeme_Grant 26-May-23 17:41pm    
Ah, homework, always fun...

Progmatically walk the graph and output to screen or string.
Richard MacCutchan 27-May-23 4:21am    
Print out the node id and status each time in the loop.

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