C#에서 토폴로지 정렬 알고리즘을 구현하는 방법-C#.Net 튜토리얼-php.cn

C#에서 토폴로지 정렬 알고리즘을 구현하는 방법

王林

풀어 주다： 2023-09-21 08:09:02

원래의

1244명이 탐색했습니다.

C#에서 토폴로지 정렬 알고리즘을 구현하는 방법

C#에서 위상 정렬 알고리즘을 구현하려면 구체적인 코드 예제가 필요합니다.

위상 정렬은 방향성 그래프에서 노드 간의 종속성을 해결하는 데 사용되는 일반적인 그래프 알고리즘입니다. 소프트웨어 개발에서 토폴로지 정렬은 작업 스케줄링 및 컴파일 순서와 같은 문제를 해결하는 데 자주 사용됩니다. 이 문서에서는 C#에서 토폴로지 정렬 알고리즘을 구현하는 방법을 소개하고 구체적인 코드 예제를 제공합니다.

알고리즘 원리

위상 정렬 알고리즘은 방향성 그래프의 인접 목록을 설정한 후 깊이 우선 탐색(DFS) 또는 너비 우선 탐색(BFS)을 사용하여 그래프의 노드를 순회하고 특정 순서대로 출력합니다.

구체적인 단계는 다음과 같습니다.

1) 유향 그래프의 인접 목록을 구성합니다. 유향 그래프의 각 노드를 구조로 표현하고, 노드의 종속성을 유향 간선으로 표현합니다.

2) 각 노드의 내부 차수 계산: 인접 목록을 순회하고 각 노드의 내부 차수를 계산합니다.

3) 대기열 만들기: in차수가 0인 노드를 대기열에 넣습니다.

4) 차수가 0인 노드에 따라 탐색 시작: 대기열에서 차수가 0인 노드를 꺼내고 이 노드를 정렬 결과에 추가하고 이 노드의 모든 인접한 노드의 차수를 줄입니다. 1.

5) 대기열이 빌 때까지 위 단계를 반복합니다.

코드 구현

다음은 C#을 사용하여 위상 정렬 알고리즘을 구현하기 위한 샘플 코드입니다.

using System;
using System.Collections.Generic;

public class Graph
{
    private int V; //图中节点的个数
    private List<int>[] adj; //图的邻接表

    public Graph(int v)
    {
        V = v;
        adj = new List<int>[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new List<int>();
    }

    public void AddEdge(int v, int w)
    {
        adj[v].Add(w); //将节点w加入节点v的邻接表中
    }

    public void TopologicalSort()
    {
        int[] indegree = new int[V]; //用于统计每个节点的入度
        for (int i = 0; i < V; ++i)
            indegree[i] = 0;

        //统计每个节点的入度
        for (int v = 0; v < V; ++v)
        {
            List<int> adjList = adj[v];
            foreach (int w in adjList)
                indegree[w]++;
        }

        Queue<int> queue = new Queue<int>(); //存放入度为0的节点
        for (int i = 0; i < V; ++i)
        {
            if (indegree[i] == 0)
                queue.Enqueue(i);
        }

        List<int> result = new List<int>(); //存放排序结果
        int count = 0; //已经排序的节点个数

        while (queue.Count > 0)
        {
            int v = queue.Dequeue();
            result.Add(v);
            count++;

            //将与节点v相邻的节点的入度减1
            List<int> adjList = adj[v];
            foreach (int w in adjList)
            {
                indegree[w]--;
                if (indegree[w] == 0)
                    queue.Enqueue(w);
            }
        }

        //判断是否有环
        if (count != V)
        {
            Console.WriteLine("图中存在环！");
            return;
        }

        //输出排序结果
        Console.WriteLine("拓扑排序结果：");
        foreach (int v in result)
        {
            Console.Write(v + " ");
        }
    }
}

public class Program
{
    public static void Main(string[] args)
    {
        Graph g = new Graph(6);
        g.AddEdge(5, 2);
        g.AddEdge(5, 0);
        g.AddEdge(4, 0);
        g.AddEdge(4, 1);
        g.AddEdge(2, 3);
        g.AddEdge(3, 1);

        g.TopologicalSort();
    }
}

로그인 후 복사

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.