圖論基礎(chǔ)
1强岸、圖的定義
圖（Graph）是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G（V,E）掩宜，其中蔫骂，G表示一個圖，V是圖G中頂點的集合牺汤，E是圖G中邊的集合辽旋。
2、圖的基本性質(zhì)
線性表中我們把數(shù)據(jù)元素叫元素檐迟，樹中將數(shù)據(jù)元素叫節(jié)點补胚，在圖中數(shù)據(jù)元素，則稱之為頂點（Vertex）
線性表中可以沒有數(shù)據(jù)元素追迟，稱為空表溶其。樹中可以沒有節(jié)點，叫做空樹敦间。
線性表中瓶逃，相鄰的數(shù)據(jù)元素之間具有線性關(guān)系束铭，樹結(jié)構(gòu)中，相鄰兩層的節(jié)點具有層次關(guān)系厢绝，而圖中契沫，任意兩個頂點之間都有可能有關(guān)系，頂點之間的邏輯關(guān)系用邊來表示昔汉，邊集可以是空的懈万。
3、圖的基本概念
1.無向圖
若頂點v1到v2之間的邊沒有方向挤庇，則稱這條邊為無向邊（Edge）钞速，用無序偶對（v?, v??）來表示。
如果圖中任意兩個頂點之間的邊都是無向邊嫡秕，則稱該圖為無向圖（Undirected graphs）渴语。
重要：在無向圖中，如果任意兩個頂點之間都存在邊昆咽，則稱該圖為無向完全圖驾凶。
2.有向圖
用有序偶<v?, vj>來表示，vi稱為弧尾（Tail）掷酗，Vj稱為弧頭（Head）调违。如果圖中任意兩個頂點之間的邊都是有向邊，則稱該圖為有向圖（Directed graphs）泻轰。
在有向圖中技肩，如果任意兩個頂點之間都存在方向互為相反的兩條弧，則稱該圖為有向完全圖
3.圖的權(quán)
有些圖的邊或弧具有與它相關(guān)的數(shù)字浮声，這種與圖的邊或弧相關(guān)的數(shù)叫做權(quán)
4.連通圖
在無向圖 G 中虚婿，如果從頂點 v 到頂點 v'有路徑，則稱 v和v'是連通的泳挥。
如果對于圖中任意兩個頂點v?然痊、vj（E， vi和vj都是連通的屉符，則稱 G 是連通圖（Connected Graphs）剧浸。
5.度
無向圖頂點的邊數(shù)叫度，有向圖頂點的邊數(shù)叫出度和入度
4矗钟、圖的數(shù)據(jù)存儲結(jié)構(gòu)
-
鄰接矩陣：圖的鄰接矩陣（Adjacency Matrix）存儲方式是用兩個數(shù)組來表示圖唆香。一個一維數(shù)組存儲圖中頂點信息，一個二維數(shù)組（稱為鄰接矩陣）存儲圖中的邊或弧的信息吨艇。有以下性質(zhì)表示：
1.無向圖躬它， 2.有向圖， 3.帶權(quán)有向圖秸应， 4.鄰接矩陣的問題
-
鄰接表
1.無向圖虑凛， 2.有向圖， 3.帶權(quán)
5软啼、圖的遍歷
-
深度優(yōu)先遍歷（Depth Firsh Search)桑谍。
遍歷規(guī)則：不斷地沿著頂點的深度方向遍歷。頂點的深度方向是指它的鄰接點方向祸挪。
-
廣度優(yōu)先遍歷（Breadth First Search）
1.先訪問完當前頂點的所有鄰接點锣披。（應該看得出廣度的意思）
2.先訪問頂點的鄰接點先于后訪問頂點的鄰接點被訪問。
6贿条、代碼實現(xiàn)
import java.util.LinkedList;
/**
* author: bobo
* create time: 2018/12/22 10:24 PM
* email: jqbo84@163.com
*/
public class Graph {
//頂點集合
private int[] vertices;
//圖的邊的信息
private int[][] matrix;
private int verticesSize;
public static final int MAX_WEIGHT = Integer.MAX_VALUE;
private boolean[] isVisited;
public Graph() {
}
public Graph(int verticesSize) {
this.verticesSize = verticesSize;
this.vertices = new int[verticesSize];
this.matrix = new int[verticesSize][verticesSize];
this.isVisited = new boolean[verticesSize];
for (int i = 0; i < verticesSize; i++) {
vertices[i] = i;
}
}
/**
* 計算V1到V2的權(quán)度（路徑長度）
*/
public int getWeight(int v1, int v2) {
int weight = matrix[v1][v2];
return (weight == 0 ? 0 : (weight == MAX_WEIGHT ? -1 : weight));
}
/**
* 獲取頂點
*
* @return
*/
public int[] getVertices() {
return vertices;
}
/**
* 獲取圖的邊的信息數(shù)組
* @return
*/
public int[][] getMatrix() {
return matrix;
}
/**
* 計算出度, 橫向計算
*/
public int getOutDegree(int v) {
int count = 0;
for (int i = 0; i < verticesSize; i++) {
if (matrix[v][i] != 0 && matrix[v][i] != MAX_WEIGHT) {
count += 1;
}
}
return count;
}
/**
* 計算入度雹仿， 縱向計算
*/
public int getInDegree(int v) {
int count = 0;
for (int i = 0; i < verticesSize; i++) {
if (matrix[i][v] != 0 && matrix[i][v] != MAX_WEIGHT) {
count += 1;
}
}
return count;
}
/**
* 獲取第一個鄰接點
*/
public int getFirstNeightBor(int v){
for (int i = 0; i < verticesSize; i++) {
if(matrix[v][i] > 0 && matrix[v][i] != MAX_WEIGHT){
return i;
}
}
return -1;
}
/**
* 獲取到頂點 v 的鄰接點的index到下一個鄰接點
*/
public int getNextNeightBor(int v, int index){
for (int i = index + 1; i < verticesSize; i++) {
if(matrix[v][i] > 0 && matrix[v][i] != MAX_WEIGHT){
return i;
}
}
return -1;
}
/**
* 深度優(yōu)先(很像二叉樹的前序排序算法)
*/
public void dfs(){
for (int i = 0; i < verticesSize; i++) {
if(!isVisited[i]){
System.out.println("Visited Vertice = " + i);
dfs(i);
}
}
}
public void dfs(int i){
isVisited[i] = true;
int v = getFirstNeightBor(i);
while (v != -1) {
if(!isVisited[v]){
System.out.println("Visited Vertice = " + v);
dfs(v);
}
v = getNextNeightBor(i, v);
}
}
/**
* 廣度優(yōu)先（有點像二叉樹的第四種排序算法）
*/
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 = " + i);
bfs(i);
}
}
}
public void bfs(int i){
LinkedList<Integer> queue = new LinkedList<>();
//找到第一個鄰接點
int fn = getFirstNeightBor(i);
if(fn == -1){
return;
}
if(!isVisited[fn]){
isVisited[fn] = true;
System.out.println("visited vertice = " + fn);
queue.offer(fn);
}
//開始把后面的鄰接點都入隊
int next = getNextNeightBor(i, fn);
while (next != -1){
if(!isVisited[next]){
isVisited[next] = true;
System.out.println("visited vertice = " + next);
queue.offer(next);
}
next = getNextNeightBor(i, next);
}
//從隊列中取出來一個，重復之前的操作
while (!queue.isEmpty()){
int p = queue.poll();
bfs(p);
}
}
}
7整以、測試
@Test
public void testGraph(){
// Graph graph=new Graph(5);
// int[] a0=new int[]{0,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,6};
// int[] a1=new int[]{9,0,3,MAX_WEIGHT,MAX_WEIGHT};
// int[] a2=new int[]{2,MAX_WEIGHT,0,5,MAX_WEIGHT};
// int[] a3=new int[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,0,1};
// int[] a4=new int[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,0};
// graph.getMatrix()[0]=a0;
// graph.getMatrix()[1]=a1;
// graph.getMatrix()[2]=a2;
// graph.getMatrix()[3]=a3;
// graph.getMatrix()[4]=a4;
// System.out.println(graph.getInDegree(2));
// System.out.println(graph.getOutDegree(2));
Graph graph = new Graph(5);
int[] v0 = new int[]{0, 1, 1, MAX_WEIGHT, MAX_WEIGHT};
int[] v1 = new int[]{MAX_WEIGHT, 0, MAX_WEIGHT, 1, MAX_WEIGHT};
int[] v2 = new int[]{MAX_WEIGHT, MAX_WEIGHT, 0, MAX_WEIGHT, MAX_WEIGHT};
int[] v3 = new int[]{1, MAX_WEIGHT, MAX_WEIGHT, 0, MAX_WEIGHT};
int[] v4 = new int[]{MAX_WEIGHT, MAX_WEIGHT, 1, MAX_WEIGHT, 0};
graph.getMatrix()[0] = v0;
graph.getMatrix()[1] = v1;
graph.getMatrix()[2] = v2;
graph.getMatrix()[3] = v3;
graph.getMatrix()[4] = v4;
graph.dfs();
System.out.println("--------------------------------");
graph.bfs();
}
結(jié)果：
--------------- 入度出度 -----------------
1
2
--------------- 深度優(yōu)先 -----------------
Visited Vertice = 0
Visited Vertice = 1
Visited Vertice = 3
Visited Vertice = 2
Visited Vertice = 4
--------------- 廣度優(yōu)先 -----------------
visited vertice = 0
visited vertice = 1
visited vertice = 2
visited vertice = 3
visited vertice = 4
8胧辽、附測試圖
1.入度出度測試圖：
2.深度優(yōu)先、廣度優(yōu)先測試圖：
