圖
圖的表示方式：鄰接矩陣、鄰接鏈表
1. 鄰接矩陣表示圖
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
// 圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)
public class Graph {
int maxVertexNum; // 最大頂點(diǎn)數(shù)
List<String> vertex; // 頂點(diǎn)表
int[][] edge; // 鄰接矩陣结蟋，邊表
int edgeNum; // 圖中當(dāng)前的邊數(shù)
boolean[] visited; // 頂點(diǎn)是否被訪問(wèn)
public Graph(int maxVertexNum) {
this.maxVertexNum = maxVertexNum;
vertex = new ArrayList<>(maxVertexNum);
edge = new int[maxVertexNum][maxVertexNum];
visited = new boolean[maxVertexNum];
}
// 顯示鄰接矩陣
public void display() {
for (int i = 0; i < edge.length; i++) {
System.out.println(Arrays.toString(edge[i]));
}
}
// 在圖中插入一個(gè)頂點(diǎn)
public void insertVertex(String vertex) {
this.vertex.add(vertex);
}
// 向圖中添加一條無(wú)向邊<vs, ve>蜒犯，其權(quán)值為weight
public void addEdge(int vs, int ve, int weight) {
edge[vs][ve] = weight;
edge[ve][vs] = weight;
edgeNum++;
}
// 獲取邊<vs, ve>的權(quán)值
public int getEdgeValue(int vs, int ve) {
return edge[vs][ve];
}
// 獲取頂點(diǎn)vertex的第一個(gè)鄰接點(diǎn)*
public int firstNeighbor(int vertex) {
for (int c = 0; c < this.vertex.size(); c++) {
if (edge[vertex][c] > 0)
return c;
}
return -1;
}
// 獲取vertex的除了exclude頂點(diǎn)的下一個(gè)鄰接點(diǎn)*
public int nextNeighbor(int vertex, int exclude) {
for (int c = exclude + 1; c < this.vertex.size(); c++) {
if (edge[vertex][c] > 0)
return c;
}
return -1;
}
// 對(duì)圖進(jìn)行深度優(yōu)先遍歷
public void dfsTraverse() {
int vertexNum = vertex.size();
// 初始化visited
for (int v = 0; v < vertexNum; v++)
visited[v] = false;
// 從0開(kāi)始逐個(gè)訪問(wèn)
for (int v = 0; v < vertexNum; v++)
if (!visited[v])
dfs(v);
}
// Depth First Search，深度優(yōu)先搜索，遞歸
private void dfs(int v) {
System.out.print(vertex.get(v) + " "); // 訪問(wèn)頂點(diǎn)v
visited[v] = true; // 標(biāo)記為已被訪問(wèn)
// adjacent為v的尚未被訪問(wèn)的鄰接頂點(diǎn)
for (int adjacent = firstNeighbor(v); adjacent >= 0; adjacent = nextNeighbor(v, adjacent)) {
// v的所有鄰接結(jié)點(diǎn)是從左到右按順序訪問(wèn)
if (!visited[adjacent])
dfs(adjacent);
}
}
// 借助棧渠鸽，非遞歸颈抚，從頂點(diǎn)v開(kāi)始深度優(yōu)先*
public void dfsTraverse(int v) {
LinkedList<Integer> stack = new LinkedList<>();
// 初始化visited
for (int i = 0; i < vertex.size(); i++)
visited[i] = false;
// 將v入棧踩衩，入棧一個(gè)就將其置為已被訪問(wèn)
stack.push(v);
visited[v] = true;
while (!stack.isEmpty()) {
// 出棧一個(gè)頂點(diǎn)并訪問(wèn)
v = stack.pop();
System.out.print(vertex.get(v) + " ");
// 將v的所有鄰接結(jié)點(diǎn)adjacent入棧
for (int adjacent = firstNeighbor(v); adjacent >= 0; adjacent = nextNeighbor(v, adjacent))
// 由于是棧，因此v的所有鄰接結(jié)點(diǎn)是從右到左逆序訪問(wèn)
if (!visited[adjacent]) { // 未進(jìn)過(guò)棧的頂點(diǎn)入棧
stack.push(adjacent);
visited[adjacent] = true;
}
}
}
// 對(duì)圖進(jìn)行廣度優(yōu)先遍歷
public void bfsTraverse() {
// 初始化visited
for (int i = 0; i < vertex.size(); i++)
visited[i] = false;
// 從0開(kāi)始逐個(gè)訪問(wèn)
for (int i = 0; i < vertex.size(); i++)
if (!visited[i])
bfs(i);
}
// Breadth First Search，廣度優(yōu)先搜索驱富，借助隊(duì)列锚赤，非遞歸*
private void bfs(int v) {
LinkedList<Integer> queue = new LinkedList<>();
// 訪問(wèn)v，并將其入隊(duì)
System.out.print(vertex.get(v) + " ");
visited[v] = true;
queue.addLast(v);
while (!queue.isEmpty()) {
// 頂點(diǎn)v出隊(duì)
v = queue.removeFirst();
// 訪問(wèn)v的所有鄰接點(diǎn)
for (int adjacent = firstNeighbor(v); adjacent >= 0; adjacent = nextNeighbor(v, adjacent))
if (!visited[adjacent]) {
// 訪問(wèn)adjacent褐鸥，并將其入隊(duì)
System.out.print(vertex.get(adjacent) + " ");
visited[adjacent] = true;
queue.addLast(adjacent);
}
}
}
}
// 測(cè)試
class GraphClient {
public static void main(String[] args) {
String[] vertex = {"1", "2", "3", "4", "5", "6", "7", "8"};
Graph graph = new Graph(vertex.length);
for (String s : vertex)
graph.insertVertex(s);
graph.addEdge(0, 1, 1); // 1-2
graph.addEdge(0, 2, 1); // 1-3
graph.addEdge(1, 3, 1); // 2-4
graph.addEdge(1, 4, 1); // 2-5
graph.addEdge(2, 5, 1); // 3-6
graph.addEdge(2, 6, 1); // 3-7
graph.addEdge(3, 7, 1); // 4-8
graph.addEdge(4, 7, 1); // 5-8
graph.addEdge(5, 6, 1); // 6-7
graph.display();
System.out.println("遞歸深度優(yōu)先：");
// 1 2 4 8 5 3 6 7
graph.dfsTraverse();
System.out.println("\n非遞歸深度優(yōu)先：");
// 1 3 7 6 2 5 8 4
graph.dfsTraverse(0);
System.out.println("\n非遞歸廣度優(yōu)先：");
// 1 2 3 4 5 6 7 8
graph.bfsTraverse();
}
}
2. 最小生成樹(shù)
最小生成樹(shù)可以用Prim(普里姆)算法或Kruskal(克魯斯卡爾)算法求出线脚。
Prim算法簡(jiǎn)述：
- 輸入：一個(gè)加權(quán)連通圖，其中頂點(diǎn)集合為V叫榕，邊集合為E
- 初始化：
酒贬，其中x為集合V中的任一節(jié)點(diǎn)，
翠霍，為空
- 重復(fù)下列操作锭吨，直到
：
- 在集合E中選取權(quán)值最小的邊
，其中u為集合
中的元素寒匙，而v不在
(如果存在有多條滿足前述條件即具有相同權(quán)值的邊，則可任意選取其中之一)
- 將v加入集合
中
- 在集合E中選取權(quán)值最小的邊
- 輸出：使用集合
Kruskal算法簡(jiǎn)述：
- 構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)考蕾，而邊集為空的子圖，若將該子圖中各個(gè)頂點(diǎn)看成是各棵樹(shù)上的根結(jié)點(diǎn)会宪，則它是一個(gè)含有n棵樹(shù)的一個(gè)森林肖卧。
- 從邊集E中選取一條權(quán)值最小的邊，若該條邊的兩個(gè)頂點(diǎn)分屬不同的樹(shù)掸鹅，則將其加入子圖塞帐；反之，若該條邊的兩個(gè)頂點(diǎn)已落在同一棵樹(shù)上巍沙，則不可取葵姥，而應(yīng)該取下一條權(quán)值最小的邊再試之。直至森林中只有一棵樹(shù)句携，也即子圖中含有n-1條邊為止榔幸。
import java.util.ArrayList;
import java.util.List;
class Edge {
String start;
String end;
int weight;
public Edge(String start, String end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
}
public class MinimumSpanningTree {
// prim求解最小生成樹(shù)，v表示從第v個(gè)頂點(diǎn)開(kāi)始生成
public static void prim(Graph graph, int v) {
// visited標(biāo)記結(jié)點(diǎn)是否被訪問(wèn)
boolean[] visited = new boolean[graph.maxVertexNum];
// 初始化visited
for (int i = 0; i < visited.length; i++)
visited[i] = false;
// 頂點(diǎn)v已被訪問(wèn)
visited[v] = true;
// vs和ve記錄兩個(gè)頂點(diǎn)的下標(biāo)
int vs = -1;
int ve = -1;
int minWeight = Integer.MAX_VALUE;
for (int k = 1; k < graph.maxVertexNum; k++) {
// 確定每一次生成的子圖和哪個(gè)結(jié)點(diǎn)的距離最近
for (int i = 0; i < graph.maxVertexNum; i++) { // 遍歷已經(jīng)訪問(wèn)過(guò)的結(jié)點(diǎn)
for (int j = 0; j < graph.maxVertexNum; j++) { // 遍歷所有沒(méi)有訪問(wèn)過(guò)的結(jié)點(diǎn)
// 如果是一個(gè)訪問(wèn)過(guò)的結(jié)點(diǎn)和一個(gè)沒(méi)有訪問(wèn)過(guò)的結(jié)點(diǎn)矮嫉，并且當(dāng)前邊的權(quán)值小于最小權(quán)值
if (visited[i] == true && visited[j] == false && graph.edge[i][j] < minWeight) {
minWeight = graph.edge[i][j];
vs = i;
ve = j;
}
}
}
System.out.println(graph.vertex.get(vs) + "->" + graph.vertex.get(ve) + ": " + minWeight);
visited[ve] = true;
minWeight = Integer.MAX_VALUE;
}
}
// kruskal求解最小生成樹(shù)
public static void kruskal(Graph graph, List<Edge> edges) {
// 保存已有最小生成樹(shù)中削咆，每個(gè)頂點(diǎn)所在樹(shù)的根的索引
int[] ends = new int[edges.size()];
// 對(duì)邊進(jìn)行排序，按照權(quán)值從小到大
edges.sort(((o1, o2) -> o1.weight - o2.weight));
// 遍歷邊集合蠢笋，將邊添加到最小生成樹(shù)中
// 判斷準(zhǔn)備加入的邊是否形成回路拨齐，即是同一棵樹(shù)的兩個(gè)頂點(diǎn)
for (int i = 0; i < edges.size(); i++) {
// 獲取第i條邊的起點(diǎn)索引
int start = graph.vertex.indexOf(edges.get(i).start);
// 獲取第i條邊的終點(diǎn)索引
int end = graph.vertex.indexOf(edges.get(i).end);
// 獲取起點(diǎn)所在樹(shù)的根索引
int startRoot = getRoot(ends, start);
// 獲取終點(diǎn)所在樹(shù)的根索引
int endRoot = getRoot(ends, end);
if (startRoot != endRoot) { // 不在同一棵樹(shù)
// 設(shè)置startRoot這棵樹(shù)在已有最小生成樹(shù)中的終點(diǎn)
ends[startRoot] = endRoot;
// 輸出這一條邊
System.out.println(edges.get(i).start + "--" + edges.get(i).end + ": " + edges.get(i).weight);
}
}
}
// (kruskal的難點(diǎn))返回頂點(diǎn)i所在樹(shù)的根的索引，ends數(shù)組記錄各個(gè)頂點(diǎn)所在樹(shù)的根的索引
private static int getRoot(int[] ends, int i) {
while (ends[i] != 0)
i = ends[i];
return i;
}
// 測(cè)試
public static void main(String[] args) {
String[] vertex = {"V1", "V2", "V3", "V4", "V5", "V6"};
// 將頂點(diǎn)加入到集合
List<String> list = new ArrayList<>();
for (String v : vertex)
list.add(v);
// max表示不連通
int max = Integer.MAX_VALUE;
// 初始化鄰接矩陣
int[][] edge = new int[][]{
{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}
};
// 將邊加入到集合
List<Edge> edges = new ArrayList<>();
for (int r = 0; r < edge.length; r++)
for (int c = r + 1; c < edge[r].length; c++)
if (edge[r][c] != max)
edges.add(new Edge(vertex[r], vertex[c], edge[r][c]));
// 創(chuàng)建一個(gè)圖挺尿，圖是自己定義的
Graph graph = new Graph(vertex.length);
graph.vertex = list;
graph.edge = edge;
graph.edgeNum = edges.size();
prim(graph, 0);
System.out.println("---------");
kruskal(graph, edges);
}
}
3. 最短路徑
最短路徑可以用Dijkstra(迪杰斯特拉)算法或Floyd(弗洛伊德)算法求出奏黑。
- Dijkstra算法可以求出指定頂點(diǎn)到其他各個(gè)頂點(diǎn)的最短路徑
- Floyd算法可以求出每一個(gè)頂點(diǎn)到其他各個(gè)頂點(diǎn)的最短路徑
Dijkstra算法過(guò)程：Dijkstra算法不適用于含有負(fù)權(quán)邊的圖
- 初始化：集合S初始為{0}，dist[]的初始值
编矾。
- 從頂點(diǎn)集合
中選出
熟史，滿足
，
出發(fā)的最短路徑的終點(diǎn)窄俏，令
蹂匹。
- 修改從
可達(dá)的最短路徑長(zhǎng)度：若
，則令
凹蜈。
- 重復(fù)2~3操作共n-1次限寞，直到所有的頂點(diǎn)都包含在S中。
- dist[]：記錄從源點(diǎn)
的初值為
履植。
- path[]：path[i]表示從源點(diǎn)到頂點(diǎn)i之間的最短路徑的前驅(qū)結(jié)點(diǎn)，在算法結(jié)束時(shí)悄晃，可根據(jù)其值追溯得到源點(diǎn)
的最短路徑玫霎。
Floyd算法過(guò)程：Floyd算法又稱為插點(diǎn)法，利用了動(dòng)態(tài)規(guī)劃的思想
- 從任意一條單邊路徑開(kāi)始妈橄。所有兩點(diǎn)之間的距離是邊的權(quán)庶近，如果兩點(diǎn)之間沒(méi)有邊相連，則權(quán)為無(wú)窮大眷蚓。
- 對(duì)于每一對(duì)頂點(diǎn)u和v鼻种，看看是否存在一個(gè)頂點(diǎn)w使得從u到w再到v比已知的路徑更短，如果存在則更新它沙热。
- 把圖用鄰接矩陣G表示出來(lái)叉钥，如果從
篙贸，d表示該路的長(zhǎng)度沼侣；否則
。定義一個(gè)矩陣D用來(lái)記錄所插入點(diǎn)的信息歉秫，
表示從
。把各個(gè)頂點(diǎn)插入圖中雁芙，比較插點(diǎn)后的距離與原來(lái)的距離轧膘，
，如果
的值變小兔甘，則
谎碍。在G中包含有兩點(diǎn)之間最短道路的信息，而在D中則包含了最短通路徑的信息洞焙。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
// Dijkstra算法的輔助數(shù)組類
class AuxiliaryArray {
// 記錄各個(gè)頂點(diǎn)是否訪問(wèn)過(guò)：1訪問(wèn)過(guò)蟆淀，0未訪問(wèn)
int[] visited;
// 記錄從源點(diǎn)到其他各頂點(diǎn)當(dāng)前的最短路徑長(zhǎng)度
int[] dist;
// path[i]表示從源點(diǎn)到頂點(diǎn)i之間的最短路徑的前驅(qū)結(jié)點(diǎn)
int[] path;
// 頂點(diǎn)數(shù)
int vertexNum;
// 源點(diǎn)的索引
int source;
public AuxiliaryArray(int vertexNum, int source) {
this.vertexNum = vertexNum;
this.source = source;
visited = new int[vertexNum];
dist = new int[vertexNum];
path = new int[vertexNum];
Arrays.fill(dist, Integer.MAX_VALUE / 2); // 初始化dist數(shù)組
visited[source] = 1; // 標(biāo)記源點(diǎn)已被訪問(wèn)
dist[source] = 0; // 設(shè)置源點(diǎn)到源點(diǎn)的距離為0
}
// 判斷頂點(diǎn)v是否被訪問(wèn)過(guò)
public boolean isVisited(int v) {
return visited[v] == 1;
}
// 返回從源點(diǎn)到頂點(diǎn)v當(dāng)前的最短路徑長(zhǎng)度
public int getDistance(int v) {
return dist[v];
}
// 更新源點(diǎn)到頂點(diǎn)v的距離為distance
public void updateDist(int v, int distance) {
dist[v] = distance;
}
// 更新頂點(diǎn)v的前驅(qū)結(jié)點(diǎn)為頂點(diǎn)prev
public void updatePath(int v, int prev) {
path[v] = prev;
}
// 選出vj拯啦，dist[j]為剩余結(jié)點(diǎn)i中dist[i]最小的
public int next() {
int minValue = Integer.MAX_VALUE / 2;
int minIndex = 0;
for (int i = 0; i < visited.length; i++) {
if (visited[i] == 0 && dist[i] < minValue) {
minValue = dist[i];
minIndex = i;
}
}
// 更新minIndex頂點(diǎn)被訪問(wèn)過(guò)
visited[minIndex] = 1;
return minIndex;
}
// 便于展示
public void display(List<String> vertex) {
System.out.println("visited: ");
for (int i = 0; i < visited.length; i++)
System.out.print(visited[i] + " ");
System.out.println("\npath: ");
for (int i = 0; i < path.length; i++)
System.out.print(path[i] + " ");
System.out.println("\ndist: ");
for (int i = 0; i < dist.length; i++)
System.out.print(dist[i] + " ");
System.out.println("\n源點(diǎn)" + vertex.get(source) + "到各頂點(diǎn)的最短路徑：");
for (int i = 0; i < dist.length; i++) {
if (dist[i] != Integer.MAX_VALUE / 2)
System.out.print(vertex.get(source) + "-" + dist[i] + "->" + vertex.get(i) + "\t");
else
System.out.print("MAX ");
}
}
}
public class ShortestPath {
// dijkstra更新輔助數(shù)組Dist和Path
private static void updateDistAndPath(Graph graph, AuxiliaryArray auxiliary, int j) {
// 遍歷鄰接矩陣的第j行
for (int k = 0; k < graph.edge[j].length; k++) {
// distance表示源點(diǎn)到頂點(diǎn)v的距離+源點(diǎn)到頂點(diǎn)j的距離
int distance = auxiliary.getDistance(j) + graph.edge[j][k];
// 如果頂點(diǎn)j沒(méi)有被訪問(wèn)過(guò)，并且distance小于源點(diǎn)到頂點(diǎn)j的距離熔任，就更新
if (!auxiliary.isVisited(k) && distance < auxiliary.getDistance(k)) {
// 更新頂點(diǎn)j的前驅(qū)結(jié)點(diǎn)為頂點(diǎn)v
auxiliary.updatePath(k, j);
// 更新源點(diǎn)到頂點(diǎn)j的距離為distance
auxiliary.updateDist(k, distance);
}
}
}
// Dijkstra算法求最短路徑
public static void dijkstra(Graph graph, AuxiliaryArray auxiliary, int source) {
updateDistAndPath(graph, auxiliary, source);
for (int j = 1; j < graph.vertex.size(); j++) {
// 獲取下一個(gè)訪問(wèn)頂點(diǎn)next
int next = auxiliary.next();
// 設(shè)置到next頂點(diǎn)的最短路徑和前驅(qū)
updateDistAndPath(graph, auxiliary, next);
}
}
// Floyd算法求最短路徑
public static void floyd(Graph graph, int[][] dist, int[][] path) {
// 初始化dist為鄰接矩陣
for (int r = 0; r < graph.maxVertexNum; r++)
for (int c = 0; c < graph.maxVertexNum; c++)
dist[r][c] = graph.edge[r][c];
// 初始化path
for (int i = 0; i < graph.maxVertexNum; i++)
// 初始時(shí)褒链，各個(gè)頂點(diǎn)到源點(diǎn)i的前驅(qū)默認(rèn)為i
Arrays.fill(path[i], i);
// Floyd求最短路徑過(guò)程
for (int k = 0; k < dist.length; k++) { // 中間頂點(diǎn)k
for (int i = 0; i < dist.length; i++) { // 從頂點(diǎn)i出發(fā)
for (int j = 0; j < dist.length; j++) { // 到達(dá)頂點(diǎn)j
// distance為路徑i-->k-->j的距離
int distance = dist[i][k] + dist[k][j];
// 如果i-->k-->j的距離小于i-->j的距離
if (distance < dist[i][j]) {
// 更新最短路徑
dist[i][j] = distance;
// 更新前驅(qū)
path[i][j] = path[k][j];
}
}
}
}
}
// 測(cè)試
public static void main(String[] args) {
String[] vertex = {"A", "B", "C", "D", "E", "F", "G"};
// 將頂點(diǎn)加入到集合
List<String> list = new ArrayList<>();
for (String v : vertex)
list.add(v);
// max表示不連通
int max = Integer.MAX_VALUE / 2;
// 初始化鄰接矩陣
int[][] edge = new int[][]{
{0, 5, 7, max, max, max, 2},
{5, 0, max, 9, max, max, 3},
{7, max, 0, max, 8, max, max},
{max, 9, max, 0, max, 4, max},
{max, max, 8, max, 0, 5, 4},
{max, max, max, 4, 5, 0, 6},
{2, 3, max, max, 4, 6, 0}
};
// 創(chuàng)建一個(gè)圖，圖是自己定義的
Graph graph = new Graph(vertex.length);
graph.vertex = list;
graph.edge = edge;
System.out.println("-----Dijkstra-----");
AuxiliaryArray auxiliary = new AuxiliaryArray(graph.maxVertexNum, 2);
dijkstra(graph, auxiliary, auxiliary.source);
auxiliary.display(graph.vertex);
System.out.println("\n-----Floyd-----");
int[][] dist = new int[graph.maxVertexNum][graph.maxVertexNum];
int[][] path = new int[graph.maxVertexNum][graph.maxVertexNum];
floyd(graph, dist, path);
// 遍歷dist和path
for (int r = 0; r < dist.length; r++) {
System.out.print("各個(gè)頂點(diǎn)到源點(diǎn)" + graph.vertex.get(r) + "的前驅(qū)：");
for (int c = 0; c < dist.length; c++)
System.out.print(vertex[path[r][c]] + " ");
System.out.println();
for (int c = 0; c < dist.length; c++)
System.out.print(vertex[r] + "-" + dist[r][c] + "->" + vertex[c] + "\t");
System.out.println();
}
}
}
