Hamiltonian cycle algorithm using Backtracking technique.

Algorithm:
Algorithm NextValue(K)
{
repeat
{
x[k] := (x[k+1] mod (n+1));
if (x[k] = 0) then return;
if (G[x[k-1], x[k]] != 0) then
{
for j := 1 to k-1 do if (x[j] = x[k]) then break;
if (j = k) then
if ((k < n) or ((K = n) and G[x[n], x[l]] != 0))
then return;
}
}until false
}
Algorithm Hamiltonian(k)
{
repeat
{
NextValue(k);
if (x[k]=0) then return;
if (k=n) then write (x[1:n]);
else Hamiltonian(k + 1);
} until (false);
}

Source Code:
def hamiltonian_cycle(graph):
 n = len(graph)
 path = [-1] * n
 def is_valid(v, k):
 if graph[path[k-1]][v] == 0:
 return False
 if v in path[:k]:
 return False
 return True
 def solve(k):
 if k == n:
 if graph[path[k-1]][path[0]] == 1:
 return True
 else:
return False
 for v in range(1, n):
 if is_valid(v, k):
 path[k] = v
 if solve(k+1):
 return True
 path[k] = -1
 return False
 path[0] = 0
 if solve(1):
 return path
 else:
 return None
graph = [[0, 1, 0, 1, 0],
 [1, 0, 1, 1, 1],
 [0, 1, 0, 0, 1],
 [1, 1, 0, 0, 1],
 [0, 1, 1, 1, 0]]
hamiltonian_cycle(graph)

Comments

Post a Comment

Popular posts from this blog

2. Create 3 private networks namely N1, N2 and N3, Send the data from N1 to N2. If the packets are transferring from N3, it shouldn't accept the packets. Accordingly develop the security features.Create 3 private networks namely N1, N2 and N3, Send the data from N1 to N2. If the packets are transferring from N3, it shouldn't accept the packets. Accordingly develop the security features.

Image
 In Cisco Packet Tracer, you can simulate this scenario by configuring access control lists (ACLs) on routers to control the flow of traffic between the networks. Here's a basic example: Procedure  1. **Create the Networks:**    - Place three routers on the workspace and label them R1, R2, and R3.    - Connect the routers as follows:      - Connect R1 to R2 and R3.      - Connect R2 to R3.    - Assign IP addresses to the router interfaces for each network (N1, N2, N3). 2. **Configure Router ACLs:**    - Access the CLI of each router.    For R1 (assuming FastEthernet interfaces):    ```bash    enable    configure terminal    interface FastEthernet0/0    ip address <N1_IP> <Subnet_Mask>    exit    interface FastEthernet0/1    ip address <N2_IP> <Subnet_Mask>    exit    access-li...
Read more

Kruskal algorithm using greedy technique.

Algorithm: Algorithm Kruskal(E, cost, n, t) { Construct a heap out of the edge costs using Heapify; for i:=1 to n, do parent[i]:=—1; i := O; mincost := 0.0; while ( (i < n — 1) and (heap not empty)) do       { Delete a minimum cost edge (u, v) from the heap and reheapify using Adjust; j:=Find(u); k := Find(v); if (j!=k) then        { i:=i+1; t[i, 1] := u; t[i, 2]:=v; mincost := mincost + cost[u, v]; Union(j, k); }                 } if (i != n — 1) then write ("No spanning tree"); else return mincost; } Source Code: def kruskal(E, cost, n): # E is the edge set, cost is the cost matrix, n is the number of vertices T = [] # T is the set of edges in the tree S = [] # S is the set of vertices in the tree while len(T) < n ...
Read more