本文共 789 字,大约阅读时间需要 2 分钟。
用于深度和广度搜索算法一般就是用来做图的遍历,或者说图是搜索算法的最常用数据结构,因此需要先储备一些图的概念。
图是由一个非空的顶点集合和一个边的集合组成。 G=( V, E ) 1.无向图:任意两顶点构成的偶对(vi , vj )是无序的。一个顶点的连接边数叫作结点的度。一个完全无向图有n(n-1)/2 条边。 2.有向图:顶点之间的关系(边)有方向,因此把度也分成了出度和入度。表示微博中的用户关注度可用 3.带权图:边加了权重的图。表示网络中,QQ好友亲密度度可用 4.完全图:(1)若 n 个顶点的无向图有 n(n-1)/2 条边, 称为无向完全图 (2)若 n 个顶点的有向图有n(n-1) 条边, 称为有向完全图 5.邻接矩阵:优点是容易实现图的操作,如:求某顶点的度、判断顶点之间是否有边(弧)、找顶点的邻接点等等。缺点是n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。 6.邻接表:对每个顶点vi 建立一个单链表,把与vi有关联的边的信息(度)链接起来。优点是空间效率高且容易寻找顶点的邻接点; 以下是无向图及其邻接表: 先给出用邻接表实现的无向图代码:public class Graph{ private int v; private LinkedListadj[]; public Graph(int v){ this.v=v; adj = new LinkedList[v]; for(int i=0;i (); } } public void addEdge(int s, int t){ adj[s].add(t); adj[t].add(s); }}
转载地址:http://jfrsi.baihongyu.com/