图算法, 无向图

/*若以二维数组存储图信息, 负责度比定为n^2, 采用链表存储*/

基础存储类型为Item(用来存储基本类型), 需继承Iterable用以顺序访问


public class Bag<Item> implements Iterable<Item> {

private Node<Item> first;

private int n;

private static class Node<Item> { //内部类

private Item first;

private Node<Item> next; //下一个节点

}

public Bag() {

first = null;

n = 0;

}

public int size() { return n; }

public void add (Item item) { //在队首添加

Node<Item> oldfirst = first;

first = new Node<Item>();

first.item = item;

first.next = oldfirst;

n++

}

public Iterator<Item> iterator() { return new ListIterator<Item>(first) ; } 重写迭代器

private class ListIterator<Item> implements Iterator<Item> {

private Node<Item> current;

public ListIterator(Node<Item> first) { current = first; } ;

public boolean hasNext() { return current != null; }

public void remove() { throw new UnsupportedOperationException(); }

public Item next() {

if(!hasnext()) throw new NoSuchElementException();

Item item = current.item;

current = current.next ;

return item;

}


以下图为例构建无向图


无向图


所构成链表

形成图代码

public class Grath {

private final int V;//节点数目, 实例化时赋值

private int E;//边数目, 为0;

private Bag<Integer>[] adj; //链表结构


public Grath(int V) {

this.V = V;

this.E = 0;

adj = (Bag<Integer>[]) new Bag[V];

for(int i =0; i < V; i++) {

adj[V]  = new Bag<Integer>();

}

private voidvalidateVertex(int v) { //节点是否有效

if(v<0|| v>V) { throw newIllegalArgumentException("vertex "+ v +" is not between 0 and "+ (V-1)); }

}

public addEdge(int v, int w) {

validateVertex(v);

validateVertex(w);

E++;

adj[v].add(w);

adj[w].add(v);//双向连接

}

public Iterable adj(int v) { //获取某一条链

validateVertex(v);

returnadj[v];

}


深度搜索

public class DepthFirstSearch { /*采用动态规划和递归的方法从一个指定节点所能访问的所有的节点, 若能访问则返回true*/

private  boolean[] marked;//用来标志节点是否访问过

private int count;//指定节点所在图的所有节点数目

public DepthFirstSearch(Grapth G, int s) {

marked = new boolean[G.V()];

bfs(G, s); //深度遍历

}

private void dfs(Grapth G, int v) {

marked[v] = true;

count++;

for(int w : G.adj(v))

if(!marked[w] ) dfs (G, w);

}

public boolean marked( int w ) { return marked[w]; }

public int count() { return count; }

}




最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 14,349评论 0 33
  • 一、基本数据类型 注释 单行注释:// 区域注释:/* */ 文档注释:/** */ 数值 对于byte类型而言...
    龙猫小爷阅读 9,703评论 0 16
  • Code Splitting 将代码拆分成多个bundle,时webpack提供的比较吸引人的功能。拆分之后的代码...
    yftx_阅读 1,885评论 0 0
  • 大学生活就在匆匆忙忙熙熙攘攘中度过了,这期间我做了很多家教,在学校图书馆和食堂勤工俭学,再加上明子的帮助,我很...
    李笑然阅读 1,521评论 0 1
  • 小时候,我对家的印象,就是有个小小的庭院,有爸爸妈妈的笑脸。在学校,如果被表扬了,第一反应,就是回家告诉妈妈,如果...
    小考拉俱乐部阅读 4,404评论 0 2