2 数据结构学习指南

时间:2023-02-01 07:59:02


2 数据结构学习指南

为了简单,我们的图都是用二维数组进行存储

            col1  col2  col3

row1   [  0      1       0

row2      1      0       1

row3      0      1       0 ]

2 数据结构学习指南

package graph;

/*矩阵初始化*/
public class Graph {
private int vexNum;
private String[] vexNode;
private int[][] matrix = new int[vexNum][vexNum];

public Graph(int vexNum, String[] vexNode, int[][] graph) {
this.vexNum = vexNum;
this.matrix = graph;
this.vexNode = vexNode;
}

// 获得第一个邻接点
public int getFirstAdjvex(int[][] matrix, int u) {
for (int i = 0; i < vexNum; i++) {
if (matrix[u][i] != 0) {
return i;
}
}
return -1;
}

// 反方向获得第一个邻接点
public int getReverseFirstAdjvex(int[][] matrix, int u) {
for (int i = 0; i < vexNum; i++) {
if (matrix[i][u] != 0) {
return i;
}
}
return -1;
}

// 获取下一个邻接点
public int getNextAdjvex(int[][] matrix, int u, int v) {
for (int i = v + 1; i < vexNum; i++) {
if (matrix[u][i] != 0) {
return i;
}
}
return -1;
}

// 获取下一个邻接点
public int getReverseNextAdjvex(int[][] matrix, int u, int v) {
for (int i = v + 1; i < vexNum; i++) {
if (matrix[i][u] != 0) {
return i;
}
}
return -1;
}

public int getVexNum() {
return vexNum;
}

public void setVexNum(int vexNum) {
this.vexNum = vexNum;
}

public int[][] getMatrix() {
return matrix;
}

public void setMatrix(int[][] graph) {
this.matrix = graph;
}

public String[] getVexNode() {
return vexNode;
}

public void setVexNode(String[] vexNode) {
this.vexNode = vexNode;
}

}

1 图的遍历

深度优先遍历

类似树的中序遍历,每次都访问第一个邻接点,把访问的节点置为已访问。如果,已经没有了第一个邻接点,则访问下一个邻接点。重复该过程。

广度优先遍历

每次访问一层邻接节点,一直往下访问

写算法

package graph.traverse;


import java.util.LinkedList;

import java.util.Queue;


import graph.Graph;


public class Traverse {



private Graph graph;

private boolean []isVisited=new boolean[100];

public void boardFirstSearch() {

for (int i = 0; i < graph.getVexNum(); i++) {

if (!isVisited[i]) {

boardFirstSearch(i);

}

}

}

private void boardFirstSearch(int i) {

int u,w;

Queue queue=new LinkedList<Integer>();

//1 当前节点下标如队列

queue.add(i);

System.out.print(graph.getVexNode()[i]+"-->");

while(!queue.isEmpty()){

u=(int) queue.remove();



isVisited[u]=true;

for(w=graph.getFirstAdjvex(graph.getMatrix(), u);w>=0;

w=graph.getNextAdjvex(graph.getMatrix(), u, w)){

if(!isVisited[w]){

System.out.print(graph.getVexNode()[w]+"-->");

isVisited[w]=true;

queue.add(w);

}

}

}



}



public void BFSFirstSearch() {

for (int i = 0; i < graph.getVexNum(); i++) {

if (!isVisited[i]) {

BFSFirstSearch(i);

}

}

}

private void BFSFirstSearch(int i) {

// TODO Auto-generated method stub

int w;

System.out.print(graph.getVexNode()[i]+"-->");

isVisited[i]=true;

for(w=graph.getFirstAdjvex(graph.getMatrix(), i);w>=0;

w=graph.getNextAdjvex(graph.getMatrix(), i, w)){

if(!isVisited[w]){

BFSFirstSearch(w);

}



}



}

public static void main(String[] args) {

System.out.println("图");

int vexNum=8;

String []vexNode={"V1","V2","V3","V4","V5","V6","V7","V8"};

int [][]matrix={{0,1,1,0,0,0,0,0},

{1,0,0,1,1,0,0,0},

{1,0,0,0,0,1,1,0},

{0,1,0,0,0,0,0,1},

{0,1,0,0,0,0,0,1},

{0,0,0,1,0,0,1,0},

{0,0,0,1,0,1,0,0},

{0,0,0,0,1,1,0,0}

};

Traverse bfs=new Traverse();

bfs.graph=new Graph(vexNum, vexNode, matrix);

for (int i=0;i<vexNum;i++){

bfs.isVisited[i]=false;

}

System.out.println("---------广度优先遍历---------");

bfs.boardFirstSearch();

for (int i=0;i<vexNum;i++){

bfs.isVisited[i]=false;

}

System.out.println("\r\n---------深度优先遍历---------");

bfs.BFSFirstSearch();

}

}

2 图的连通性和生成树

无向图

连通图:任意两个顶点可达

连通分量:无向图的极大连通子图

有向图

强连通图:任意两个顶点可达

强连通分量:极大强连通子图

生成树:一个连通图的生成树是一个极小连通子图,他包含图的所有顶点,但只有足以构成一棵树的n-1条边。添加一条边就形成环。生成树求解算法。

普里姆算法:

初始的U={v0},选择V-U各个节点到U={V0}的最短路径的节点{V0,V3},继续重复此过程,直到选择出n个节点。每次都选择一个最短的路径,那么生成树就是最小的。

package graph.traverse;


import java.util.HashSet;

import java.util.Set;


import graph.Graph;


public class MiniSpanTree {


// int [][]closeEdge,记录任意两个节点之间的权值,k代表起始节点的下标

public void miniTree(Graph graph, int k, CloseEdge[] closeEdge) {

int vexNum = graph.getVexNum();

// 带有权值的矩阵

int[][] matrix = graph.getMatrix();

closeEdge[k] = new CloseEdge();

// 1 目前U={k},求其他各个节点和U的节点之间的权值

for (int i = 0; i < vexNum; i++) {

if (i != k) {

closeEdge[i] = new CloseEdge();

closeEdge[i].lowcost = matrix[k][i];

closeEdge[i].adjvex = k;

}

}

for (CloseEdge is : closeEdge) {

if (is.lowcost == Integer.MAX_VALUE) {

System.out.print("∽ ");

} else {

System.out.print(is.lowcost + " ");

}

}

System.out.println();



Set U = new HashSet();

U.add(k);

//剩余n-1个节点

for (int i = 1; i < vexNum; i++) {

// 3 寻找U和V-U的节点权值的最小值


k = mininum(closeEdge, vexNum, U);

System.out.print("k="+k+" ");

U.add(k);

System.out.println(graph.getVexNode()[closeEdge[k].adjvex] + "-->" + graph.getVexNode()[k]);

closeEdge[k].lowcost = 0;

// 4 对U到U-V的各个节点的权值做一轮更新

for (int j = 0; j < vexNum; j++) {

if (matrix[k][j] < closeEdge[j].lowcost) {

closeEdge[j].lowcost = matrix[k][j];

closeEdge[j].adjvex = k;

}

}

for (CloseEdge is : closeEdge) {

if (is.lowcost == Integer.MAX_VALUE) {

System.out.print(" ∽ ");

} else {

System.out.print(is.lowcost + " ");

}

}

System.out.println();

}

}


private int mininum(CloseEdge[] closeEdge, int vexNum, Set U) {

// TODO Auto-generated method stub

int min = Integer.MAX_VALUE;

int index = 0;

for (int i = 1; i < vexNum; i++) {

// System.out.println(closeEdge[i]);

if (closeEdge[i].lowcost < min && closeEdge[i].lowcost != 0) {

min = closeEdge[i].lowcost;

index = i;

}

}

return index;


}


public static void main(String[] args) {

MiniSpanTree mst = new MiniSpanTree();

System.out.println("图");

int vexNum = 6;

int MAX = Integer.MAX_VALUE;

String[] vexNode = { "V1", "V2", "V3", "V4", "V5","v6"};

int[][] matrix = { { MAX, 6, 1, 5, MAX, MAX },

{ 6, MAX, 5, MAX, 3, MAX },

{ 1, 5, MAX, 5, 6, 4},

{ 5, MAX, 5, MAX, MAX, 2 },

{ MAX, 3, 6, MAX, MAX, 6 }, { MAX, MAX, 4, 2, 6, MAX }, };

Graph graph = new Graph(vexNum, vexNode, matrix);

CloseEdge[] closeEdge = new CloseEdge[vexNum];

mst.miniTree(graph, 0, closeEdge);

}


}

//V-U的节点到U的大小,随着节点的加入不断的进行更新

class CloseEdge {

int adjvex;

int lowcost;

}

3 拓扑排序

不存在环。算法:给定每个节点入度,把入度为0的节点入队列,然后,节点出对列,把与这个节点相连的节点的入度-1,如果,节点入度为0也入队列。对列不空,继续重复这个过程。
 

package graph.traverse;


import java.util.Stack;


import graph.Graph;


public class TopologicalSort {


public boolean topologic(Graph graph) {

int[][] matrix = graph.getMatrix();

int vexNum = graph.getVexNum();

int[] indegree = new int[vexNum];

// 求各个节点的入度

for (int i = 0; i < vexNum; i++) {

for (int j = 0; j < vexNum; j++) {

if (matrix[i][j] != 0) {

indegree[j]++;

}

}

}

// 把入度为零的节点全部入栈

Stack stack = new Stack();

for (int i = 0; i < vexNum; i++) {

if (indegree[i] == 0) {

stack.push(i);

System.out.print(graph.getVexNode()[i] + " ");

}

}

// 栈不空的时候,一直出栈,并把和出栈节点相邻的节点的入度--。如果,为零也入栈

int count = 0;

while (!stack.isEmpty()) {

int u = (int) stack.pop();

count++;

for (int w = graph.getFirstAdjvex(matrix, u); w >= 0; w = graph.getNextAdjvex(matrix, u, w)) {

if (--indegree[w] == 0) {

stack.push(w);

System.out.print(graph.getVexNode()[w] + " ");

}

}

}

if (count != graph.getVexNum()) {

return false;

}

return true;

}


public static void main(String[] args) {

int vexNum = 4;

String[] vexNode = { "V1", "V2", "V3", "V4" };

int[][] matrix = {

{ 0, 1, 1, 0 },

{ 0, 0, 0, 1 },

{ 0, 0, 0, 1 },

{ 0, 0, 0, 0 } };

Graph graph = new Graph(vexNum, vexNode, matrix);

TopologicalSort ts=new TopologicalSort();

ts.topologic(graph);


}


}

4 关键路径

关键路径就是消耗时间最长的那条路径,如果这个路径完成,那么其他的路径都已经完成。算法:从开始节点出发,计算出每个节点的最早的到达时间ve,ve是由它前边的最长路径决定的。从终止节点往回走,计算出每个节点的最晚的到达时间vl,vl的初始值都设为终点的最早到达时间,然后,从终点-路径长度就是该点的路径长度。

如果,最早到达时间和最晚到达时间大小相等,那么这个点肯定在关键的路径上,这个节点没有任何时间调整的可能。

package graph.traverse;


import java.util.Stack;


import graph.Graph;


public class CriticalPath {



private Stack T=new Stack();

//每个节点开始的最早的时间,前边的都执行完才能执行该节点,因此,该节点是前边最长的那条路径长度

private int [] ve;

private int [] vl;

public boolean topologic(Graph graph) {

int[][] matrix = graph.getMatrix();

int vexNum = graph.getVexNum();

int[] indegree = new int[vexNum];

ve=new int [vexNum];

for(int i=0;i<vexNum;i++){

ve[i]=0;

}

// 求各个节点的入度

for (int i = 0; i < vexNum; i++) {

for (int j = 0; j < vexNum; j++) {

if (matrix[i][j] != 0) {

indegree[j]++;

}

}

}

// 把入度为零的节点全部入栈

Stack stack = new Stack();

for (int i = 0; i < vexNum; i++) {

if (indegree[i] == 0) {

stack.push(i);

}

}

// 栈不空的时候,一直出栈,并把和出栈节点相邻的节点的入度--。如果,为零也入栈

int count = 0;

while (!stack.isEmpty()) {

int u = (int) stack.pop();

//System.out.print(graph.getVexNode()[u] + " ");

T.push(u);

count++;

for (int w = graph.getFirstAdjvex(matrix, u); w >= 0; w = graph.getNextAdjvex(matrix, u, w)) {

if (--indegree[w] == 0) {

stack.push(w);

}

if(ve[u]+matrix[u][w]>ve[w]){

ve[w]=ve[u]+matrix[u][w];

}

}

}

if (count<graph.getVexNum()) {

return false;

}

return true;

}



public void critical(Graph graph){

int[][] matrix = graph.getMatrix();

int vexNum = graph.getVexNum();

int[] indegree = new int[vexNum];

vl=new int [vexNum];

//初始化各个节点的最迟发生时间

if(!topologic(graph)){

return;

}



for(int i=0;i<vexNum;i++){

vl[i]=ve[vexNum-1];

}

int u,w;

while(!T.isEmpty()){



u=(int)T.pop();

for(w=graph.getReverseFirstAdjvex(matrix, u);w>=0;w=graph.getReverseNextAdjvex(matrix, u, w)){

//往前推,使其前驱事件能够满足所有的后驱实践,这个应该是能发生的越早就越早

if(vl[w]>vl[u]-matrix[w][u]){

vl[w]=vl[u]-matrix[w][u];

}



}

}

for(int i=0;i<graph.getVexNum();i++){

if(ve[i]==vl[i]){

System.out.println(graph.getVexNode()[i]+" ");

}

}

}



public static void main(String[] args) {

int vexNum = 6;

String[] vexNode = { "V1", "V2", "V3", "V4","V5","V6"};

int[][] matrix = {

{ 0, 3, 2, 0, 0, 0 },

{ 0, 0, 0, 2, 3, 0 },

{ 0, 0, 0, 4, 0, 3 },

{ 0, 0, 0, 0, 0, 2 },

{ 0, 0, 0, 0, 0, 1 },

{ 0, 0, 0, 0, 0, 0 }

};

Graph graph = new Graph(vexNum, vexNode, matrix);

CriticalPath cp=new CriticalPath();

//cp.topologic(graph);

cp.critical(graph);

}



}

最短路径

迪杰斯特拉算法(一个节点到所有节点的最短路径):贪婪算法,从一个节点出发,每次选一条最短的路径,这个最短的路径可能是(v,vk)或者是((v,vj),vk)

这个算法那网上有很多,就不在赘述。

弗洛伊德算法(任意两个节点之间的最短距离):每次以一个节点为桥,更新两个节点之间的最短距离

package graph.traverse;

import graph.Graph;

public class FlOYD {



public void shortPath(Graph graph){

int[][] matrix = graph.getMatrix();

int vexNum = graph.getVexNum();

int [][]D=new int [vexNum][vexNum];

boolean [][][]P=new boolean[vexNum][vexNum][vexNum];

//初始化

for(int i=0;i<vexNum;i++){

for(int j=0;j<vexNum;j++){

D[i][j]=matrix[i][j];

for(int u=0;u<vexNum;u++){

P[i][j][u]=false;

}

//记录i到j之间的路径

if(D[i][j]<Integer.MAX_VALUE){

P[i][j][i]=true;

P[i][j][j]=true;

}

}

}





//一个顶点一个顶点的矩阵中添加,不断的跟新矩阵

for(int u=0;u<vexNum;u++){

for(int v=0;v<vexNum;v++){

for(int w=0;w<vexNum;w++){

if(D[v][u]+D[u][w]<D[v][w]){

D[v][w]=D[v][u]+D[u][w];

//路径也要更新



}

}

}

for (int[] is : D) {

for (int i : is) {

System.out.print(i+" ");

}

System.out.println();



}

}

}

public static void main(String[] args) {

int vexNum = 3;

String[] vexNode = { "A", "B", "C"};

int MAX=Integer.MAX_VALUE;

int[][] matrix = {

{ 0, 4, 11},

{ 6, 0, 2},

{ 3, MAX, 0}

};

Graph graph = new Graph(vexNum, vexNode, matrix);

FlOYD f=new FlOYD();

f.shortPath(graph);

}

}