Shulou(Shulou.com)06/01 Report--

This article mainly introduces the Java so the realization of undirected graph related knowledge, the content is detailed and easy to understand, the operation is simple and fast, has a certain reference value, I believe that everyone after reading this Java undirected graph article will have a harvest, let's take a look at it.

Definition of basic concept map

A graph is a binary consisting of a set of vertices V = {vi} and a set E = {ek} of unordered pairs of elements in VV, denoted by G = (V ek E), the element vi in V is called vertex, and the element ek in E is called edge.

For the two points of V, ujournal v, if the edge belongs to E, then the two points are said to be adjacent to each other, and the ugraine v is called the end point of the edge (uperior v).

We can use m (G) = | E | to indicate the number of edges in graph G and n (G) = | V | to indicate the number of vertices in graph G.

The definition of undirected graph

For any edge (vi,vj) in E, if the end of the edge (vi,vj) is disordered, then it is an undirected edge, and the graph G is called an undirected graph. The undirected graph is the simplest graph model. The following image shows the same undirected graph, with vertices represented by circles and edges as lines between vertices without arrows (picture from the fourth edition of the algorithm):

API of undirected graph

For an undirected graph, we are concerned about the number of vertices, edges, adjacent vertices and edges of each vertex, so the interface is as follows:

Package com.zhiyiyo.graph;/** * undirected graph * / public interface Graph {/ * returns the number of vertices in the graph * / int V (); / * * returns the number of edges in the graph * / int E () / * add an edge to the graph * @ param v vertex v * @ param w vertex w * / void addEdge (int v, int w); / * return all adjacent vertices * @ param v vertex v * @ return all adjacent vertices * / Iterable adj (int v);} implementation of undirected graph adjacency matrix

It is often convenient to use matrix to represent graphs to study the properties and applications of graphs. For all kinds of graphs, there are various matrix representations, such as weight matrix and adjacency matrix, here we only focus on adjacency matrix. It is defined as:

For graph G = (VMague E), | V | = n, construct a matrix A = (aij) n × n, where:

Then the matrix An is called the adjacency matrix of graph G.

From the definition, we can use a two-dimensional Boolean array A to realize the adjacency matrix, and when A [I] [j] = true, it means that the vertices I and j are adjacent.

For a graph G with n vertices, the space consumed by the adjacency matrix is the size of n 2 Boolean values, which will cause a great waste for sparse graphs, and the space consumed will be astronomical when the number of vertices is very large. At the same time, when the graph is special, there are self-loops and parallel edges, the representation of the adjacency matrix is powerless. A graph of these two situations is given in the algorithm:

Array of edges

For undirected graphs, we can implement a class Edge, in which only two instance variables are used to store two vertices u and v, and then store all Edge in an array. There is a big problem with this, that is, when you get all the adjacent vertices of vertex v, you have to traverse the entire array, and the time complexity is O (| E |). So this representation is not very good.

Adjacency table array

If we represent a vertex as an integer with a range of 0 ∼ | V | − 1, then we can represent each vertex with an index of an array of length | V |, and then set each array element to a linked list with other vertices adjacent to the vertex represented by the index. The undirected graph shown in figure 1 can be represented by an array of adjacency tables shown in the following figure:

The code to implement an undirected graph using an adjacency list is as follows. Because each linked list in the adjacency table array saves vertices adjacent to vertices, adding edges to the graph requires adding nodes to the two linked lists in the array:

Package com.zhiyiyo.graph;import com.zhiyiyo.collection.stack.LinkStack;/** * undirected graph implemented using adjacency tables * / public class LinkGraph implements Graph {private final int V; private int E; private LinkStack [] adj; public LinkGraph (int V) {this.V = V; adj = (LinkStack []) 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 adj(int v) { return adj[v]; }} 这里用到的栈代码如下所示，栈的实现不是这篇博客的重点，所以这里不做过多解释： package com.zhiyiyo.collection.stack;import java.util.EmptyStackException;import java.util.Iterator;/** * 使用链表实现的堆栈 */public class LinkStack { 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 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 { 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() { } }}无向图的遍历 给定下面一幅图，现在要求找到每个顶点到顶点 0 的路径，该如何实现？或者简单点，给定顶点 0 和 4，要求判断从顶点 0 开始走，能否到达顶点 4，该如何实现？这就要用到两种图的遍历方式：深度优先搜索和广度优先搜索。

Before introducing these two traversal methods, we first give the API that needs to be implemented to solve the above problems:

Whether package com.zhiyiyo.graph;public interface Search {/ * whether the starting point s and vertex v are connected * @ param v vertex v * @ return is connected * / boolean connected (int v); / * returns the number of vertices connected to vertex s (including s) * / int count () / * whether there is a path from start s to vertex v * @ param v vertex v * @ return whether there is a path * / boolean hasPathTo (int v); / * if there is no path from start s to vertex v, return null * @ param v vertex v * @ return path * / Iterable pathTo (int v);} depth first search

The idea of depth-first search is similar to the preorder traversal of a tree. We start with vertex 0 and add its adjacent vertices 2, 1, 5 to the stack. Then pop up vertex 2 at the top of the stack and add its adjacent vertices 0, 1, 3, 4 to the stack, but when you write about this, you will find a problem: vertices 0 and 1 are already in the stack, and if you add them to the stack, then the stack will never become empty. So we also need to maintain an array boolean [] marked. When we add a vertex I to the stack, we set marked [I] to true, so the next time we want to add vertex I to the stack, we have to check whether a marked [I] is true, and if it is true, we don't have to add it any more. Repeat the pop-up of the top node of the stack and the stack operation of the neighboring nodes, until the stack is empty, we finish traversing all the vertices that vertex 0 can reach.

To record the path from each vertex to vertex 0, we also need an array of int [] edgeTo. Whenever we visit vertex u and push one of its adjacent vertices I into the stack, we set edgeTo [I] to u, which means that if we want to reach vertex 0 from vertex I, we need to return vertex u first, and then get the next vertex to fall back from vertex edgeTo [u] until vertex 0 is found.

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 ();} / * * Recursive depth-first search * * @ param v vertex v * / private void dfs (int v) {marked [v] = true; Numeric + For (int I: graph.adj (v)) {if (! marked [I]) {edgeTo [I] = v; dfs (I);} / * depth-first search for stack implementation * / private void dfs () {Stack vertexes = new LinkStack () Vertexes.push (s); marked [s] = true; while (! vertexes.isEmpty ()) {Integer v = vertexes.pop (); Integer + / / add all adjacent vertices to the stack 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 pathTo (int v) {if (! hasPathTo (v)) return null Stack path = new LinkStack (); int vertex = v; while (vertex! = s) {path.push (vertex); vertex = edgeTo [vertex];} path.push (s); return path;}} breadth first search

The idea of breadth-first search is similar to the sequence traversal of trees. Unlike depth-first search, starting from vertex 0, breadth-first search processes all vertices 2, 1, and 5 adjacent to vertex 0 before processing the adjacent vertices of vertex 2, 1, and 5. This search process is a process of expanding outward and going farther and farther in a circle, so it can be used to obtain the shortest path from vertex 0 to other nodes. A breadth-first search can be achieved as long as the heap in the depth-first search is replaced with a queue:

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 queue = new LinkQueue (); marked [s] = true; queue.enqueue (s); while (! queue.isEmpty ()) {int v = queue.dequeue (); Numbai + For (Integer I: graph.adj (v)) {if (! marked [I]) {edgeTo [I] = v; marked [I] = true; queue.enqueue (I);}

The implementation code of the queue is as follows:

Package com.zhiyiyo.collection.queue;import java.util.EmptyStackException;public class LinkQueue {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 This is the end of the article on "how Java realizes undirected graph". Thank you for reading! I believe that everyone has a certain understanding of the knowledge of "Java so achieve undirected graph". If you want to learn more knowledge, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.