转载请标明出处，谢谢！
https://www.jianshu.com/p/cf03e51a3ca2
关联文章
冒泡、选择排序 https://www.jianshu.com/p/176b0b892591
栈和队列 https://www.jianshu.com/p/8cb602ef4e21
顺序表、单双链表 https://www.jianshu.com/p/3aeb5998e79e
二叉树 https://www.jianshu.com/p/de829eab944c
图论 https://www.jianshu.com/p/cf03e51a3ca2
图
定义：图(graph)是由一些点(vertex)和这些点之间的连线(edge)所组成的；其中，点通常被成为”顶点(vertex)”，而点与点之间的连线则被成为”边或弧”(edege)。通常记为，G=(V,E)。
无向图
image.png
有向图
image.png
邻接点
一条边上的两个顶点叫做邻接点。 例如无向图中的A点的B点就是邻接点
在有向图中，除了邻接点之外；还有”入边”和”出边”的概念。
顶点的入边，是指以该顶点为终点的边。而顶点的出边，则是指以该顶点为起点的边。
度
在无向图中，某个顶点的度是邻接到该顶点的边(或弧)的数目。
例如，上面无向图中顶点A的度是3。
在有向图中，度还有”入度”和”出度”之分。
某个顶点的入度，是指以该顶点为终点的边的数目。而顶点的出度，则是指以该顶点为起点的边的数目。
顶点的度=入度+出度。
例如，上面有向图G2中，顶点B的入度是2，出度是2；顶点B的度=2+2=4。
路径和回路
路径：如果顶点(Vm)到顶点(Vn)之间存在一个顶点序列。则表示Vm到Vn是一条路径。
路径长度：路径中”边的数量”。
简单路径：若一条路径上顶点不重复出现，则是简单路径。
回路：若路径的第一个顶点和最后一个顶点相同，则是回路。
简单回路：第一个顶点和最后一个顶点相同，其它各顶点都不重复的回路则是简单回路。
连通图和连通分量
连通图：对无向图而言，任意两个顶点之间都存在一条无向路径，则称该无向图为连通图。 对有向图而言，若图中任意两个顶点之间都存在一条有向路径，则称该有向图为强连通图。
连通分量：非连通图中的各个连通子图称为该图的连通分量。
权
image.png
在某些图中，边具有与之相关的数值，称为权
邻接矩阵
用一个一维数组存放图中所有顶点数据；用一个二维数组存放顶点间关系（边或弧）的数据，这个二维数组称为邻接矩阵。
无向图
image.png
有向图
image.png
带权有向图
image.png
邻接表
邻接表存储的基本思想：对于图的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，称为顶点vi的边表（对于有向图则称为出边表），所有边表的头指针和存储顶点信息的一维数组构成了顶点表。
将节点存入数组中，并对节点的孩子进行链式存储，不管有多少孩子，也不会存在空间按浪费的问题，这个思路同样适用于图的存储。我们把这种数组与链表相结合的存储方法称为邻接表
无向图
image.png
有向图
image.png
带权
image.png
图的遍历
[参考:]（https://blog.csdn.net/zhangxiangdavaid/article/details/38323633）
深度遍历
从图的某个顶点出发，访问图中的所有顶点，且使每个顶点仅被访问一次。这一过程叫做图的遍历。
深度优先搜索的思想：
①访问顶点v；
②依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
③若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。
比如：
image
在这里为了区分已经访问过的节点和没有访问过的节点，我们引入一个一维数组bool visited[MaxVnum]用来表示与下标对应的顶点是否被访问过，
流程：
☐ 首先输出 V1，标记V1的flag=true;
☐ 获得V1的邻接边 [V2 V3],取出V2，标记V2的flag=true;
☐ 获得V2的邻接边[V1 V4 V5],过滤掉已经flag的，取出V4，标记V4的flag=true;
☐ 获得V4的邻接边[V2 V8],过滤掉已经flag的，取出V8，标记V8的flag=true;
☐ 获得V8的邻接边[V4 V5],过滤掉已经flag的，取出V5，标记V5的flag=true;
☐ 此时发现V5的所有邻接边都已经被flag了，所以需要回溯。（左边黑色虚线，回溯到V1，回溯就是下层递归结束往回返）
☐image
☐ 回溯到V1，在前面取出的是V2，现在取出V3，标记V3的flag=true;
☐ 获得V3的邻接边[V1 V6 V7]，过滤掉已经flag的,取出V6，标记V6的flag=true;
☐ 获得V6的邻接边[V3 V7],过滤掉已经flag的,取出V7，标记V7的flag=true;
☐ 此时发现V7的所有邻接边都已经被flag了，所以需要回溯。（右边黑色虚线，回溯到V1，回溯就是下层递归结束往回返）
图例：
image.png
代码：
public void depthTraverse() {
for (int i = 0; i < verticesSize; i++) {
if (!isVisited[i]) {
/*如果顶点没被访问过先打印*/
System.out.println("打印顶点" + vertices[i]);
traverse(i);
}
}
}
public void traverse(int i) {
isVisited[i] = true;
int v = getFirstBor(i);
while (v!=-1){
if(!isVisited[v]){
System.out.println("visit ="+vertices[v]);
traverse(v);
}
/**
* 以下代码会先压入栈中，在递归完成后会以先进后出的
* 形式执行，达到从下往上把各个顶点的邻接点打印的效果
* 0
* / \
* 1 4
* / \ \
* 2 5 6
* /
* 3
*/
v = getNextBor(i,v);
}
}
结果：
image.png
广度优先遍历
所谓广度，就是一层一层的，向下遍历，层层堵截，还是这幅图，我们如果要是广度优先遍历的话，我们的结果是V1 V2 V3 V4 V5 V6 V7 V8。
image
广度优先搜索的思想：
① 访问顶点vi ；
② 访问vi 的所有未被访问的邻接点w1 ,w2 , …wk ；
③ 依次从这些邻接点（在步骤②中访问的顶点）出发，访问它们的所有未被访问的邻接点; 依此类推，直到图中所有访问过的顶点的邻接点都被访问；
说明：
为实现③，需要保存在步骤②中访问的顶点，而且访问这些顶点的邻接点的顺序为：先保存的顶点，其邻接点先被访问。 这里我们就想到了用标准模板库中的queue队列来实现这种先进现出的服务。
老规矩我们还是走一边流程：
说明：
☐将V1加入队列，取出V1，并标记为true(即已经访问)，将其邻接点加进入队列，则 <—[V2 V3]
☐取出V2，并标记为true(即已经访问)，将其未访问过的邻接点加进入队列，则 <—[V3 V4 V5]
☐取出V3，并标记为true(即已经访问)，将其未访问过的邻接点加进入队列，则 <—[V4 V5 V6 V7]
☐取出V4，并标记为true(即已经访问)，将其未访问过的邻接点加进入队列，则 <—[V5 V6 V7 V8]
☐取出V5，并标记为true(即已经访问)，因为其邻接点已经加入队列，则 <—[V6 V7 V8]
☐取出V6，并标记为true(即已经访问)，将其未访问过的邻接点加进入队列，则 <—[V7 V8]
☐取出V7，并标记为true(即已经访问)，将其未访问过的邻接点加进入队列，则 <—[V8]
☐取出V8，并标记为true(即已经访问)，将其未访问过的邻接点加进入队列，则 <—[]
图例
image.png
/**
* 广度优先
*/
public void bfs(){
for (int i = 0; i < verticesSize; i++) {
isVisited[i]=false;
}
for (int i = 0; i < verticesSize; i++) {
if(!isVisited[i]){
isVisited[i]=true;
System.out.println("visited vertice:"+ vertices[i]);
bfs(i);
}
}
}
public void bfs() {
for (int i = 0; i < verticesSize; i++) {
if (!isVisited[i]) {
/*如果顶点没被访问过先打印*/
System.out.println("打印顶点" + vertices[i]);
isVisited[i] = true;
bfs(i);
}
}
}
public void bfs(int i) {
/*自定义的队列*/
Queue queue = new Queue();
int first = getFirstBor(i);
/*如果存在且没有被访问过*/
if (first != -1 && !isVisited[first]) {
isVisited[first] = true;
System.out.println("first " + vertices[first]);
queue.enQueue(queue, first);
}
int next = getNextBor(i, first);
while (next != -1) {
if (!isVisited[next]) {
isVisited[next] = true;
System.out.println("next " + vertices[next]);
queue.enQueue(queue, next);
}
next = getNextBor(i, next);
}
/*重复以上操作*/
while (queue.front != queue.rear) {
int temp = queue.array[queue.front];
bfs(temp);
queue.front = (queue.front + 1) % queue.MAX_LENGTH;
}
}
结果：
image.png
两种算法的复杂度分析
深度优先
数组表示：查找所有顶点的所有邻接点所需时间为O(n2)，n为顶点数，算法时间复杂度为O(n2)
广度优先
数组表示：查找每个顶点的邻接点所需时间为O(n2)，n为顶点数，算法的时间复杂度为O(n2)
代码
public class MyGraph {
/*顶点集*/
public String[] vertices;
/*图的边的信息*/
public int[][] matrix;
/*矩阵大小*/
public int verticesSize;
/*被访问过的顶点集合*/
public boolean[] isVisited;
public static final int MAX_WEIGHT = Integer.MAX_VALUE;
public MyGraph(int verticesSize) {
this.verticesSize = verticesSize;
vertices = new String[verticesSize];
matrix = new int[verticesSize][verticesSize];
isVisited = new boolean[verticesSize];
for (int i = 0; i < verticesSize; i++) {
vertices[i] = "v" + i;
}
}
/*获取第一个邻接点*/
public int getFirstBor(int v) {
for (int i = 0; i < verticesSize; i++) {
if (matrix[v][i] > 0 && matrix[v][i] < MAX_WEIGHT) {
// System.out.println(v + " first " + i);
return i;
}
}
return -1;
}
/**
* 获取到顶点v的邻接点index的下一个邻接点
*/
public int getNextBor(int v, int index) {
for (int i = index + 1; i < verticesSize; i++) {
// System.out.println(v + "---" + i + "---" + matrix[v][i]);
if (matrix[v][i] > 0 && matrix[v][i] < MAX_WEIGHT) {
// System.out.println(v + " next " + i);
return i;
}
}
return -1;
}
public void depthTraverse() {
for (int i = 0; i < verticesSize; i++) {
if (!isVisited[i]) {
/*如果顶点没被访问过先打印*/
System.out.println("打印顶点" + vertices[i]);
traverse(i);
}
}
}
public void traverse(int i) {
isVisited[i] = true;
int v = getFirstBor(i);
while (v != -1) {
if (!isVisited[v]) {
System.out.println("visit =" + vertices[v]);
traverse(v);
}
/**
* 以下代码会先压入栈中，在递归完成后会以先进后出的
* 形式执行，达到从下往上把各个顶点的邻接点打印的效果
* 0
* / \
* 1 4
* / \ \
* 2 5 6
* /
* 3
*/
v = getNextBor(i, v);
}
}
public void dfs(int i) {
isVisited[i] = true;
int v = getFirstBor(i);
if (v != -1) {
if (!isVisited[v]) {
System.out.println("visit =" + vertices[v]);
traverse(v);
}
/**
* 以下代码会先压入栈中，在递归完成后会以先进后出的
* 形式执行，达到从下往上把各个顶点的邻接点打印的效果
* 0
* / \
* 1 4
* / \ \
* 2 5 6
* /
* 3
*/
// v = getNextBor(i,v);
}
}
public void bfs() {
for (int i = 0; i < verticesSize; i++) {
if (!isVisited[i]) {
/*如果顶点没被访问过先打印*/
System.out.println("打印顶点" + vertices[i]);
isVisited[i] = true;
bfs(i);
}
}
}
public void bfs(int i) {
/*自定义的队列*/
Queue queue = new Queue();
int first = getFirstBor(i);
/*如果存在且没有被访问过*/
if (first != -1 && !isVisited[first]) {
isVisited[first] = true;
System.out.println("first " + vertices[first]);
queue.enQueue(queue, first);
}
int next = getNextBor(i, first);
while (next != -1) {
if (!isVisited[next]) {
isVisited[next] = true;
System.out.println("next " + vertices[next]);
queue.enQueue(queue, next);
}
next = getNextBor(i, next);
}
/*重复以上操作*/
while (queue.front != queue.rear) {
int temp = queue.array[queue.front];
bfs(temp);
queue.front = (queue.front + 1) % queue.MAX_LENGTH;
}
}
}
网友评论