c# - 如何知道图中的最大连接节点数 - 无需返回前一个节点

Question

假设我们需要绘制一个包含许多点的图形。例如输入：{1#2,2#3,3#11,1#11,4#11,4#5,5#6,4#12} 输出：7

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

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

提前致谢， 克里山

Answer 1

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

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)