1、算法用途:
是一种图像搜索演算法。用于遍历图中的节点,有些类似于树的深度优先遍历。这里唯一的问题是,与树不同,图形可能包含循环,因此我们可能会再次来到同一节点。
2、主要思想:
主要借助一个队列、一个布尔类型数组、邻接矩阵完成(判断一个点是否查看过,用于避免重复到达同一个点,造成死循环等),先将各点以及各点的关系存入邻接矩阵。
再从第一个点开始,将一个点存入队列,然后在邻接表中找到他的相邻点,存入队列,每次pop出队列头部并将其打印出来(文字有些抽象,实际过程很简单),整个过程有点像往水中投入石子水花散开。
(邻接表是表示了图中与每一个顶点相邻的边集的集合,这里的集合指的是无序集)
3、代码(java):
(以上图为例的代码)
1 import java.util.*2 3 //This class represents a directed graph using adjacency list
4 //representation 5 class Graph1 { 6 private static int V// No. of vertices 7 private LinkedList<Integer>awww.ynzzyx.com#Adjacency Lists 8 9 // Constructor10 Graph1(int v) {11 V = v12 adj = new LinkedList[v]13 for (int i = 0i <v++i)14 adj[i] = new LinkedList()15 }16 17 // Function to add an edge into the graph18 void addEdge(int v, int w) {19 adj[v].add(w)20 }21 22 // prints BFS traversal from a given source s23 public void BFS() {24 // Mark all the vertices as not visited(By default25 // set as false)26 boolean visited[] = new boolean[V]27 // Create a queue for BFS28 LinkedList<Integer>queue = new LinkedList<Integer>()29 30 for (int i = 0i <Vi++) {31 if (!visited[i]) {32 BFSUtil(i, visited, queue)33 }34 }35 }36 37 public void BFSUtil(int s, boolean visited[], LinkedList<Integer>queue) {38 // Mark the current node as visited and enqueue it39 visited[s] = true40 queue.add(s)41 42 while (queue.size() != 0) {43 // Dequeue a vertex from queue and print it44 s = queue.poll()45 System.out.print(s + " ")46 47 // Get all adjacent vertices of the dequeued vertex s48 // If a adjacent has not been visited, then mark it49 // visited and enqueue it50 Iterator<Integer>i = adj[s].listIterator()51 while (i.hasNext()) {52 int n = i.next()53 if (!visited[n]) {54 visited[n] = true55 queue.add(n)56 }57 }58 }59 }60 61 // Driver method to62 public static void main(String args[]) {63 Graph1 g = new Graph1(4)64 65 g.addEdge(0, 1)66 g.addEdge(0, 2)67 g.addEdge(1, 2)68 g.addEdge(2, 0)69 g.addEdge(2, 3)70 g.addEdge(3, 3)71 72 System.out.println("Following is Breadth First Traversal " + "(starting from vertex 2)")73 g.BFS()74 }75 }
4、复杂度分析:
算法借助了一个邻接表和队列,故它的空问复杂度为O(V)。 遍历图的过程实质上是对每个顶点查找其邻接点的过程,其耗费的时间取决于所采用结构。 邻接表表示时,查找所有顶点的邻接点所需时间为O(E),访问顶点的邻接点所花时间为O(V),此时,总的时间复杂度为O(V+E)。
1.首先,你要确定你要开发什么样的软件,是PC端的,还是移动端的。2.如果是PC端的,那么你要确定是Windows的,还是Mac OS的,或者是Linux的。前两者可能性最大。windows 的去学C#和Qt还有MFC,你现在掌握的C和C++肯定是不够的。Mac OS 去学Objective-C和Cocoa库/框架。
3.如果是移动端,你最容易的还是区别一下Android和IOS的。Android去学Java和Android对应的知识,比如去看第一行代码,对Android 有一个初步认识。IOS的话刚开始对C要求不高,你就先去学Objective-C。
4.可以查词的话你还的去学学算法,例如倒排索引,bfs,dfs等,刚开始可以直接上框架(可以了解一下solr和lucene),然后还得有词库。