Explication détaillée des exemples d'algorithmes de profondeur d'abord et de largeur d'abord

Tout d'abord, permettez-moi de vous présenter la deuxième partie du site Algorithmes, qui est le cours en ligne du livre Algorithmes.

De plus, le cours sur les algorithmes graphiques sur Coursera est également très bon.

Plusieurs méthodes de représentation des graphiques :

De cette façon (structure de données) représente le diagramme, qui comprend les deux exigences suivantes : (1) L'espace doit être approprié (2) La mise en œuvre de la méthode d'instance doit être rapide

Ensuite, vous avez le choix entre trois options :

(1) L'ensemble des bords est le suivant :

Simple mais ne satisfait pas aux deux conditions - pour implémenter la liste de contiguïté adj(), toutes les arêtes du graphe doivent être traversées.

(2) Matrice de contiguïté :

Utiliser un V par V La preuve booléenne n’est pas satisfaite dans l’espace.

(3) Liste de contiguïté :

Utiliser un sommet comme index Une liste de tableaux, dont chaque élément est une liste de sommets adjacents au sommet.

Étant donné que la méthode ci-dessus a une plus grande flexibilité, si une liste de contiguïté est utilisée pour la représenter, la structure de données suivante peut être définie pour représenter un objet Graph.

public class Graph
{private readonly int verticals;//顶点个数private int edges;//边的个数private List<int>[] adjacency;//顶点联接列表public Graph(int vertical)
    {this.verticals = vertical;this.edges = 0;
        adjacency=new List<int>[vertical];for (int v = 0; v < vertical; v++)
        {
            adjacency[v]=new List<int>();
        }
    }public int GetVerticals ()
    {return verticals;
    }public int GetEdges()
    {return edges;
    }public void AddEdge(int verticalStart, int verticalEnd)
    {
        adjacency[verticalStart].Add(verticalEnd);
        adjacency[verticalEnd].Add(verticalStart);
        edges++;
    }public List<int> GetAdjacency(int vetical)
    {return adjacency[vetical];
    }
}

Algorithme de profondeur d'abord

Avant de parler de l'algorithme de profondeur d'abord, nous pouvons d'abord regarder à la question d'exploration du labyrinthe. Voici la correspondance entre un labyrinthe et un graphe :

Chaque point d'intersection dans le labyrinthe représente un sommet dans le graphe, et chaque canal correspond à une arête.

La méthode d'exploration sur corde de Trémaux peut être utilisée pour explorer le labyrinthe. C'est-à-dire :

• Mettez une corde derrière vous

• Mettez-la partout où vous visite Une corde marque les points d'intersection et les passages visités

• Lorsque vous rencontrez un lieu qui a été visité, remontez le long de la corde jusqu'à un endroit qui n'a pas été visité avant :

L'icône est la suivante :

ci-dessous C'est une petite animation d'exploration de labyrinthe :

L'algorithme de recherche en profondeur d'abord simule l'exploration de labyrinthe. Dans les algorithmes de traitement de graphes réels, nous séparons généralement la représentation du graphe et la logique de traitement du graphe. Le modèle de conception global de l'algorithme est donc le suivant :

• Créer un objet Graph

• Créer un graphique L'objet est transmis à l'objet de traitement de l'algorithme graphique, tel qu'un objet Paths

• , puis les résultats traités sont interrogés pour obtenir des informations

Nous pouvons voir que lors de l'appel récursif de la méthode dfs, maintient un tableau de balises Marked[] pour déterminer si le nœud a été visité avant d'appeler .

Description de l'algorithme de profondeur d'abord : Lors de la visite d'un sommet

1. Marquez-le comme visité ;

2. Visitez récursivement tous ses sommets voisins non marqués.

public class DepthFirstSearch
{private bool[] marked;//记录顶点是否被标记private int count;//记录查找次数private DepthFirstSearch(Graph g, int v)
    {
        marked = new bool[g.GetVerticals()];
        dfs(g, v);
    }private void dfs(Graph g, int v)
    {
        marked[v] = true;
        count++;foreach (int vertical in g.GetAdjacency(v))
        {if (!marked[vertical])
                dfs(g,vertical);
        }
    }public bool IsMarked(int vertical)
    {return marked[vertical];
    }public int Count()
    {return count;
    }
}

试验一个算法最简单的办法是找一个简单的例子来实现。

算法应用：

连通性。给定一幅图，回答“两个给定顶点是否连通？” 或者 “图中有多少个连通子图？”

寻找路径。给定一幅图和一个起点，回答“从s到给定目的顶点v是否存在一条路径？如果有，找出这条路径。”

检测环。给定的图是无环图吗？

双色问题。能够用两种颜色将图的所有顶点着色，使得任意一条边连个顶点的颜色都不相同？这个问题等价于：这是一个二分图吗？

 

深度优先路径查询

有了这个基础，我们可以实现基于深度优先的路径查询，要实现路径查询，我们必须定义一个变量来记录所探索到的路径。

所以在上面的基础上定义一个edgesTo变量来后向记录所有到s的顶点的记录，和仅记录从当前节点到起始节点不同，我们记录图中的每一个节点到开始节点的路径。为了完成这一日任务，通过设置edgesTo[w]=v，我们记录从v到w的边，换句话说，v-w是做后一条从s到达w的边。 edgesTo[]其实是一个指向其父节点的树。

注意代码只是在前面算法的基础上维护了一个edgTo数组，并用栈Stack保存路径。

public class DepthFirstPaths
{private bool[] marked;//记录是否被dfs访问过
    private int[] edgesTo;//记录最后一个到当前节点的顶点private int s;//搜索的起始点public DepthFirstPaths(Graph g, int s)
    {
        marked = new bool[g.GetVerticals()];
        edgesTo = new int[g.GetVerticals()];this.s = s;
        dfs(g, s);
    }private void dfs(Graph g, int v)
    {
        marked[v] = true;foreach (int w in g.GetAdjacency(v))
        {if (!marked[w])
            {                edgesTo[w] = v;dfs(g,w);
            }
        }
    }public bool HasPathTo(int v)
    {return marked[v];
    }public Stack<int> PathTo(int v){if (!HasPathTo(v)) return null;
        Stack<int> path = new Stack<int>();for (int x = v; x!=s; x=edgesTo[x])
        {
            path.Push(x);
        }
        path.Push(s);return path;
    }
}

 

上图中是黑色线条表示 深度优先搜索中，所有定点到原点0的路径， 他是通过edgeTo[]这个变量记录的，可以从右边可以看出，

他其实是一颗树，树根即是原点，每个子节点到树根的路径即是从原点到该子节点的路径。

下图是深度优先搜索算法的一个简单例子的追踪。

 

 

 

连通分量

API如下：

CC的实现使用了marked[ ]数组来寻找一个顶点作为每个连通分量中深度优先搜索的起点。递归的深搜第一次调用的参数是顶点0，会标记所有与0连通的顶点。然后构造函数中的for循环会查找每个没有被标记的顶点并递归调用dfs来标记和它相邻的所有顶点。另外，它还使用了一个以顶点作为索引的数组id[ ],将同一个连通分量中的顶点和连通分量的标识符关联起来。这个数组使得connected( )方法的实现变得十分简单。

public class CC {private boolean[] marked;private int[] id;private int count;public CC(Graph g){
        marked = new boolean[g.getVertexCount()];
        id = new int[g.getVertexCount()];for(int s = 0; s < g.getVertexCount(); s++){if(!marked[s]){
                dfs(g,s);
                count++;
            }
        }
    }private void dfs(Graph g, int v) {
        marked[v] = true;
        id[v] = count;for(int w: g.adj(v))if(!marked[w])
                dfs(g,w);
    }/** v和w连通吗*/public boolean connected(int v, int w)    { return id[v] == id[w]; }/** v所在的连通分量的标识符*/public int id(int v)    { return id[v]; }/** 连通分量数*/public int count()        {return count;}

 

检测环

/**
 * 给定的图是无环图吗
 * 检测自环:假设没有自环，没有平行边 */public class Cycle {private boolean[] marked;private boolean hasCycle;public Cycle(Graph g){
        marked = new boolean[g.getVertexCount()];for(int i = 0;i<g.getVertexCount();i++)if(!marked[i])    dfs(g, i, i);
    }private void dfs(Graph g, int v, int u) {
        marked[v] = true;for(int w: g.adj(v))if(!marked[w])    dfs(g, w, v); // 若w没被标记过，那么从w继续递归深搜，把w的父节点作为第二参数else if(w != u) hasCycle = true; // 若w被标记过，那么若无环，w必然和父节点相同，否则就是有环    }/** 是否含有环*/public boolean hasCycle(){return hasCycle;}

 

双色问题

/**
 * 双色问题：能够用两种颜色将图的所有顶点着色，使得任意一条边上的两个端点的颜色都不同吗？
 * 等价于：判断是否是二分图的问题 */public class TwoColor {private boolean[] marked;private boolean[] color;private boolean isColorable;public TwoColor(Graph g){
        isColorable = true;
        marked = new boolean[g.getVertexCount()];
        color = new boolean[g.getVertexCount()];for(int i = 0; i<g.getVertexCount(); i++)//遍历所有顶点if(!marked[i])    dfs(g, i);//没有mark就进行深搜    }private void dfs(Graph g, int v) {
        marked[v] = true;        // 标记for(int w: g.adj(v))    // 对邻接表进行遍历if(!marked[w]){        // 如果没有被标记color[w] = !color[v];    // 当前w节点颜色置为和父节点不同的颜色dfs(g, w);                // 对当前节点继续深搜}else if(color[w] == color[v]){    // 如果已经被标记，看是否颜色和父节点相同isColorable = false;         // 若相同则不是二分图            }
    }/** 是否是二分图*/public boolean isBipartite(){return isColorable;}

 

 

广度优先算法

通常我们更关注的是一类单源最短路径的问题，那就是给定一个图和一个源S，是否存在一条从s到给定定点v的路径，如果存在，找出最短的那条(这里最短定义为边的条数最小)

深度优先算法是将未被访问的节点放到一个堆中(stack)，虽然在上面的代码中没有明确在代码中写stack，但是 递归间接的利用递归堆实现了这一原理。

和深度优先算法不同， 广度优先是将所有未被访问的节点放到了队列中。其主要原理是：

先将起点加入队列，然后重复一下步骤直到队列为空：

1.取队列中的下一个顶点V并标记它

2.将与v相邻的所有未被标记过的顶点加入队列

广度优先是以距离递增的方式来搜索路径的。

class BreadthFirstSearch
{private bool[] marked;private int[] edgeTo;private int sourceVetical;//Source verticalpublic BreadthFirstSearch(Graph g, int s)
    {
        marked=new bool[g.GetVerticals()];
        edgeTo=new int[g.GetVerticals()];this.sourceVetical = s;
        bfs(g, s);
    }private void bfs(Graph g, int s)
    {
        Queue<int> queue = new Queue<int>();
        marked[s] = true;
        queue.Enqueue(s);while (queue.Count()!=0)
        {int v = queue.Dequeue();foreach (int w in g.GetAdjacency(v))
            {if (!marked[w])
                {
                    edgeTo[w] = v;
                    marked[w] = true;
                    queue.Enqueue(w);
                }
            }
        }
    }public bool HasPathTo(int v)
    {return marked[v];
    }public Stack<int> PathTo(int v)
    {if (!HasPathTo(v)) return null;

        Stack<int> path = new Stack<int>();for (int x = v; x!=sourceVetical; x=edgeTo[x])
        {
            path.Push(x);
        }
        path.Push(sourceVetical);return path;
    }

}

算法应用：最短路径问题

 

总结：

深度优先搜索和广度优先搜索都是将起点存入数据结构中，然后重复一下步骤直到数据结构被清空：

1.取其中的下一个顶点并标记它

2.将v的所有相邻而未被标记的顶点加入数据结构

这两个算法 的不同之处仅在于从数据结构中获取下一个顶点的规则（广度优先来说是最早加入的顶点，对于深度优先搜索来说是最晚加入的顶点）。

 

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!