Datawhale 系列資料結構
Task6 圖
圖，基本概念：
1.鄰接：如果兩個定點同一條邊連接配接，就成這兩個定點是鄰接的。
2.路徑：路徑是邊的序列，比如從頂點B到定點J的路徑為BAEJ，當然還有别的路徑BCDJ。
3.連通圖和非連通圖：如果至少一條路徑可以連接配接所有的定點，這個圖稱為聯通圖。如果存在從某個定點不能到達另外一個定點，則稱為非聯通的。
4.有向圖和無向圖：如果圖中的邊沒有方向，可以從任意一邊到達另一邊，則稱為無向圖。例如從A城市可以到B城市，也可以從B城市到A城市，這叫做無向圖。但是如果隻能從A城市駛向B城市的圖，稱為有向圖。
5.有權圖和無權圖：圖中的邊呗賦予一個權值，全職是一個數字，代表兩個定點間的實體距離，或者從一個頂點到另一個頂點時間，這種圖被稱作有權圖。反之邊沒有賦權的圖被稱為無權圖
6.1實作有向圖、無向圖、有權圖、無權圖的鄰接矩陣和鄰接表表示方法
//圖所需要的，節點，隊列，棧
//節點
public class Vertex {
public char label;
public boolean wasVisited;
public Vertex(char label){
this.label = label;
wasVisited = false;
}
}
//隊列
public class QueueX {
private final int SIZE = 20;
private int[] queArray;
private int front;
private int rear;
public QueueX(){
queArray = new int[SIZE];
front = 0;
rear = -1;
}
public void insert(int j) {
if(rear == SIZE-1) {
rear = -1;
}
queArray[++rear] = j;
}
public int remove() {
int temp = queArray[front++];
if(front == SIZE) {
front = 0;
}
return temp;
}
public boolean isEmpty() {
return (rear+1 == front || front+SIZE-1 == rear);
}
}
//棧
public class StackX {
private final int SIZE = 20;
private int [] st;
private int top;
public StackX(){
st = new int[SIZE];
top=-1;
}
public void push(int j){
st[++top] = j;
}
public int pop(){
return st[top--];
}
public int peek(){
return st[top];
}
public boolean isEmpty(){
return (top == -1);
}
} //無權無向圖，用鄰接表表示，
public class Graph {
private final int MAX_VERTS = 20;//表示定點的個數
private Vertex vertexList[];//用來存儲定點的數組
private int adjMat[][];//用鄰接矩陣來存儲邊，數組元素0表示沒有邊界，1表示有邊界
private int nVerts;
private StackX theStack;//用棧實作深度優先搜多
private QueueX queue;
public Graph(){
vertexList = new Vertex[MAX_VERTS];
adjMat = new int[MAX_VERTS][MAX_VERTS];
nVerts = 0;//初始化頂點個數為0
//初始化鄰接矩陣所有元素都為0，即所有頂點都沒有邊
for(int i = 0; i < MAX_VERTS; i++) {
for(int j = 0; j < MAX_VERTS; j++) {
adjMat[i][j] = 0;
}
}
theStack = new StackX();
queue = new QueueX();
}
//将頂點添加到數組中，是否通路标志置為wasVisited=false（未通路）
public void addVertex(char lab){
vertexList[nVerts++]=new Vertex(lab);
}
//注意用臨界矩陣表示邊，是對稱的，兩部分都要指派
public void addEdge(int start,int end){
adjMat[start][end]=1;
adjMat[end][start]=1;
}
//列印某個頂點表示的值
public void displayVertex(int v){
System.out.println(vertexList[v].label);
}
/**深度優先搜尋算法
* 1.用peek()方法檢查棧頂的頂點
* 2.用getAdjUnvisitedVertex()方法找到目前棧頂鄰接且未被通路的頂點
* 3.第二步方法值不等-1則找到下一個未通路的鄰接頂點，通路這個頂點，并入棧
* 如果第二步方法傳回值等于-1,則沒有找到，出棧
*/
public void depthFirstSearch(){
vertexList[0].wasVisited = true;//通路之後标記未true
displayVertex(0);
theStack.push(0);
while(!theStack.isEmpty()){
int v=getAdjUnvisitedVertex(theStack.peek());
if(v==-1){
theStack.pop();
}else{
vertexList[v].wasVisited = true;
displayVertex(v);
theStack.push(v);
}
}
for(int i=0;i<nVerts;i++){
vertexList[i].wasVisited=false;
}
}
//找到與某一點鄰接且未被通路的頂點
public int getAdjUnvisitedVertex(int v){
for(int i=0;i<nVerts;i++){
if(adjMat[v][i]==1 && vertexList[i].wasVisited == false){
return i;
}
}
return -1;
}
/**廣度優先搜尋算法：
* 1.用remove()方法檢查棧頂的頂點
* 2.試圖找到這個頂點還未通路的鄰接點
* 3.如果沒有找到，該頂點出列
* 4.如果找到這樣的頂點，通路這個頂點，并把它放入隊列中
*/
public void breadthFirstSearch(){
vertexList[0].wasVisited = true;
displayVertex(0);
queue.insert(0);
int v2;
while(!queue.isEmpty()){
int v1=queue.remove();
while((v2=getAdjUnvisitedVertex(v1))!=-1){
vertexList[v2].wasVisited = true;
displayVertex(v2);
queue.insert(v2);
}
}
for(int i=0;i<nVerts;i++){
vertexList[i].wasVisited=false;
}
}
} //最小生成樹
/**基于深度優先搜尋找到最小生成樹
*這裡是指，用最少的邊連接配接所有頂點。對于一組頂點，可能有多種最小生成樹，但是最小生成樹的邊的數量E總是比頂點V的數量小1，即：V = E+1
*/
public void mst(){
vertexList[0].wasVisited = true;
theStack.push(0);
while(!theStack.isEmpty()){
int currentVertex = theStack.peek();
int v = getAdjUnvisitedVertex(currentVertex);
if(v == -1){
theStack.pop();
}else{
vertexList[v].wasVisited = true;
theStack.push(v);
displayVertex(currentVertex);
displayVertex(v);
System.out.print(" ");
}
}
//搜尋完畢，初始化，以便于下次搜尋
for(int i = 0; i < nVerts; i++) {
vertexList[i].wasVisited = false;
}
} 6.2實作圖的深度優先搜尋、廣度優先搜尋
//這塊參考6.1中代碼 6.3.1 實作DijKstra算法
DijKstra算法思想：
互補松弛條件：
設标量d1,d2,...,dN滿足
dj<=di+aij,(i,j)屬于A， 且P是以i1為起點ik為終點的路，如果，
dj=di+aij，對P的所有邊（i,j） 成立，那麼P是從i到ik的最短路。其中，滿足上面兩式的被稱為最短路問題松弛條件。
1，令G=（V,E）為一個帶權無向圖。G中若有兩個相鄰的節點，i，j。aij為節點i到j的權值，在本算法可以了解為距離。每個節點鬥魚一個值di(節點标記)表示其從起點到它的某條路的距離
2，算法儲是有個數組V用于存儲未通路的節點清單，我們稱為候選清單。標明節點1為起始節點。開始時，節點1的d1=0,其他節點di=無窮大，V為所有節點。初始化條件後，然後開始疊代算法，指導B為空集時停止。具體疊代步驟如下：
将d值最小的節點di從候選清單中移除。（本例中V的資料結構采用的是優先隊列實作最小值出列，最好使用斐波那契數列？）對于該節點為期待你的每一條邊，不包括移除V的節點，(i,j)屬于A，若dj>di+dj（違反松弛條件）
/**DijKstra算法
*這裡使用帶權無向圖，彌補6.1中知識
*/
public class Vertex implements Comparable<Vertex>{
/**
* 節點名稱(A,B,C,D)
*/
private String name;
/**
* 最短路徑長度
*/
private int path;
/**
* 節點是否已經出列(是否已經處理完畢)
*/
private boolean isMarked;
public Vertex(String name){
this.name = name;
this.path = Integer.MAX_VALUE; //初始設定為無窮大
this.setMarked(false);
}
public Vertex(String name, int path){
this.name = name;
this.path = path;
this.setMarked(false);
}
@Override
public int compareTo(Vertex o) {
return o.path > path?-1:1;
}
}
public class Vertex implements Comparable<Vertex>{
/**
* 節點名稱(A,B,C,D)
*/
private String name;
/**
* 最短路徑長度
*/
private int path;
/**
* 節點是否已經出列(是否已經處理完畢)
*/
private boolean isMarked;
public Vertex(String name){
this.name = name;
this.path = Integer.MAX_VALUE; //初始設定為無窮大
this.setMarked(false);
}
public Vertex(String name, int path){
this.name = name;
this.path = path;
this.setMarked(false);
}
@Override
public int compareTo(Vertex o) {
return o.path > path?-1:1;
}
}
public class Graph {
/*
* 頂點
*/
private List<Vertex> vertexs;
/*
* 邊
*/
private int[][] edges;
/*
* 沒有通路的頂點
*/
private Queue<Vertex> unVisited;
public Graph(List<Vertex> vertexs, int[][] edges) {
this.vertexs = vertexs;
this.edges = edges;
initUnVisited();
}
/*
* 搜尋各頂點最短路徑
*/
public void search(){
while(!unVisited.isEmpty()){
Vertex vertex = unVisited.element();
//頂點已經計算出最短路徑，設定為"已通路"
vertex.setMarked(true);
//擷取所有"未通路"的鄰居
List<Vertex> neighbors = getNeighbors(vertex);
//更新鄰居的最短路徑
updatesDistance(vertex, neighbors);
pop();
}
System.out.println("search over");
}
/*
* 更新所有鄰居的最短路徑
*/
private void updatesDistance(Vertex vertex, List<Vertex> neighbors){
for(Vertex neighbor: neighbors){
updateDistance(vertex, neighbor);
}
}
/*
* 更新鄰居的最短路徑
*/
private void updateDistance(Vertex vertex, Vertex neighbor){
int distance = getDistance(vertex, neighbor) + vertex.getPath();
if(distance < neighbor.getPath()){
neighbor.setPath(distance);
}
}
/*
* 初始化未通路頂點集合
*/
private void initUnVisited() {
unVisited = new PriorityQueue<Vertex>();
for (Vertex v : vertexs) {
unVisited.add(v);
}
}
/*
* 從未通路頂點集合中删除已找到最短路徑的節點
*/
private void pop() {
unVisited.poll();
}
/*
* 擷取頂點到目标頂點的距離
*/
private int getDistance(Vertex source, Vertex destination) {
int sourceIndex = vertexs.indexOf(source);
int destIndex = vertexs.indexOf(destination);
return edges[sourceIndex][destIndex];
}
/*
* 擷取頂點所有(未通路的)鄰居
*/
private List<Vertex> getNeighbors(Vertex v) {
List<Vertex> neighbors = new ArrayList<Vertex>();
int position = vertexs.indexOf(v);
Vertex neighbor = null;
int distance;
for (int i = 0; i < vertexs.size(); i++) {
if (i == position) {
//頂點本身，跳過
continue;
}
distance = edges[position][i]; //到所有頂點的距離
if (distance < Integer.MAX_VALUE) {
//是鄰居(有路徑可達)
neighbor = getVertex(i);
if (!neighbor.isMarked()) {
//如果鄰居沒有通路過，則加入list;
neighbors.add(neighbor);
}
}
}
return neighbors;
}
/*
* 根據頂點位置擷取頂點
*/
private Vertex getVertex(int index) {
return vertexs.get(index);
}
/*
* 列印圖
*/
public void printGraph() {
int verNums = vertexs.size();
for (int row = 0; row < verNums; row++) {
for (int col = 0; col < verNums; col++) {
if(Integer.MAX_VALUE == edges[row][col]){
System.out.print("X");
System.out.print(" ");
continue;
}
System.out.print(edges[row][col]);
System.out.print(" ");
}
System.out.println();
}
}
}
6.3.2 A* 算法
public class AstarPathFind {
// 前四個是上下左右，後四個是斜角
public final static int[] dx = { 0, -1, 0, 1, -1, -1, 1, 1 };
public final static int[] dy = { -1, 0, 1, 0, 1, -1, -1, 1 };
// 最外圈都是1表示不可通過
final static public int[][] map = {
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } };
public static void main(String[] args) {
// TODO Auto-generated method stub
Point start = new Point(1, 1);
Point end = new Point(10, 13);
/*
* 第一個問題：起點FGH需要初始化嗎？
* 看參考資料的圖檔發現不需要
*/
Stack<Point> stack = printPath(start, end);
if(null==stack) {
System.out.println("不可達");
}else {
while(!stack.isEmpty()) {
//輸出(1,2)這樣的形勢需要重寫toString
System.out.print(stack.pop()+" -> ");
}
System.out.println();
}
}
public static Stack<Point> printPath(Point start, Point end) {
/*
* 不用PriorityQueue是因為必須取出存在的元素
*/
ArrayList<Point> openTable = new ArrayList<Point>();
ArrayList<Point> closeTable = new ArrayList<Point>();
openTable .clear();
closeTable.clear();
Stack<Point> pathStack = new Stack<Point>();
start.parent = null;
//該點起到轉換作用，就是目前擴充點
Point currentPoint = new Point(start.x, start.y);
//closeTable.add(currentPoint);
boolean flag = true;
while(flag) {
for (int i = 0; i < 8; i++) {
int fx = currentPoint.x + dx[i];
int fy = currentPoint.y + dy[i];
Point tempPoint = new Point(fx,fy);
if (map[fx][fy] == 1) {
// 由于邊界都是1中間障礙物也是1，，這樣不必考慮越界和障礙點擴充問題
//如果不設定邊界那麼fx >=map.length &&fy>=map[0].length判斷越界問題
continue;
} else {
if(end.equals(tempPoint)) {
flag = false;
//不是tempPoint，他倆都一樣了此時
end.parent = currentPoint;
break;
}
if(i<4) {
tempPoint.G = currentPoint.G + 10;
}else {
tempPoint.G = currentPoint.G + 14;
}
tempPoint.H = Point.getDis(tempPoint,end);
tempPoint.F = tempPoint.G + tempPoint.H;
//因為重寫了equals方法，是以這裡包含隻是按equals相等包含
//這一點是使用java封裝好類的關鍵
if(openTable.contains(tempPoint)) {
int pos = openTable.indexOf(tempPoint );
Point temp = openTable.get(pos);
if(temp.F > tempPoint.F) {
openTable.remove(pos);
openTable.add(tempPoint);
tempPoint.parent = currentPoint;
}
}else if(closeTable.contains(tempPoint)){
int pos = closeTable.indexOf(tempPoint );
Point temp = closeTable.get(pos);
if(temp.F > tempPoint.F) {
closeTable.remove(pos);
openTable.add(tempPoint);
tempPoint.parent = currentPoint;
}
}else {
openTable.add(tempPoint);
tempPoint.parent = currentPoint;
}
}
}//end for
if(openTable.isEmpty()) {
return null;
}//無路徑
if(false==flag) {
break;
}//找到路徑
openTable.remove(currentPoint);
closeTable.add(currentPoint);
Collections.sort(openTable);
currentPoint = openTable.get(0);
}//end while
Point node = end;
while(node.parent!=null) {
pathStack.push(node);
node = node.parent;
}
return pathStack;
}
}
class Point implements Comparable<Point>{
int x;
int y;
Point parent;
int F, G, H;
public Point(int x, int y) {
super();
this.x = x;
this.y = y;
this.F = 0;
this.G = 0;
this.H = 0;
}
@Override
public int compareTo(Point o) {
// TODO Auto-generated method stub
return this.F - o.F;
}
@Override
public boolean equals(Object obj) {
Point point = (Point) obj;
if (point.x == this.x && point.y == this.y)
return true;
return false;
}
public static int getDis(Point p1, Point p2) {
int dis = Math.abs(p1.x - p2.x) * 10 + Math.abs(p1.y - p2.y) * 10;
return dis;
}
@Override
public String toString() {
return "(" + this.x + "," + this.y + ")";
}
} 6.4實作拓撲排序的 Kahn 算法、DFS 算法
拓撲排序是對有向無圈圖的頂點的一種排序，使得如果存在一條從vi到vj的路徑，那麼在拓撲排序中，vj就出現在vi的後面。
拓撲圖中，不能出現圈，如果有圈，那麼就沒有意義。
一個有向圖能被拓撲排序的充要條件就是它是一個有向無環圖。
偏序：在有向圖中兩個頂點之間不存在環路，至于連通與否，是無所謂的。是以，有向無環圖必然是滿足偏序關系的。
全序：在偏序的基礎之上，有向無環圖中的任意一對頂點還需要有明确的關系，反應在圖中，就是單向連通的關系。（不能雙向連通，否則就是環）
// Kahn 算法
public class KahnTopological
{
private List<Integer> result; // 用來存儲結果集
private Queue<Integer> setOfZeroIndegree; // 用來存儲入度為0的頂點
private int[] indegrees; // 記錄每個頂點目前的入度
private int edges;
private Digraph di;
public KahnTopological(Digraph di)
{
this.di = di;
this.edges = di.getE();
this.indegrees = new int[di.getV()];
this.result = new ArrayList<Integer>();
this.setOfZeroIndegree = new LinkedList<Integer>();
// 對入度為0的集合進行初始化
Iterable<Integer>[] adjs = di.getAdj();
for(int i = 0; i < adjs.length; i++)
{
// 對每一條邊 v -> w
for(int w : adjs[i])
{
indegrees[w]++;
}
}
for(int i = 0; i < indegrees.length; i++)
{
if(0 == indegrees[i])
{
setOfZeroIndegree.enqueue(i);
}
}
process();
}
private void process()
{
while(!setOfZeroIndegree.isEmpty())
{
int v = setOfZeroIndegree.dequeue();
// 将目前頂點添加到結果集中
result.add(v);
// 周遊由v引出的所有邊
for(int w : di.adj(v))
{
// 将該邊從圖中移除，通過減少邊的數量來表示
edges--;
if(0 == --indegrees[w]) // 如果入度為0，那麼加入入度為0的集合
{
setOfZeroIndegree.enqueue(w);
}
}
}
// 如果此時圖中還存在邊，那麼說明圖中含有環路
if(0 != edges)
{
throw new IllegalArgumentException("Has Cycle !");
}
}
public Iterable<Integer> getResult()
{
return result;
}
}
//DFS算法
public class DirectedDepthFirstOrder
{
// visited數組，DFS實作需要用到
private boolean[] visited;
// 使用棧來儲存最後的結果
private Stack<Integer> reversePost;
/**
* Topological Sorting Constructor
*/
public DirectedDepthFirstOrder(Digraph di, boolean detectCycle)
{
// 這裡的DirectedDepthFirstCycleDetection是一個用于檢測有向圖中是否存在環路的類
DirectedDepthFirstCycleDetection detect = new DirectedDepthFirstCycleDetection(
di);
if (detectCycle && detect.hasCycle())
throw new IllegalArgumentException("Has cycle");
this.visited = new boolean[di.getV()];
this.reversePost = new Stack<Integer>();
for (int i = 0; i < di.getV(); i++)
{
if (!visited[i])
{
dfs(di, i);
}
}
}
private void dfs(Digraph di, int v)
{
visited[v] = true;
for (int w : di.adj(v))
{
if (!visited[w])
{
dfs(di, w);
}
}
// 在即将退出dfs方法的時候，将目前頂點添加到結果集中
reversePost.push(v);
}
public Iterable<Integer> getReversePost()
{
return reversePost;
}
} 6.5Number of Islands（島嶼的個數）
class Solution {
public int numIslands(char[][] grid) {
int count=0;
for(int x=0;x<grid.length;x++)
for(int y =0;y<grid[0].length;y++) {
if( grid[x][y] =='1') {
clear(grid,x,y);
++count;
}
}
return count;
}
public void clear(char[][] grid,int x,int y) {
grid[x][y]=0;
if(x+1<grid.length&& grid[x+1][y]=='1')clear(grid,x+1,y);
if(x-1>=0&& grid[x-1][y]=='1')clear(grid,x-1,y);
if(y+1<grid[0].length&& grid[x][y+1]=='1')clear(grid,x,y+1);
if(y-1>=0&& grid[x][y-1]=='1')clear(grid,x,y-1);
}
} 6.6Valid Sudoku（有效的數獨）
class Solution {
public boolean isValidSudoku(char[][] board) {
boolean[] rowFlags = new boolean[9];
boolean[] colFlags = new boolean[9];
boolean[] squareFlags = new boolean[9];
for (int i = 0; i < 9; i++) {
Arrays.fill(rowFlags, false);
Arrays.fill(colFlags, false);
Arrays.fill(squareFlags, false);
for (int j = 0; j < 9; j++) {
// 行數獨
char cell = board[i][j];
if (!isCellValid(rowFlags, cell)) {
return false;
}
// 列數獨
cell = board[j][i];
if (!isCellValid(colFlags, cell)) {
return false;
}
// 3*3 方格數獨
int row = (j / 3) + ((i / 3) * 3);
int col = (j % 3) + ((i % 3) * 3);
cell = board[row][col];
if (!isCellValid(squareFlags, cell)) {
return false;
}
}
}
return true;
}
//如果之前出現過，就return false。
public boolean isCellValid(boolean[] flags, char cell) {
if (cell == '.') {
return true;
}
int value = cell - 49;
if (flags[value]) {
return false;
}
flags[value] = true;
return true;
}
} ![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)