Java图教程–如何实现图数据结构_图结构编程

图数据结构主要表示连接各个点的网络。这些点称为顶点，连接这些顶点的链接称为“边”。因此，图g被定义为一组顶点V和连接这些顶点的边E。

图主要用于表示各种网络，例如计算机网络，社交网络等。它们还可以用于表示软件或体系结构中的各种依赖关系。这些依赖图对于分析软件以及有时对其进行调试非常有用。

 

Java图形数据结构

下面给出的图具有五个顶点{A，B，C，D，E}，其边由{{AB}，{AC}，{AD}，{BD}，{CE}，{ED}}给出。由于边缘没有显示任何方向，因此此图称为“无向图”。

无向图

除了上面显示的无向图以外，Java中还有几种图的变体。

让我们详细讨论这些变体。

图的不同变体

以下是该图的一些变体。

＃1）有向图

有向图或有向图是其中边缘具有特定方向的图数据结构。它们源自一个顶点，最终达到另一个顶点。

下图显示了有向图的示例。

有向图

在上图中，从顶点A到顶点B有一条边。但是请注意，除非存在从B到A的边，否则A到B就像无向图中的B到A一样。

如果有至少一个路径的第一个和最后一个顶点相同，则有向图是循环的。在上图中，路径A-> B-> C-> D-> E-> A形成有向环或循环图。

相反，有向无环图是其中没有有向环，即没有形成环的路径的图。

＃2）加权图

在加权图中，权重与图的每个边关联。权重通常表示两个顶点之间的距离。下图显示了加权图。由于未显示方向，因此这是无向图。

加权图

注意，加权图可以是有向的或无向的。

如何创建图形？

Java没有提供图形数据结构的完整实现。但是，我们可以使用Java中的Collections以编程方式表示图形。我们还可以使用像矢量这样的动态数组来实现图。

通常，我们使用HashMap集合在Java中实现图形。HashMap元素采用键-值对的形式。我们可以在HashMap中表示图邻接表。

创建图的最常见方法是使用图的表示形式之一，例如邻接矩阵或邻接列表。接下来，我们将讨论这些表示形式，然后使用将使用ArrayList的邻接列表在Java中实现图形。

Java中的图形表示

图形表示是指将图形数据存储在计算机内存中的方法或技术。

我们有两个主要的图形表示，如下所示。

邻接矩阵

邻接矩阵是图的线性表示。该矩阵存储图的顶点和边缘的映射。在邻接矩阵中，图形的顶点表示行和列。这意味着，如果图具有N个顶点，则邻接矩阵的大小将为NxN。

如果V是图形的一组顶点，则邻接表中的交点M ij = 1表示在顶点i和j之间存在边。

为了更好地清楚地理解这个概念，让我们为无向图准备一个邻接矩阵。

从上图可以看出，对于顶点A，交点AB和AE设置为1，因为存在从A到B以及A到E的边。类似地，交点BA设置为1，因为这是无向的图，AB = BA。同样，我们将具有边的所有其他相交设置为1。

在有向图的情况下，只有在从Vi到Vj有明确的边沿的情况下，交集M ij才会设置为1。

如下图所示。

从上图中可以看到，从A到B有一条边。因此，交集AB设置为1，而交集BA设置为0。这是因为没有从B指向A的边。

考虑顶点E和D。我们看到从E到D以及从D到E都有边。因此，我们在邻接矩阵中将这两个交点都设置为1。

现在我们继续加权图。正如我们对加权图所知，每个边缘都关联有一个整数，也称为权重。我们在邻接矩阵中为存在的边缘表示此权重。只要从一个顶点到另一个顶点之间有一条边而不是“ 1”，就指定该权重。

此表示如下所示。

邻接表

除了将图表示为本质上是连续的邻接矩阵之外，我们还可以使用链接表示。这种链接表示形式称为邻接表。邻接列表不过是一个链表，列表中的每个节点都代表一个顶点。

从第一个顶点到第二个顶点的指针表示两个顶点之间存在边。为图中的每个顶点维护此邻接表。

当我们遍历了特定节点的所有相邻节点时，我们将NULL存储在邻接表的最后一个节点的下一个指针字段中。

现在，我们将使用上面用来表示邻接矩阵的图来演示邻接表。

上图显示了无向图的邻接表。我们看到每个顶点或节点都有其邻接表。

对于无向图，邻接表的总长度通常是边数的两倍。在上图中，边的总数为6，所有邻接表的长度的总和为12。

现在，让我们为有向图准备一个邻接表。

从上图可以看出，在有向图中，该图的邻接表的总长度等于该图中的边数。在上图中，有9条边，该图的邻接表长度之和= 9。

现在让我们考虑以下加权有向图。请注意，加权图的每个边缘都具有与之关联的权重。因此，当我们用邻接表表示该图时，我们必须向每个列表节点添加一个新字段，以表示边缘的权重。

加权图的邻接表如下所示。

上图显示了加权图及其邻接表。注意，在邻接表中有一个新的空格，表示每个节点的权重。

Java中的图实现

以下程序显示了Java图形的实现。在这里，我们使用了邻接表来表示图。

package Graph;
 
import java.util.*;
 
//class to store edges of the weighted graph
class Edge {
	int src, dest, weight;
 
	Edge(int src, int dest, int weight) {
		this.src = src;
		this.dest = dest;
		this.weight = weight;
	}
}
 
//Graph class
class Graph {
	// node of adjacency list
	static class Node {
		int value, weight;
 
		Node(int value, int weight) {
			this.value = value;
			this.weight = weight;
		}
	};
 
//define adjacency list
 
	List<List<Node>> adj_list = new ArrayList<>();
 
	// Graph Constructor
	public Graph(List<Edge> edges) {
		// adjacency list memory allocation
		for (int i = 0; i < edges.size(); i++)
			adj_list.add(i, new ArrayList<>());
 
		// add edges to the graph
		for (Edge e : edges) {
			// allocate new node in adjacency List from src to dest
			adj_list.get(e.src).add(new Node(e.dest, e.weight));
		}
	}
 
//print adjacency list for the graph
	public static void printGraph(Graph graph) {
		int src_vertex = 0;
		int list_size = graph.adj_list.size();
 
		System.out.println("The contents of the graph:");
		while (src_vertex < list_size) {
			// traverse through the adjacency list and print the edges
			for (Node edge : graph.adj_list.get(src_vertex)) {
				System.out.print("Vertex:" + src_vertex + " ==> " + edge.value + " (" + edge.weight + ")\t");
			}
 
			System.out.println();
			src_vertex++;
		}
	}
}
 
class Main {
	public static void main(String[] args) {
		// define edges of the graph
		List<Edge> edges = Arrays.asList(new Edge(0, 1, 2), new Edge(0, 2, 4), new Edge(1, 2, 4), new Edge(2, 0, 5),
				new Edge(2, 1, 4), new Edge(3, 2, 3), new Edge(4, 5, 1), new Edge(5, 4, 3));
 
		// call graph class Constructor to construct a graph
		Graph graph = new Graph(edges);
 
		// print the graph as an adjacency list
		Graph.printGraph(graph);
	}
}

输出：

图遍历Java

为了执行任何有意义的操作（例如搜索是否存在任何数据），我们需要遍历图，以使图的每个顶点和边缘至少被访问一次。这是通过使用图形算法完成的，图形算法不过是一组帮助我们遍历图形的指令。

支持两种算法来遍历Java中的图形。

1. 深度优先遍历
2. 广度优先遍历

深度优先遍历

深度优先搜索（DFS）是一种用于遍历树或图形的技术。DFS技术从根节点开始，然后通过更深入地遍历图来遍历该根节点的相邻节点。在DFS技术中，节点沿深度方向遍历，直到没有更多的子级可以探索为止。

一旦我们到达叶节点（没有更多的子节点），DFS就会回溯并从其他节点开始，并以类似的方式进行遍历。DFS技术使用堆栈数据结构来存储正在遍历的节点。

以下是DFS技术的算法。

算法

步骤1：从根节点开始，并将其插入堆栈

步骤2：从堆栈中弹出项目，然后插入“已访问”列表

步骤3：对于标记为“已访问”（或已访问列表）的节点，将该节点的尚未标记为已访问的相邻节点添加到堆栈中。

步骤4：重复步骤2和3，直到堆栈为空。

DFS技术的插图

现在，我们将使用适当的图形示例来说明DFS技术。

下面给出的是一个示例图。我们维护堆栈以存储探索的节点，并维护一个列表以存储访问的节点。

我们将以A开头，将其标记为已访问，然后将其添加到已访问列表。然后，我们将考虑A的所有相邻节点，并将这些节点压入堆栈，如下所示。

接下来，我们从堆栈中弹出一个节点，即B并将其标记为已访问。然后，将其添加到“已访问”列表中。如下所示。

现在我们考虑B的相邻节点，即A和C。已经访问了其中的A。因此，我们将其忽略。接下来，我们从堆栈中弹出C。将C标记为已访问。C的相邻节点，即E被添加到堆栈中。

接下来，我们从堆栈中弹出下一个节点E并将其标记为已访问。节点E的相邻节点是已被访问的C。因此，我们将其忽略。

现在，只有节点D保留在堆栈中。因此，我们将其标记为已访问。它的相邻节点是A，该节点已经被访问过。因此，我们不将其添加到堆栈中。

此时，堆栈为空。这意味着我们已经完成了给定图的深度优先遍历。

访问列表使用深度优先技术给出了遍历的最终顺序。上图的最终DFS序列是A-> B-> C-> E-> D。

DFS实施

package GraphDFS;
 
import java.io.*;
import java.util.*;
 
//DFS Technique for undirected graph
class Graph {
	private int Vertices; // No. of vertices
 
	// adjacency list declaration
	private LinkedList<Integer> adj_list[];
 
	// graph Constructor: to initialize adjacency lists as per no of vertices
	Graph(int v) {
		Vertices = v;
		adj_list = new LinkedList[v];
		for (int i = 0; i < v; ++i)
			adj_list[i] = new LinkedList();
	}
 
	// add an edge to the graph
	void addEdge(int v, int w) {
		adj_list[v].add(w); // Add w to v's list.
	}
 
	// helper function for DFS technique
	void DFS_helper(int v, boolean visited[]) {
		// current node is visited
		visited[v] = true;
		System.out.print(v + " ");
 
		// process all adjacent vertices
		Iterator<Integer> i = adj_list[v].listIterator();
		while (i.hasNext()) {
			int n = i.next();
			if (!visited[n])
				DFS_helper(n, visited);
		}
	}
 
	void DFS(int v) {
		// initially none of the vertices are visited
		boolean visited[] = new boolean[Vertices];
 
		// call recursive DFS_helper function for DFS technique
		DFS_helper(v, visited);
	}
}
 
class Main {
	public static void main(String args[]) {
		// create a graph object and add edges to it
		Graph g = new Graph(5);
		g.addEdge(0, 1);
		g.addEdge(0, 2);
		g.addEdge(0, 3);
		g.addEdge(1, 2);
		g.addEdge(2, 4);
		// print the DFS Traversal sequence
		System.out.println("Depth First Traversal for given graph" + "(with 0 as starting vertex)");
		g.DFS(0);
	}
}

输出：

DFS的应用

＃1）检测图中的循环：当我们可以回溯到边缘时，DFS有助于检测图中的循环。

＃2）寻路：正如我们在DFS插图中已经看到的，给定任何两个顶点，我们都可以找到这两个顶点之间的路径。

＃3）最小 生成树和最短路径：如果我们在非加权图上运行DFS技术，它将为我们提供最小生成树和最短路径。

＃4）拓扑排序：当我们必须安排作业时，使用拓扑排序。我们在各种工作之间有依赖性。我们还可以使用拓扑排序来解决链接器，指令调度程序，数据序列化等之间的依赖关系。

广度优先遍历

广度优先（BFS）技术使用队列存储图的节点。与DFS技术不同，在BFS中，我们横向遍历图形。这意味着我们明智地遍历图形。当我们在一个级别上探索所有顶点或节点时，我们将进入下一个级别。

下面给出的是广度优先遍历技术的算法。

算法

让我们看看BFS技术的算法。

给定一个图G，我们需要对其执行BFS技术。

• 步骤1：从根节点开始，然后将其插入队列。
• 步骤2：对图中的所有节点重复步骤3和4。
• 步骤3：从队列中删除根节点，并将其添加到Visited列表中。
• 步骤4： 现在将根节点的所有相邻节点添加到队列中，并对每个节点重复步骤2至4。[END OF LOOP]
• 步骤6： 退出

BFS的插图

让我们使用下面显示的示例图来说明BFS技术。请注意，我们维护了一个名为“访问”的列表和一个队列。为了清晰起见，我们使用在DFS示例中使用的同一图形。

首先，我们从根即节点A开始，并将其添加到访问列表。节点A的所有相邻节点（即B，C和D）都添加到队列中。

接下来，我们从队列中删除节点B。我们将其添加到“已访问”列表中，并将其标记为“已访问”。接下来，我们探索队列中B的相邻节点（C已经在队列中）。另一个相邻的节点A已经被访问过，因此我们将其忽略。

接下来，我们从队列中删除节点C并将其标记为已访问。我们将C添加到访问列表，并将其相邻节点E添加到队列。

接下来，我们从队列中删除D并将其标记为已访问。节点D的相邻节点A已被访问，因此我们将其忽略。

因此，现在只有节点E在队列中。我们将其标记为已访问，并将其添加到已访问列表。E的相邻节点是已被访问的C。因此，请忽略它。

此时，队列为空，并且访问列表具有我们通过BFS遍历而获得的序列。顺序是A-> B-> C-> D-> E。

BFS实施

以下Java程序显示了BFS技术的实现。

package GraphBFS;
 
import java.io.*;
import java.util.*;
 
//undirected graph represented using adjacency list.  
class Graph {
	private int Vertices; // No. of vertices
	private LinkedList<Integer> adj_list[]; // Adjacency Lists
 
	// graph Constructor:number of vertices in graph are passed
	Graph(int v) {
		Vertices = v;
		adj_list = new LinkedList[v];
		for (int i = 0; i < v; ++i) // create adjacency lists
			adj_list[i] = new LinkedList();
	}
 
	// add an edge to the graph
	void addEdge(int v, int w) {
		adj_list[v].add(w);
	}
 
	// BFS traversal from the root_node
	void BFS(int root_node) {
		// initially all vertices are not visited
		boolean visited[] = new boolean[Vertices];
 
		// BFS queue
		LinkedList<Integer> queue = new LinkedList<Integer>();
 
		// current node = visited, insert into queue
		visited[root_node] = true;
		queue.add(root_node);
 
		while (queue.size() != 0) {
			// deque an entry from queue and process it
			root_node = queue.poll();
			System.out.print(root_node + " ");
 
			// get all adjacent nodes of current node and process
			Iterator<Integer> i = adj_list[root_node].listIterator();
			while (i.hasNext()) {
				int n = i.next();
				if (!visited[n]) {
					visited[n] = true;
					queue.add(n);
				}
			}
		}
	}
}
 
class Main {
	public static void main(String args[]) {
		// create a graph with 5 vertices
		Graph g = new Graph(5);
		// add edges to the graph
		g.addEdge(0, 1);
		g.addEdge(0, 2);
		g.addEdge(0, 3);
		g.addEdge(1, 2);
		g.addEdge(2, 4);
		// print BFS sequence
		System.out.println("Breadth-first traversal of graph with 0 as starting vertex:");
		g.BFS(0);
	}
}

输出：

BFS遍历的应用

＃1）垃圾收集：垃圾收集技术用来复制垃圾收集的算法之一是“切尼算法”。该算法使用广度优先遍历技术。

＃2）网络中的广播：使用BFS技术将数据包从网络中的一个点广播到另一点。

＃3）GPS导航：在使用GPS导航时，我们可以使用BFS技术找到相邻的节点。

＃4）社交网站： BFS技术也用于社交网站中，以查找特定人员周围的人际网络。

＃5）未加权图中的最短路径和最小生成树：在未加权图中，BFS技术可用于查找最小生成树和节点之间的最短路径。

Java图形库

Java并不强制程序员必须始终在程序中实现图形。Java提供了许多现成的库，可以直接使用它们来利用程序中的图。这些库具有充分利用图形及其各种功能所需的所有图形API功能。

下面给出的是Java中某些图形库的简要介绍。

＃1）Google Guava： Google Guava提供了一个丰富的库，该库支持图和算法，包括简单图，网络，值图等。

＃2）Apache Commons： Apache Commons是一个Apache项目，它提供Graph数据结构组件和API，这些组件和API对该图数据结构进行操作。这些组件是可重用的。

＃3）JGraphT： JGraphT是广泛使用的Java图形库之一。它提供了图数据结构功能，其中包括简单图，有向图，加权图等，以及在图数据结构上工作的算法和API。

＃4）SourceForge JUNG： JUNG代表“ Java通用网络/图形”，并且是Java框架。JUNG提供了一种可扩展的语言，用于分析，可视化和建模我们要表示为图形的数据。

JUNG还提供用于分解，聚类，优化等的各种算法和例程。

经常问的问题

Q＃1）什么是Java图？

答：图形数据结构主要存储连接的数据，例如，人的网络或城市的网络。图数据结构通常由称为顶点的节点或点组成。每个顶点使用称为边的链接连接到另一个顶点。

Q＃2）图的类型是什么？

答：下面列出了不同类型的图。

1. 折线图：折线图用于绘制特定属性相对于时间的变化。
2. 条形图：条形图比较实体的数值，例如各个城市的人口，全国的识字率等。

除了这些主要类型外，我们还具有其他类型，例如象形图，直方图，面积图，散点图等。

Q＃3）什么是连通图？

答案：连通图是其中每个顶点都连接到另一个顶点的图。因此，在连接图中，我们可以从每个其他顶点到达每个顶点。

Q＃4）图的应用是什么？

答：图形可用于多种应用程序。该图可用于表示复杂的网络。图形还用于社交网络应用程序中，以表示人员网络以及诸如查找邻居或人脉之类的应用程序。

图形用于表示计算机科学中的计算流程。

问＃5）如何存储图形？

答：有三种方法可以将图形存储在内存中：

＃1）我们可以将节点或顶点存储为对象，将边存储为指针。

＃2）我们还可以将图存储为邻接矩阵，其行和列与顶点数相同。每行和列的交集表示边的存在或不存在。在非加权图中，边缘的存在由1表示，而在加权图中，边缘的存在被边缘的权重代替。

＃3）存储图形的最后一种方法是使用图形顶点或节点之间的边的邻接列表。每个节点或顶点都有其邻接表。

结论

在本教程中，我们详细讨论了Java中的图形。我们探索了各种类型的图，图实现和遍历技术。可以使用图来查找节点之间的最短路径。