图
为什么要学习图
- 之前的
数据结构都不存在多对多的关系- 线性表局限于一对一
- 树局限于一对多
图的类型
无向图
- 顶点（vertex），边（edge）
- 顶点之间的连接没有方向
- 路径：从任一顶点开始，由边或弧的邻接至关系构成的有限长顶点序列
比如：从D -> C的路径有：
D -> A -> B -> C
D -> B-> C
有向图
- 顶点之间存在方向
- A只能通向B，而B不能通向A
带权图
- 边带权值的图（也称为网）
图的表达方式
二维数组表示（邻接矩阵）
邻接矩阵：表示图形中顶点之间相邻关系的矩阵
对于 n 个顶点的图而言，矩阵的 row 和 col 表示的是 1…n 个点
- 0 表示不存在连接
- 1 表示存在连接
链表表示（邻接表）
- 邻接矩阵需要给每个顶点都分配 n 个空间，但存在很多边其实没有被使用的情况，浪费空间，所以常常选择用邻接表来表示图
- 邻接表的实现只存储存在的边，不会存储不存在的边，所以邻接表比邻接矩阵更加节约空间
邻接表的组成
数组 + 链表
每个顶点都对应一个链表，链表中存储的是相连的顶点
比如在下图中
以 0 为顶点作链表。由图可知，0与1 2 3 4 相连，所以将相连的几个顶点放置到链表中
图的实现
实现要求
思路分析
- 存储顶点
String- 使用集合
ArrayList
- 使用集合
- 保存矩阵
- 使用二维数组
代码实现
import java.util.ArrayList;
import java.util.Arrays;
public class Graph {
private ArrayList<String> vertexList;//存储顶点集合
private int[][] edges;//存储边的邻接矩阵
private int numOfEdges;//边的数目
//构造器
public Graph(int n){
//初始化
vertexList = new ArrayList<String>(n);
edges = new int[n][n];
numOfEdges = 0;
}
/*
* 图的常用方法
* 返回节点的个数
* 得到边的数目
* 返回节点i对应的值
* 返回v1与v2的权值
* 显示图对应的矩阵
*/
//显示图对应的矩阵
public void showGraph(){
for(int[] links : edges){
System.out.println(Arrays.toString(links));
}
}
//返回节点的个数
public int getNumOfVertex(){
return vertexList.size();
}
//得到边的数目
public int getNumOfEdges(){
return numOfEdges;
}
//返回节点i对应的值
public String getValue(int i){
return vertexList.get(i);
}
//返回v1与v2的权值
public int getWeight(int v1, int v2){
return edges[v1][v2];
}
public void insertVertex(String vertex){
vertexList.add(vertex);
}
/**
*
* @param v1 第一个顶点的下标（即第几个顶点）
* @param v2 第二个顶点的下标（即第几个顶点）
* @param weight 表示边
*/
public void insertEdge(int v1, int v2, int weight){
edges[v1][v2] = weight;
edges[v2][v1] = weight;
numOfEdges++;
}
//测试
public static void main(String[] args) {
int n = 5;
String[] vertexs = new String[]{"A","B","C","D","E"};
//初始化图
Graph graph = new Graph(n);
//添加顶点
for(String vertex : vertexs){
graph.insertVertex(vertex);
}
//添加边
graph.insertEdge(0,1,1);
graph.insertEdge(0,2,1);
graph.insertEdge(1,2,1);
graph.insertEdge(1,3,1);
graph.insertEdge(1,4,1);
//显示邻接矩阵
graph.showGraph();
}
}
图的遍历
深度优先搜索（Depth First Search）
- 深度优先搜索：从顶点v出发，访问v的所有未被访问的邻接顶点，再对该顶点进行深度优先遍历，直至v的所有邻接顶点被访问。
- 如果这个邻接顶点被访问或者无邻接顶点，则返回上一节点。若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到所有顶点均被访问过为止。
DFS的典型例子：
走迷宫。沿着一条路走，走不通则返回，然后再走其他路。
- 这样的访问策略是优先纵向访问，而不是对一个顶点的所有邻接顶点进行横向访问
- 深度优先搜索是一个递归的过程
算法步骤
- 访问初始结点 v，并标记结点 v 为
已访问 - 查找结点 v 的第一个邻接结点w
- 如果 w 存在，则执行步骤4。如果不存在，则回到步骤1，然后从v的下一个结点继续查找
- 如果 w 未被访问，则继续对 w 进行深度优先遍历
- 如果 w 已被访问，则返回到 v ，继续进行步骤3
例子
代码实现
import java.util.ArrayList;
import java.util.Arrays;
public class Graph {
private ArrayList<String> vertexList;//存储顶点集合
private int[][] edges;//存储边的邻接矩阵
private int numOfEdges;//边的数目
private boolean[] isVisit;//记录某个结点是否被访问过
//构造器
public Graph(int n){
//初始化
vertexList = new ArrayList<String>(n);
edges = new int[n][n];
numOfEdges = 0;
isVisit = new boolean[n];
}
//得到第一个邻接结点的下标 w
/**
*
* @param index
* @return 如果存在邻接结点，则返回对应的下标。如果不存在，则返回-1
*/
public int getFirstNeighbor(int index){
for(int i = 0; i < vertexList.size(); i++){
if(edges[index][i] != 0){
return i;
}
}
return -1;
}
//根据前一个邻接结点的下标获取下一个邻接结点
/**
*
* @param v1 上一个结点
* @param v2 上一个结点的另外一个邻接结点
* @return
*/
public int getNextNeighbor(int v1, int v2){
for(int i = v2 + 1; i < vertexList.size(); i++){
if(edges[v1][i] > 0){
return i;
}
}
return -1;
}
//深度优先遍历算法
p void dfs(boolean[] isVisit, int i){
//访问当前结点
System.out.print(getValueByIndex(i) + " -> ");
//将当前结点设置为已访问
isVisit[i] = true;
//查找结点i的第一个邻接结点
int w = getFirstNeighbor(i);
while(w != -1){
if(!isVisit[w]){
dfs(isVisit,w);
}
w = getNextNeighbor(i,w);
}
}
//重载dfs，遍历所有结点并进行dfs
public void dfs(){
for(int i = 0; i < getNumOfVertex(); i++){
if(!isVisit[i]){
dfs(isVisit,i);
}
}
}
/*
* 图的常用方法
* 返回节点的个数
* 得到边的数目
* 返回节点i对应的值
* 返回v1与v2的权值
* 显示图对应的矩阵
*/
//显示图对应的矩阵
public void showGraph(){
for(int[] links : edges){
System.out.println(Arrays.toString(links));
}
}
//返回节点的个数
public int getNumOfVertex(){
return vertexList.size();
}
//得到边的数目
public int getNumOfEdges(){
return numOfEdges;
}
//返回节点i对应的值
public String getValueByIndex(int i){
return vertexList.get(i);
}
//返回v1与v2的权值
public int getWeight(int v1, int v2){
return edges[v1][v2];
}
public void insertVertex(String vertex){
vertexList.add(vertex);
}
/**
*
* @param v1 第一个顶点的下标（即第几个顶点）
* @param v2 第二个顶点的下标（即第几个顶点）
* @param weight 表示边
*/
public void insertEdge(int v1, int v2, int weight){
edges[v1][v2] = weight;
edges[v2][v1] = weight;
numOfEdges++;
}
//测试
public static void main(String[] args) {
int n = 5;
String[] vertexs = new String[]{"A","B","C","D","E"};
//初始化图
Graph graph = new Graph(n);
//添加顶点
for(String vertex : vertexs){
graph.insertVertex(vertex);
}
//添加边
graph.insertEdge(0,1,1);
graph.insertEdge(0,2,1);
graph.insertEdge(1,2,1);
graph.insertEdge(1,3,1);
graph.insertEdge(1,4,1);
System.out.println("深度优先遍历");
graph.dfs();
System.out.println();
//显示邻接矩阵
graph.showGraph();
}
}
证明
- 与理论分析结果相同
广度优先遍历（Broad First Search）
- 类似于
分层搜索 - 需要用队列来保持访问过的结点的顺序，以便以按照顺序来访问结点的邻接结点
算法步骤
- 访问初始结点 v 并标记结点 v 为已访问
- 结点 v 入队列
- 当队列非空时，继续执行，否则算法结束
- 出队列，取得队头结点 u
- 查找结点 u 的第一个邻接结点 w
- 若结点u的邻接结点w不存在，则回到步骤3，否则循环执行下面的步骤
- 若结点 w 没有被访问，则访问结点 w 并标记为已访问
- 结点 w 入队列
- 查找结点 u 的继 w 邻接结点后的下一个邻接结点 w
例子
代码实现
import java.util.*;
public class Graph {
private ArrayList<String> vertexList;//存储顶点集合
private int[][] edges;//存储边的邻接矩阵
private int numOfEdges;//边的数目
private boolean[] isVisit;//记录某个结点是否被访问过
//构造器
public Graph(int n){
//初始化
vertexList = new ArrayList<String>(n);
edges = new int[n][n];
numOfEdges = 0;
isVisit = new boolean[n];
}
//得到第一个邻接结点的下标 w
/**
*
* @param index
* @return 如果存在邻接结点，则返回对应的下标。如果不存在，则返回-1
*/
public int getFirstNeighbor(int index){
for(int i = 0; i < vertexList.size(); i++){
if(edges[index][i] != 0){
return i;
}
}
return -1;
}
//根据前一个邻接结点的下标获取下一个邻接结点
/**
*
* @param v1 上一个结点
* @param v2 上一个结点的另外一个邻接结点
* @return
*/
public int getNextNeighbor(int v1, int v2){
for(int i = v2 + 1; i < vertexList.size(); i++){
if(edges[v1][i] > 0){
return i;
}
}
return -1;
}
public void resetIsVisit(){
isVisit = new boolean[getNumOfVertex()];
}
//广度优先遍历
public void bfs(int index){
resetIsVisit();
int head;
int neighbor;
Queue<Integer> queue = new LinkedList<>();
queue.add(index);
System.out.print(getValueByIndex(index) + "-> ");
isVisit[index] = true;
while(!queue.isEmpty()){
head = queue.poll();
neighbor = getFirstNeighbor(head);
while(neighbor != -1){
if(!isVisit[neighbor]){
System.out.print(getValueByIndex(neighbor) + "-> ");
isVisit[neighbor] = true;
queue.add(neighbor);
}
neighbor = getNextNeighbor(head,neighbor);
}
}
}
/*
* 图的常用方法
* 返回节点的个数
* 得到边的数目
* 返回节点i对应的值
* 返回v1与v2的权值
* 显示图对应的矩阵
*/
//显示图对应的矩阵
public void showGraph(){
for(int[] links : edges){
System.out.println(Arrays.toString(links));
}
}
//返回节点的个数
public int getNumOfVertex(){
return vertexList.size();
}
//得到边的数目
public int getNumOfEdges(){
return numOfEdges;
}
//返回节点i对应的值
public String getValueByIndex(int i){
return vertexList.get(i);
}
//返回v1与v2的权值
public int getWeight(int v1, int v2){
return edges[v1][v2];
}
public void insertVertex(String vertex){
vertexList.add(vertex);
}
/**
*
* @param v1 第一个顶点的下标（即第几个顶点）
* @param v2 第二个顶点的下标（即第几个顶点）
* @param weight 表示边
*/
public void insertEdge(int v1, int v2, int weight){
edges[v1][v2] = weight;
edges[v2][v1] = weight;
numOfEdges++;
}
//测试
public static void main(String[] args) {
int n = 5;
String[] vertexs = new String[]{"A","B","C","D","E"};
//初始化图
Graph graph = new Graph(n);
//添加顶点
for(String vertex : vertexs){
graph.insertVertex(vertex);
}
//添加边
graph.insertEdge(0,1,1);
graph.insertEdge(0,2,1);
graph.insertEdge(1,2,1);
graph.insertEdge(1,3,1);
graph.insertEdge(1,4,1);
System.out.println("广度优先遍历");
graph.bfs(1);
System.out.println();
//显示邻接矩阵
graph.showGraph();
}
}
证明
- 与理论分析结果相同
