日日操夜夜添-日日操影院-日日草夜夜操-日日干干-精品一区二区三区波多野结衣-精品一区二区三区高清免费不卡

如何實(shí)現(xiàn)C#中的拓?fù)渑判蛩惴ǎ枰唧w代碼示例

拓?fù)渑判蚴且环N常見(jiàn)的圖算法，用于解決有向圖中節(jié)點(diǎn)之間的依賴關(guān)系。在軟件開(kāi)發(fā)中，拓?fù)渑判虺Ｓ糜诮鉀Q任務(wù)調(diào)度、編譯順序等問(wèn)題。本文將介紹如何在C#中實(shí)現(xiàn)拓?fù)渑判蛩惴ǎ⑻峁┚唧w的代碼示例。

算法原理

拓?fù)渑判蛩惴ㄍㄟ^(guò)建立有向圖的鄰接表表示，然后利用深度優(yōu)先搜索（DFS）或廣度優(yōu)先搜索（BFS）來(lái)遍歷圖中的節(jié)點(diǎn)，并按照一定的順序輸出。

具體步驟如下：

1) 構(gòu)建有向圖的鄰接表：將有向圖中的每個(gè)節(jié)點(diǎn)表示為一個(gè)結(jié)構(gòu)體，并將節(jié)點(diǎn)的依賴關(guān)系表示為有向邊。

2) 統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的入度：遍歷鄰接表，統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的入度。

3) 創(chuàng)建一個(gè)隊(duì)列：將入度為0的節(jié)點(diǎn)入隊(duì)列。

4) 按照入度為0的節(jié)點(diǎn)開(kāi)始遍歷：從隊(duì)列中取出一個(gè)入度為0的節(jié)點(diǎn)，將該節(jié)點(diǎn)加入排序結(jié)果中，并將該節(jié)點(diǎn)的所有相鄰節(jié)點(diǎn)的入度減少1。

5) 重復(fù)以上步驟，直到隊(duì)列為空。

代碼實(shí)現(xiàn)

以下是使用C#實(shí)現(xiàn)拓?fù)渑判蛩惴ǖ氖纠a：

using System;
using System.Collections.Generic;

public class Graph
{
    private int V; //圖中節(jié)點(diǎn)的個(gè)數(shù)
    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); //將節(jié)點(diǎn)w加入節(jié)點(diǎn)v的鄰接表中
    }

    public void TopologicalSort()
    {
        int[] indegree = new int[V]; //用于統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的入度
        for (int i = 0; i < V; ++i)
            indegree[i] = 0;

        //統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的入度
        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的節(jié)點(diǎn)
        for (int i = 0; i < V; ++i)
        {
            if (indegree[i] == 0)
                queue.Enqueue(i);
        }

        List<int> result = new List<int>(); //存放排序結(jié)果
        int count = 0; //已經(jīng)排序的節(jié)點(diǎn)個(gè)數(shù)

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

            //將與節(jié)點(diǎn)v相鄰的節(jié)點(diǎn)的入度減1
            List<int> adjList = adj[v];
            foreach (int w in adjList)
            {
                indegree[w]--;
                if (indegree[w] == 0)
                    queue.Enqueue(w);
            }
        }

        //判斷是否有環(huán)
        if (count != V)
        {
            Console.WriteLine("圖中存在環(huán)！");
            return;
        }

        //輸出排序結(jié)果
        Console.WriteLine("拓?fù)渑判蚪Y(jié)果：");
        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();
    }
}

登錄后復(fù)制

運(yùn)行以上代碼，將輸出以下結(jié)果：

拓?fù)渑判蚪Y(jié)果：
5 4 2 3 1 0

登錄后復(fù)制

以上是使用C#實(shí)現(xiàn)的拓?fù)渑判蛩惴ǖ木唧w代碼示例。通過(guò)構(gòu)建圖的鄰接表、統(tǒng)計(jì)入度、使用隊(duì)列進(jìn)行遍歷等步驟，可以實(shí)現(xiàn)對(duì)有向圖進(jìn)行拓?fù)渑判颉?/p>

以上就是如何實(shí)現(xiàn)C#中的拓?fù)渑判蛩惴ǖ脑敿?xì)內(nèi)容，更多請(qǐng)關(guān)注www.xfxf.net其它相關(guān)文章！