目錄
圖的定義
圖的相關術語
圖的存盤結構
鄰接矩陣
鄰接表
無向圖的實作
圖的搜索
深度優先搜索（DFS）
廣度優先搜索（BFS）
圖的定義
圖是由一組頂點和一組能夠將兩個頂點相連的邊組成的，
特殊圖：
圖可以分為無向圖和有向圖，有向圖就是連接是有方向的，
圖的相關術語
度： 某個頂點的度就是依附于該頂點的邊的個數
環： 是一條至少含有一條邊且終點和起點相同的路徑
連通圖： 如果圖中任意一個頂點都存在一條路徑到達另外一個頂點
圖的存盤結構
要表示一幅圖，只需要表示清楚以下兩部分內容即可：
1.
圖中所有的頂點；
2.
所有連接頂點的邊；
常見的圖的存盤結構有兩種：鄰接矩陣和鄰接表
鄰接矩陣
1.
使用一個
V*V
的二維陣列
int[V][V] adj,
把索引的值看做是頂點；
2.
如果頂點
v
和頂點
w
相連，我們只需要將
adj[v][w]
和
adj[w][v]
的值設定為
1,
否則設定為
0
即可，
矩陣的橫縱坐標代表了頂點，中間的元素值代表是否連接，
缺點：記憶體占用空間較大
鄰接表
1.
使用一個大小為
V
的陣列
Queue[V] adj
，把索引看做是頂點；
2.
每個索引處
adj[v]
存盤了一個佇列，該佇列中存盤的是所有與該頂點相鄰的其他頂點，
無向圖的實作
無向圖的構建：
import java.util.LinkedList;
import java.util.Queue;
public class Graph {
private final int V; //頂點數量
private int E; //邊的數量
private Queue<Integer>[] adj;
public Graph(int V){
//初始化
this.V = V;
this.E = 0;
this.adj = new LinkedList[V];
for(int i=0; i<adj.length; i++){
adj[i] = new LinkedList();
}
}
public int V(){
return V;
}
public int E(){
return E;
}
public void addEdge(int v, int w){
// 無向圖
adj[v].offer(w);
adj[w].offer(v);
// 邊的數量+1
E++;
}
public Queue<Integer> adj(int v){
return adj[v];
}
}
圖的搜索
深度優先搜索（DFS）
先找子結點，再找兄弟結點，
（搜索過的點不用再搜索）
public class DFS {
private boolean[] marked; //陣列索引代表頂點，表示當前頂點是否已經被搜索
private int count; // 記錄有多少個頂點與頂點s相通
public DFS(Graph G, int s){
//初始化
this.marked = new boolean[G.V()];
this.count = 0;
dfs(G,s);
}
private void dfs(Graph G, int V){
// 把V頂點標識為已經搜索
marked[V] = true;
for(Integer w: G.adj(V)){
//判斷當前w頂點有沒有被搜索過
if(!marked[w]){
dfs(G,w);
}
}
count++; // 相通頂點數量+1
}
//判斷W頂點是否和S頂點相通
private boolean marked(int w){
return marked[w]; //被搜索過則意味著相通
}
//獲取與頂點s相同的所有頂點的總數
public int count(){
return count;
}
}廣度優先搜索（BFS）
先找兄弟結點，再找子結點，
（搜索過的點不用再搜索）
層序遍歷其實就是廣度優先搜索，
import java.util.LinkedList;
import java.util.Queue;
public class BFS {
private boolean[] marked;
private int count;
private Queue<Integer> waitSearch; //輔助佇列
public BFS(Graph G, int s){
this.marked = new boolean[G.V()];
this.count = 0;
this.waitSearch = new LinkedList<Integer>();
bfs(G,s);
}
private void bfs(Graph G, int v){
marked[v] = true;
waitSearch.offer(v);
while(!waitSearch.isEmpty()){
Integer wait = waitSearch.remove();
//遍歷wait頂點的鄰接表
for(Integer w: G.adj(wait)){
if(!marked[w]){
bfs(G, w);
}
}
}
count ++;
}
public boolean marked(int w){
return marked[w];
}
public int count(){
return count;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/290586.html
標籤：其他
上一篇：都2021年了，還在問網路安全怎么入門，氣得我當場腦血栓發作
下一篇：Python程式員愛情詩