Create table graph (parent bigint not NULL, child bigint not NULL, [weight] int not NULL)

insert into graph
Values 
-- 1 граф
(1, 1, 1), (1, 2, 1), (1, 3, 10), (2, 3, 2), (3, 1, 3), (3, 6, 1), (6, 6, 2)
-- 2 граф
(4, 4, 1), (4, 5, 1), (5, 4, 2), (5, 4, 1)

;with cte as (
	select
		start_node  =parent
		,node		=child
		,[path]		=cast('/'+cast(parent as varchar(10))+'/'+cast(child as varchar(10))+'/' as varchar(max))
	from graph 
	where parent<>child

	union all

	select 
		cte.start_node
		,node	=t.child
		,[path]	=cast(cte.[path]+cast(t.child as varchar(10))+'/' as varchar(max))
	from graph t inner join cte on t.parent=cte.node
	where cte.[path] not like '%/'+cast(t.child as varchar(10))+'/%'
)

select 
	* 
from cte  
order by 1

drop table if exists #t;

declare @g table (parent bigint not NULL, child bigint not NULL, [weight] int not NULL);

insert into @g
Values 
-- 1 граф
(1, 1, 1), (1, 2, 1), (1, 3, 10), (2, 3, 2), (3, 1, 3), (3, 6, 1), (6, 6, 2),
-- 2 граф
(4, 4, 1), (4, 5, 1), (5, 4, 2), (5, 4, 1);

with g as
(
 select
  parent as root, parent, child, '/' + cast(parent as varchar(max)) as [path]
 from
  @g

 union all

 select
  g.root, c.parent, c.child, g.[path] + p.[path]
 from
  g join
  @g c on c.parent = g.child cross apply
  (select '/' + cast(c.parent as varchar(10))) p([path])
 where
  g.[path] + '/' not like '%' + p.[path] + '/%'
)
select root, parent, child, [path] + '/' as [path] into #t from g;

with s as
(
 select
  a.root, string_agg(a.child, '/') within group (order by a.child) as graph_id
 from
  (select distinct root, child from #t) a
 group by
  a.root
),
w as
(
 select
  s.*, row_number() over (partition by s.graph_id order by g.weight desc) as rn
 from
  s join
  @g g on g.parent = s.root
)
select distinct
 w.root, t.child
from
 w join
 #t t on t.root = w.root
where
 w.rn = 1
order by
 w.root;

declare @graph table (parent bigint not NULL, child bigint not NULL, [weight] int not NULL, gID bigint, primary key(parent, child, [weight]), unique(child, parent, [weight]) );

insert into @graph(parent, child, [weight])
Values 
-- 1 граф
(1, 1, 1), (1, 2, 1), (1, 3, 10), (2, 3, 2), (3, 1, 3), (3, 6, 1), (6, 6, 2)
-- 2 граф
, (4, 4, 1), (4, 5, 1), (5, 4, 2), (5, 4, 1);

with t as ( select *, n = row_number() over( order by 1/0 ) from @graph )
  update t set gID = n from t;

declare @rc int = 1;

while @rc > 0 begin

  with t as ( select * from @graph )
     update t set gID = t1.gID
	   from t inner join t as t1 on t.child = t1.parent
	   where t.gID > t1.gID 
  ;
  set @rc = @@ROWCOUNT;

  with t as ( select * from @graph )
     update t set gID = t1.gID
	   from t inner join t as t1 on t1.child = t.parent
	   where t.gID > t1.gID 
  ;
  set @rc = @rc + @@ROWCOUNT;

  with t as ( select * from @graph )
     update t set gID = t1.gID
	   from t inner join t as t1 on t1.child = t.child
	   where t.gID > t1.gID 
  ;
  set @rc = @rc + @@ROWCOUNT;

  with t as ( select * from @graph )
     update t set gID = t1.gID
	   from t inner join t as t1 on t1.parent = t.parent
	   where t.gID > t1.gID 
  ;
  set @rc = @rc + @@ROWCOUNT;

end;

select * from @graph order by gID;

select gID, max([weight]) from @graph group by gID

if OBJECT_ID('t_node_sequence') is not null
drop table t_node_sequence
go
if OBJECT_ID('t_node_sequence') is  null
create table t_node_sequence
(parent bigint not NULL, child bigint not NULL, graph_id int)
go
if OBJECT_ID('t_single_graph') is not null
drop table t_single_graph
go
create  table t_single_graph
(parent bigint not NULL, child bigint not NULL, [weight] int not NULL,graph_id int)
go

create proc p_first_node(@graph_id int)
as
begin


insert into t_node_sequence
(parent,child,graph_id)
select top 1 parent,child,graph_id
from graph
where 
[weight]=(select max([weight]) from graph where @graph_id=graph_id)
and graph_id=@graph_id

delete t
from t_single_graph t,t_node_sequence t1
where t.parent=t1.parent  and t.child=t1.child
and t.graph_id=@graph_id

return
end

--------------------------------------------------------------------------------------------------
create proc p_next_node(@new_parent int,@graph_id int)
as
begin
declare @parent int, @child int

if 
not exists(select * from t_single_graph where @graph_id=graph_id and @new_parent=parent
and parent<>child)
return

select top 1
@parent=parent, @child=child
from t_single_graph
where @new_parent=parent and @graph_id=graph_id
and parent<>child


insert into t_node_sequence
(parent,child,graph_id)
select @new_parent,@child,@graph_id

delete t_single_graph
where parent=@parent  and @child=child

set @new_parent=@child
exec p_next_node @new_parent ,@graph_id 
return
end

if OBJECT_ID('t_node_sequence') is not null
drop table t_node_sequence
go
if OBJECT_ID('t_node_sequence') is  null
create table t_node_sequence
(parent bigint not NULL, child bigint not NULL, graph_id int)
go
if OBJECT_ID('t_single_graph') is not null
drop table t_single_graph
go
create  table t_single_graph
(parent bigint not NULL, child bigint not NULL, [weight] int not NULL,graph_id int)
go
--=====================================================
insert into t_single_graph
select * from graph where graph_id=1
--=====================================================
declare @new_parent int
exec p_first_node 1
select @new_parent=child from t_node_sequence
--select @new_parent
 
 exec p_next_node @new_parent,1
 

insert into t_node_sequence --напоследок загоняем петли
(parent,child,graph_id)
 select parent,child,graph_id
 from graph
where graph_id=1 
 and parent=child
 
 select * from t_node_sequence
 order by parent,child

if OBJECT_ID('t_node_sequence') is not null
drop table t_node_sequence
go
if OBJECT_ID('t_node_sequence') is  null
create table t_node_sequence
(parent bigint not NULL, child bigint not NULL, graph_id int)
go
if OBJECT_ID('t_single_graph') is not null
drop table t_single_graph
go
create  table t_single_graph
(parent bigint not NULL, child bigint not NULL, [weight] int not NULL,graph_id int)
go
--=====================================================
insert into t_single_graph
select * from graph where graph_id=2
--=====================================================
declare @new_parent int
exec p_first_node 2
select @new_parent=child from t_node_sequence
--select @new_parent
 
 exec p_next_node @new_parent,2
 
insert into t_node_sequence --напоследок загоняем петли
(parent,child,graph_id)
 select parent,child,graph_id
 from graph
where graph_id=2 
 and parent=child
 
 select * from t_node_sequence
 order by parent,child