无向图例子,创建无向图的代码

　　00-1010基本概念图的定义无向图的定义API实现无向图数组邻接表数组遍历深度优先搜索宽度优先搜索无向图的后记

目录

　　00-1010图是由点集V={vi}和VV中无序元素对的集合E={ek}组成的二元群，记为G=(V，E)。V中的元素vi称为顶点，E中的元素ek称为边。

　　对于V中的两点u，V，如果边(u，V)属于E，则两点u，V相邻，u，V称为边(u，V)的端点。

　　我们可以用m(G)=E来表示图G的边数，用n(G)=V来表示图G的顶点数。

　　00-1010对于E中的任意边(vi，vj)，如果边(vi，vj)的端点是无序的，则它是一条无向边。此时，图G称为无向图。无向图是最简单的图形模型。下图显示了同一个无向图。顶点用圆圈表示，边是顶点之间的连接线，没有箭头(图片来自《算法第四版》):

　　00-1010对于一个无向图，我们关心的是图的顶点数和边数，以及每个顶点的相邻顶点和边相加的操作，所以界面如下：

　　包com . zhiyiyo . graph；/* * *无向图*/公共接口图{/** *返回图中的顶点数*/int V()；/* * *返回图中的边数*/int E()；/* * *给图添加一条边* @ param v vertex v * @ param w vertex w */void addEdge(int v，int w)；/* * *返回所有相邻顶点* @param v顶点v * @返回所有相邻顶点*/iterable integer adj(int v)；}

基本概念

　　00-1010利用矩阵表示研究图的性质和应用往往是很方便的。各种图有各种矩阵表示，如权矩阵和邻接矩阵。这里，我们只关注邻接矩阵。它被定义为：

　　对于图G=(V，E)，V=n，构造一个矩阵A=(aij)nn，其中：

　　矩阵a称为图g的邻接矩阵.

　　根据定义，我们可以用一个二维布尔数组A来实现邻接矩阵。当A[i][j]=true时，表示顶点I和J相邻。

　　对于一个有n个顶点的图G，邻接矩阵消耗的空间是n2个布尔值，对于稀疏图会造成很大的浪费。当顶点数量较大时，所消耗的空间将是天文数字。同时，当图形比较特殊，有自环和平行边时，邻接矩阵的表示是无能为力的。103010中给出了这两种情况的示意图：

　　00-1010对于无向图，我们可以实现一个类边，其中只使用两个实例变量来存储两个顶点U和V，然后将所有的边保存在一个数组中。这种方式有一个很大的问题，就是当顶点V的所有相邻顶点都得到后，必须遍历整个数组，时间复杂度为O(E)。因为获取相邻顶点是非常常见的操作，所以这种表示也不是很好。

　　00-1010如果我们把顶点表示为一个取值范围为0 V 1的整数，那么我们可以用一个长度为V的数组的索引来表示每个顶点，然后把每个数组元素设置为一个链表，在其上挂载与索引所表示的顶点相邻的其他顶点。图1所示的无向图可以用下图所示的邻接表数组来表示：

　　用邻接表实现无向图的代码如下。由于邻接表数组中的每个链表将保存与顶点相邻的顶点，所以向图添加边需要向数组中的两个链表添加节点：

　　包com . zhiyiyo . graph；导入com . zhiyiyo . collection . stack . link stack；/* * *邻接表实现的无向图*/公共类链接图实现图{ private final int v；私有int E；私人的

　　LinkStack<Integer>[] adj; public LinkGraph(int V) { this.V = V; adj = (LinkStack<Integer>[]) new LinkStack[V]; for (int i = 0; i < V; i++) { adj[i] = new LinkStack<>(); } } @Override public int V() { return V; } @Override public int E() { return E; } @Override public void addEdge(int v, int w) { adj[v].push(w); adj[w].push(v); E++; } @Override public Iterable<Integer> adj(int v) { return adj[v]; }}这里用到的栈代码如下所示，栈的实现不是这篇博客的重点，所以这里不做过多解释：

package com.zhiyiyo.collection.stack;import java.util.EmptyStackException;import java.util.Iterator;/** * 使用链表实现的堆栈 */public class LinkStack<T> { private int N; private Node first; public void push(T item) { first = new Node(item, first); N++; } public T pop() throws EmptyStackException { if (N == 0) { throw new EmptyStackException(); } T item = first.item; first = first.next; N--; return item; } public int size() { return N; } public boolean isEmpty() { return N == 0; } public Iterator<T> iterator() { return new ReverseIterator(); } private class Node { T item; Node next; public Node() { } public Node(T item, Node next) { this.item = item; this.next = next; } } private class ReverseIterator implements Iterator<T> { private Node node = first; @Override public boolean hasNext() { return node != null; } @Override public T next() { T item = node.item; node = node.next; return item; } @Override public void remove() { } }}

无向图的遍历

　　在介绍这两种遍历方式之前，先给出解决上述问题需要实现的 API：

package com.zhiyiyo.graph;public interface Search { /** * 起点 s 和 顶点 v 之间是否连通 * @param v 顶点 v * @return 是否连通 */ boolean connected(int v); /** * 返回与顶点 s 相连通的顶点个数（包括 s） */ int count(); /** * 是否存在从起点 s 到顶点 v 的路径 * @param v 顶点 v * @return 是否存在路径 */ boolean hasPathTo(int v); /** * 从起点 s 到顶点 v 的路径，不存在则返回 null * @param v 顶点 v * @return 路径 */ Iterable<Integer> pathTo(int v);}

深度优先搜索

　　为了记录每个顶点到顶点 0 的路径，我们还需要一个数组int[] edgeTo。每当我们访问到顶点u并将其一个相邻顶点i压入栈中时，就将edgeTo[i]设置为u，说明要想从顶点i到达顶点 0，需要先回退顶点u，接着再从顶点edgeTo[u]处获取下一步要回退的顶点直至找到顶点 0。

package com.zhiyiyo.graph;import com.zhiyiyo.collection.stack.LinkStack;import com.zhiyiyo.collection.stack.Stack;public class DepthFirstSearch implements Search { private boolean[] marked; private int[] edgeTo; private Graph graph; private int s; private int N; public DepthFirstSearch(Graph graph, int s) { this.graph = graph; this.s = s; marked = new boolean[graph.V()]; edgeTo = new int[graph.V()]; dfs(); } /** * 递归实现的深度优先搜索 * * @param v 顶点 v */ private void dfs(int v) { marked[v] = true; N++; for (int i : graph.adj(v)) { if (!marked[i]) { edgeTo[i] = v; dfs(i); } } } /** * 堆栈实现的深度优先搜索 */ private void dfs() { Stack<Integer> vertexes = new LinkStack<>(); vertexes.push(s); marked[s] = true; while (!vertexes.isEmpty()) { Integer v = vertexes.pop(); N++; // 将所有相邻顶点加到堆栈中 for (Integer i : graph.adj(v)) { if (!marked[i]) { edgeTo[i] = v; marked[i] = true; vertexes.push(i); } } } } @Override public boolean connected(int v) { return marked[v]; } @Override public int count() { return N; } @Override public boolean hasPathTo(int v) { return connected(v); } @Override public Iterable<Integer> pathTo(int v) { if (!hasPathTo(v)) return null; Stack<Integer> path = new LinkStack<>(); int vertex = v; while (vertex != s) { path.push(vertex); vertex = edgeTo[vertex]; } path.push(s); return path; }}

广度优先搜索

package com.zhiyiyo.graph;import com.zhiyiyo.collection.queue.LinkQueue;public class BreadthFirstSearch implements Search { private boolean[] marked; private int[] edgeTo; private Graph graph; private int s; private int N; public BreadthFirstSearch(Graph graph, int s) { this.graph = graph; this.s = s; marked = new boolean[graph.V()]; edgeTo = new int[graph.V()]; bfs(); } private void bfs() { LinkQueue<Integer> queue = new LinkQueue<>(); marked[s] = true; queue.enqueue(s); while (!queue.isEmpty()) { int v = queue.dequeue(); N++; for (Integer i : graph.adj(v)) { if (!marked[i]) { edgeTo[i] = v; marked[i] = true; queue.enqueue(i); } } } }}

package com.zhiyiyo.collection.queue;import java.util.EmptyStackException;public class LinkQueue<T> { private int N; private Node first; private Node last; public void enqueue(T item) { Node node = new Node(item, null); if (++N == 1) { first = node; } else { last.next = node; } last = node; } public T dequeue() throws EmptyStackException { if (N == 0) { throw new EmptyStackException(); } T item = first.item; first = first.next; if (--N == 0) { last = null; } return item; } public int size() { return N; } public boolean isEmpty() { return N == 0; } private class Node { T item; Node next; public Node() { } public Node(T item, Node next) { this.item = item; this.next = next; } }}

后记

　　到此这篇关于Java实现无向图的示例详解的文章就介绍到这了,更多相关Java无向图内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。