Comment connaître le nombre maximal de nœuds connectés dans un graphique sans revenir au nœud précédent

Question

Supposons que nous ayons besoin de tracer un graphique avec beaucoup de points. Par exemple INPUT: {1 # 2,2 # 3,3 # 11,1 # 11,4 # 11,4 # 5,5 # 6,4 # 12} SORTIE: 7

Un noeud peut être connecté à beaucoup d'autres nœuds directement. Nous devons trouver les nœuds max connectés dans ce graphique mais pas autorisés à revenir en arrière.

J'ai essayé beaucoup d'obtenir n'importe quel algorithme pour résoudre ce problème mais pas capable de trouver. Quelqu'un peut-il m'aider s'il vous plaît pour cela?

Merci à l'avance, Krishan

Answer 1

Votre définition du problème est encore un peu vague - au moins de mon point de vue. Cependant, je pense que vous cherchez le plus long chemin dans un graphe (dirigé ou non?). En général, il s'agit d'un problème NP-complet. Jetez un oeil à this wikepedia entry. Cela devrait servir de point de départ pour d'autres recherches.

Answer 2

Voici le code python qui trouvera le nombre de composants maximum (maximum de nœuds connectés) dans un graphique. Cependant, il n'est pas une solution optimale (a.k.a, lent), mais pourrait être utile pour vous de commencer

#!/bin/python 
max_count = 0 

def count_components(adj_list,r,c,count): 
    global max_count 
    row = adj_list[r] 

    #count 
    connections = 0 
    for j in range(len(row)): 
     if row[j]==1: 
      connections+=1 
    count+=connections 

    #traverse 
    for j in range(len(row)): 
     if row[j]==1:    
      adj_list[j][r]=0 
      count_components(adj_list,j,r,count) 
    #print 'count = {}'.format(count) 
    if count>max_count: 
     max_count = count 

def get_max_num_of_connected_component(adj_list): 

    for i in range(len(adj_list)): 
     row = adj_list[i] 
     for j in range(len(row)): 
      if row[j]==1: 
       count_components(adj_list,i,j,1) 
       break 

     #print_adjecency_list(adj_list) 
    #print 'max_count = {}'.format(max_count) 
    return max_count 
def print_adjecency_list(adj_list): 
    for i in range(len(adj_list)): 
     row = adj_list[i] 
     for j in range(len(row)): 
      print row[j], 
     print 
    print 
import sys 

n, m = raw_input().strip().split(' ') 
n, m = [int(n), int(m)] 
route = [] 
for route_i in xrange(m): 
    route_temp = map(int,raw_input().strip().split(' ')) 
    route.append(route_temp) 
# Write Your Code Here 

# generate NxM adjecency list of 
adjecency_list=[] 
for i in range(n): 
    row = [] 
    for j in range(n): 
     row.append(0) 
    adjecency_list.append(row) 

for road in route: 
    r = road[0]-1 
    c = road[1]-1 
    adjecency_row = adjecency_list[r] 
    adjecency_row[c]=1 
    adjecency_list[r] = adjecency_row 

    r = road[1]-1 
    c = road[0]-1 
    adjecency_row = adjecency_list[r] 
    adjecency_row[c]=1 
    adjecency_list[r] = adjecency_row 

#print_adjecency_list(adjecency_list) 

print get_max_num_of_connected_component(adjecency_list)