一个图包括两部分信息：顶点的信息以及描述顶点之间关系的信息。
图的邻接矩阵存储也称数组表示法，其方法是用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息，存储顶点之间邻接关系的二维数组称为邻接矩阵。
用邻接矩阵存储图
1.
确定图的顶点个数和边的个数
2.
输入顶点信息存储在一维数组
vertex
中
3.
初始化邻接矩阵；
4.
依次输入每条边存储在邻接矩阵
arc
中
-
-
输入边依附的两个顶点的序号
i,j;
-
将邻接矩阵的第
i
行第
j
列的元素值置为
1
；
-
将邻接矩阵的第
j
行第
i
列的元素值置为
1
；
由于大部分图都是稀疏图利用邻接矩阵存储开销会很大。
n
条边的用二维数组来表示的话，开销就是
n*n,
对于这种情况，对邻接矩阵做一下变化，用一个一维数组
vertex[]
来存储顶点的集合
,
再用一个一维数组来存储边的信息，数组的每一个元素都记录边的起始点，终点的相关信息，这样就能将边的存储开销降为
n
。
利用上述方法来构造，在查找的时候每次都得查找一次，则最坏的效率为
e
（边数）的
n
次方，查找比较快捷的方式可以采用链表来实现。对于图的每个顶点
v
，将所有邻接于
v
的顶点链成一个单链表，所有边表的头指针和存储顶点信息的一维数组构成了顶点表，所以，在邻接表中存在两种结点结构：顶点表结构和边表结构。
利用一个一维数组来保存来保存顶点信息。给每一个顶点分配一个
vector
。
Vector
的每一个元素都保存着与顶点有关的一条边信息，这样，对于无向图来说，得到的存储效率为
n+2e,
而对于有向图来说，得到的存储效率为
n+e;
再可以分配一个规则，对于无向图来说，每次记录边的时候都可以采用从顶点位置低的向顶点位置高的记录，这样能使无向图的存储效率达到
n+e
。
<!--
@page { margin: 2cm }
P { margin-bottom: 0.21cm }
-->
图的遍历是指从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次。
图的遍历通常有深度优先遍历与广度优先遍历两种方式，这两种遍历次序对无向图和有向图都适用。
深度优先递归方法实现：
1.
访问顶点
v;
visited[v]=1;
2.w=
顶点
v
的第一个邻接点
3.while(w
存在
)
-
-
if(w
未被访问
)
从顶点
w
出发递归执行该算法
-
w=
顶点
v
的下一个邻接点
广度优先遍历实现：
1.
初始化队列
Q
2.
访问顶点
v
；
visited[v]=1;
顶点
v
入队
Q;
3.while(
队列
Q
非空
)
-
-
v=
队列
Q
的队头元素出队；
-
w=
顶点
v
的第一个邻接点
-
while(w
存在
)
3.3.1
如果
w
未被访问，则访问顶点
w;visited[w]=1;
顶点
w
入队列
Q
3.3.2 w=
顶点
v
的下一个邻接点
以下是利用vector来存储图的遍历实现：
Stack类：
package com.javaeye.rsrt;
/**
* 栈，遵循先进后出的原则，用来保存元素
*
* @author nishiting
*
*/
public class Stack {
private int[] st;
private int top;
private int count;
/**
* 构造一个栈
*
* @param size
* 栈的大小
*/
public Stack(int size) {
st = new int[size];
top = -1;
count = 0;
}
/**
* 元素进栈
*
* @param j
* 要进栈的元素
*/
public void push(int j) {
count++;
st[++top] = j;
}
/**
* 元素出栈
*
* @return 出栈的元素
*/
public int pop() {
return st[top--];
}
/**
* 查询栈顶元素
*
* @return 栈顶元素
*/
public int peek() {
return st[top];
}
/**
* 查询栈是否为空
*
* @return 栈是否为空
*/
public boolean isEmpty() {
count--;
return (top == -1);
}
/**
* 查看栈里的所有元素
*/
public void list() {
for (int i = 0; i < count; i++) {
System.out.print(st[i] + " ");
}
System.out.println();
}
/**
* 得到栈里一共有多少元素
*
* @return 栈里的元素个数
*/
public int getCount() {
return count;
}
/**
* 查看栈里是否包含某个元素
*
* @param i
* 要查询的元素
* @return 是否包含了要查询的元素
*/
public boolean isContains(int i) {
for (int k = 0; k < st.length; k++) {
System.out.print("开始比较" + i + "此时的result:");
list();
System.out.println();
if (st[k] == i) {
return true;
}
}
return false;
}
/**
* 得到栈里的元素集
* @return 栈里的元素集合
*/
public int[] getSt(){
return st;
}
}
Queue类：
package com.javaeye.rsrt;
public class Queue {
private int[] values;
private int begin = -1;
private int end = -1;
Queue(int size){
values = new int[size];
}
void push(int value){
values[++begin] = value;
}
int pop(){
return values[++end];
}
boolean isEmpty(){
return begin == end;
}
}
Graph类：
package com.javaeye.rsrt;
import java.util.Vector;
/**
*
* @author nishiting
*
*/
public class Graph {
int vertexNum;
Vector[] vector;
int[] visited;
Stack stack;
Stack result;
Queue queue;
/**
*
* 构造一个图
*
* @param num
* 图的顶点数
*
*/
public Graph(int num) {
vertexNum = num;
vector = new Vector[vertexNum];
visited = new int[vertexNum];
for (int i = 0; i < num; i++) {
visited[i] = 0;
}
stack = new Stack(num);
result = new Stack(num);
queue = new Queue(num);
}
/**
* 向图中添加无向边
*
* @param I
* 边的一个顶点
* @param J
* 边的另一个顶点
* @return 是否添加成功
*/
public boolean addEdge(int I, int J) {
/**
* 判断用户输入的是否是一个顶点，如果是，则返回flase,添加不成功
*/
if (J == I) {
return false;
}
/**
* 判断所输入的顶点值是否在图所顶点范围值内，如果不在，则提示顶点不存在
*
*/
if (I < vertexNum && J < vertexNum && I >= 0 && J >= 0) {
int k;
/**
* 如果i比j大，则将i与j交换
*/
if (I > J) {
k = I;
I = J;
J = k;
}
/**
*
* 判断边是否存在
*/
if (isEdgeExists(I, J)) {
return false;
}
/**
* 添加边
*/
vector[I].add(J);
return true;
}
return false;
}
/**
* 判断无向边是否存在
*
* @param i
* 要查询的无向边的一个顶点
* @param j
* 要查询的无向边的另一个顶点
* @return 边是否存在，false:不存在，true:存在
*/
public boolean isEdgeExists(int i, int j) {
/**
* 判断所输入的顶点值是否在图所顶点范围值内，如果不在，则提示顶点不存在
*
*/
if (i < vertexNum && j < vertexNum && i >= 0 && j >= 0) {
if (i == j) {
return false;
}
int k;
/**
* 如果i比j大的话，i与j进行交换
*/
if (i > j) {
k = i;
i = j;
j = k;
}
/**
* 判断i的邻接结点集是否为空
*/
if (vector[i] == null) {
vector[i] = new Vector(8);
}
/**
* 判断这条边是否存在，如果存在，则提示边已经存在
*/
for (int q = 0; q < vector[i].size(); q++) {
if (((Integer) vector[i].get(q)).intValue() == j) {
System.out.println("顶点" + i + "和" + "顶点" + j + "这两点之间存在边");
return true;
}
}
}
return false;
}
/**
* 进行深度优先遍历
*/
public void dfs() {
/**
* 从顶点0开始遍历
*/
visited[0] = 1;
stack.push(0);
/**
* 如果栈不为空的话，进行循环查询
*/
while (!stack.isEmpty()) {
int v = getAdjUnvisitedVertex(stack.peek());
/**
* 没找到未被访问的邻接点，元素出栈，如果找到的话，将这个结点标记为访问过，将其未被访问的邻接点入栈
*/
if (v == -1) {
result.push(stack.peek());
stack.pop();
} else {
visited[v] = 1;
stack.push(v);
}
}
System.out.println("进行深度优先的遍历顺序为：");
result.list();
}
/**
* 进行广度优先遍历
*/
public void bsf(){
/**
* 从顶点0开始遍历
*/
visited[0] = 1;
queue.push(0);
while(!queue.isEmpty()){
int v = queue.pop();
result.push(v);
int i;
while((i = getAdjUnvisitedVertex(v))!=-1){
visited[i]=1;
queue.push(i);
}
}
System.out.println("广度优先的遍历顺序为：");
result.list();
}
/**
* 得到指定结点的一个未被访问的邻接点位置
*
* @param v
* 要查询的顶点
* @return 顶点的下一个未被访问的邻接结点
*/
public int getAdjUnvisitedVertex(int v) {
int temp;
/**
* 判断邻接结点是否为空
*/
if (vector[v] != null) {
/**
* 遍历所有的邻接结点
*/
for (int j = 0; j < vector[v].size(); j++) {
temp = ((Integer) vector[v].get(j )).intValue();
/**
* 判断邻接结点是否被访问过
*/
if (visited[temp] == 0)
return ((Integer) vector[v].get(j)).intValue();
}
}
return -1;
}
/**
* 得到图的遍历顺序
*
* @return 图的遍历顺序
*/
public Stack getResult() {
return result;
}
}
测试类：
package com.javaeye.rsrt;
import junit.framework.TestCase;
public class GraphTest extends TestCase {
public void testAddEdge(){
// Graph graph = new Graph(10);
//
// /**
// * 测试向两个相同的顶点添加边
// */
// assertEquals(false,graph.addEdge(1, 1));
// assertEquals(false,graph.isEdgeExists(1, 1));
//
// /**
// * 测试向不存在的点添加边
// */
// assertEquals(false,graph.addEdge(-1, 1));
// assertEquals(false,graph.isEdgeExists(-1, 1));
// assertEquals(false,graph.addEdge(1, 15));
// assertEquals(false,graph.isEdgeExists(1, 15));
// assertEquals(false,graph.addEdge(-1, 15));
// assertEquals(false,graph.isEdgeExists(-1, 15));
//
// /**
// * 测试向两个合理的点添加边
// */
// assertEquals(true,graph.addEdge(1,6));
// assertEquals(true,graph.isEdgeExists(1, 6));
//
// /**
// * 测试向已有班的顶点添加
// */
// assertEquals(true,graph.isEdgeExists(1, 6));
// assertEquals(false,graph.addEdge(1,6));
// /**
// * 测试向边缘的点添加边
// *
// */
// assertEquals(true,graph.addEdge(0, 9));
// assertEquals(true,graph.isEdgeExists(0, 9));
//
// /**
// * 测试无向图由位置大的点向位置小的点添加
// */
// assertEquals(true,graph.addEdge(8, 4));
// assertEquals(true,graph.isEdgeExists(8, 4));
/**
* 测试一个简单的连通图
*/
Graph graph = new Graph(6);
graph.addEdge(0, 1);
graph.addEdge(0, 5);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(2, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 4);
graph.bsf();
// graph.dfs();
// int[] values = {3,4,2,1,5,0};
// int[] result = graph.getResult().getSt();
// for(int i = 0;i < values.length;i++){
// assertEquals(values[i],result[i]);
// }
/**
* 测试一个非连通图
*
*/
// graph = new Graph(6);
//
// graph.addEdge(0, 1);
// graph.addEdge(0, 5);
// graph.addEdge(0, 2);
// graph.addEdge(1, 2);
// graph.addEdge(1, 4);
// graph.addEdge(2, 4);
//
// graph.dfs();
//
// values = new int[] {4,2,1,5,0};
// result = graph.getResult().getSt();
// for(int i = 0;i < values.length;i++){
// assertEquals(values[i],result[i]);
// }
}
}
分享到：
相关推荐
本文将深入探讨Java中实现的四个核心图算法：深度优先遍历（DFS）、广度优先遍历（BFS）、最短路径算法以及最小生成树算法。 首先，**深度优先遍历（DFS）**是一种用于遍历或搜索树或图的算法。它从根节点开始，尽...
本篇文章将深入探讨如何使用Java来实现二叉树的深度优先遍历（DFS, Depth First Search）和广度优先遍历（BFS, Breadth First Search）。 **深度优先遍历** 是一种在图或树中搜索的方法，它尽可能深地探索树的分支...
根据遍历方式的不同，图的遍历可以分为深度优先遍历（DFS）和广度优先遍历（BFS）。本文将深入探讨这两种遍历方法，并提供其在Java中的实现。 ### 图的深度优先遍历（DFS） 深度优先遍历是一种递归地访问图中的...
用Java描述的图，以邻接表存储，包含常用算法
本资源包含了一些图算法的Java实现，包括但不限于广度优先搜索（BFS）、深度优先搜索（DFS）、最小生成树（Minimum Spanning Tree, MST）、弗洛伊德算法（Floyd-Warshall）以及拓扑排序。下面将详细介绍这些算法及其...
本文将详细探讨两种主要的图遍历算法：广度优先搜索（Breadth-First Search, BFS）和深度优先搜索（Depth-First Search, DFS），以及它们在Java编程语言中的实现。 **广度优先搜索（BFS）** 1. **概念**： 广度...
深度优先搜索（DFS，Depth-First Search）是图论与数据结构中的一种经典搜索算法，广泛应用于解决实际问题，如网络爬虫、迷宫求解、拓扑排序等。本课程“20180729数据结构与算法基础班深度优先搜索”将深入探讨这一...
【标题】：“广度优先搜索学习五例之二（JAVA）” 在计算机科学中，图算法是解决问题的关键工具之一，而广度优先搜索（Breadth-First Search, BFS）是一种用于遍历或搜索树或图的算法。本篇文章将重点讲解如何在...
本篇将详细讲解如何使用Java实现图的深度优先遍历（DFS, Depth-First Search）和广度优先遍历（BFS, Breadth-First Search）。 1. **深度优先遍历（DFS）**： - DFS 是一种递归策略，它沿着某条路径深入到图的深处...
总结起来，这个案例展示了如何利用Java泛型构建一个图数据结构，以及如何使用深度优先和广度优先遍历进行图的探索。泛型使我们的代码更具通用性，能够处理不同类型的数据，而图遍历算法则帮助我们解决实际问题，如...
在ACM-ICPC的训练中，BFS通常与图论和树的其他算法结合使用，例如深度优先搜索(DFS)、Dijkstra算法、Floyd-Warshall算法等，来解决更复杂的问题。对于树的遍历，BFS可以保证找到最接近根的路径。在图中，BFS能找出两...
这种策略倾向于先访问深度较大的节点，而不是广度较大的节点，与之相对的是广度优先搜索（BFS）。 在Java中实现DFS，通常使用递归或栈数据结构。递归方法是直接对每个未访问的邻接节点进行递归调用，而栈方法则将待...
本文将详细讲解"Graph-DFS_WFS.zip"压缩包中涉及的知识点，包括Java实现的无向图、深度优先遍历（DFS）以及宽度优先遍历（WFS）。 首先，我们来理解什么是无向图。无向图是一种图结构，其中的边没有方向性，即任意...
在这个资源中，你可能会遇到排序算法（如冒泡排序、快速排序、归并排序）、查找算法（如线性查找、二分查找）以及图算法（如深度优先搜索、广度优先搜索）。理解这些基础算法可以帮助你编写更高效、更优化的代码。 ...
深度优先搜索(DFS, Depth-First Search)是一种用于遍历或搜索树或图的算法，其基本思想是从起点开始，沿着某一条路径一直探索到尽可能深的层次，如果在当前路径上找不到目标，则回溯到上一个节点，换另一条路径继续...
实现这个功能的一种方法是遍历List，将所有节点构建成一棵树，然后采用深度优先搜索（DFS）或广度优先搜索（BFS）来获取排序后的节点列表。遍历过程中，可以使用HashMap或其他数据结构暂存节点及其子节点，以便于...
在`src`目录下，我们可能找到具体的拓扑排序算法实现，如`Graph.java`（表示图的类）、`Node.java`（表示图节点的类）和`TopologicalSort.java`（拓扑排序算法类）。这些类可能包含了构建图、计算入度、遍历和排序的...
4. **深度优先搜索（DFS）**：DFS是一种遍历或搜索树或图的算法，沿着树的深度优先遍历树的节点。在九宫格问题中，可以将每个宫格看作一个节点，从左上角开始，尝试填入下一个节点，若满足条件则继续，否则回溯。 5...
通常有两种主要的拓扑排序算法：深度优先搜索（DFS）和广度优先搜索（BFS）。 1. 深度优先搜索（DFS）拓扑排序： - 从任意一个没有前驱（入度为0）的顶点开始，进行DFS遍历。 - 访问过的顶点标记为已处理，并从其...
接着，拓扑排序的核心算法有两种常见方法：深度优先搜索（DFS）和广度优先搜索（BFS）。DFS会首先访问所有没有前驱（入度为0）的节点，然后递归地访问其后继节点；BFS则使用队列，同样从没有前驱的节点开始，逐层...