如何在不返回到上一个节点的情况下知道图中连接节点的最大数量

Question

假设我们需要画一个有很多点的图。例如输入：{1#2,2#3.3#11,1#11,4#11,4#5,5#6,4#12}输出：7

一个节点可以直接连接到许多其他节点。我们需要在这个图中找到最大连接节点，但不允许返回。

我已经尝试了很多算法来解决这个问题，但都找不到。有人能帮我吗？

提前感谢，Krishan

Answer 1

您对问题的定义仍然有点模糊——至少从我的角度来看是这样。然而，我认为你正在寻找（有向或无向？）图中最长的路径。一般来说，这是一个NP完全问题。看看这个wikepedia条目。这应该成为进一步研究的起点。

Answer 2

以下是python代码，它将查找图中最大组件（最大连接节点）的数量。然而，这不是最佳解决方案（也就是说，缓慢），但可能对您开始有用

#!/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)