圖可以分為以下三種:
image.png
無向圖： 就行朋友關系一樣，你是我們的朋友，那么我也就是你的朋友；
有向圖：有向圖就像粉絲和偶像的關系，你是我的粉絲，我不一定是你的粉絲；
帶權圖：就像地鐵站各個站點之間的關系，不僅僅是相互連接，站與站之間還有距離的差距。帶權圖又可以分為無向帶權圖和有向帶權圖。
圖中的各個概念
圖中的元素我們稱之為頂點(vertex);頂點之間的連寫稱之為邊；對于無向圖來說，頂點連接的邊的個數(shù)稱之為度；對于有向圖來說，指向頂點的邊數(shù)稱為入度；從頂點出來的邊數(shù)稱為出度
圖的表示方法
圖有兩種表示方式：
鄰接矩陣法：用矩陣來存儲，如下圖所示，優(yōu)點就是定位簡單，因為數(shù)組支持直接下標索引；缺點就是浪費空間，對于無向圖有一半是沒用的，對于稀疏圖，好多空間閑置。
image.png
鄰接表法：鄰接表法如下，每個頂點所連接的頂點用鏈表連接起來。
image.png
圖的最短路徑查找
廣度優(yōu)先（BFS）搜索算法：顧名思義就是層層推進的搜索方式，先搜索離起點最近的頂點，然后依次往后搜索；因為是從近往遠搜索，所以最先找到的肯定是距離最近的
image.png
public void bfs(int start, int end){
if(start == end) return;
boolean[] visited = new boolean[v];
visited[start] = true;
int[] prev = new int[v];
for(int i = 0; i < v; i++){
prev[i] = -1;
}
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(start);
while(!queue.isEmpty()){
int current = queue.poll();
for(int i = 0; i < adj[current].size(); i++){
int next = adj[current].get(i);
if(visited[next] == true){
continue;
}
prev[next] = current;
visited[next] = true;
if(next == end){
print(prev, start, end);
return;
}
queue.offer(next);
}
}
}
深度優(yōu)先算法(DFS) 顧名思義就是一條分支走到底，遍歷完之后再向上回溯走下一個分支。
java代碼實現(xiàn)如下
public void dfs(int start, int end){
if(start == end) return;
boolean[] visited = new boolean[v];
int[] prev = new int[v];
for(int i = 0; i < v; i++){
prev[i] = -1;
}
Stack<Integer> stack = new Stack<Integer>();
visited[start] = true;
stack.push(start);
while(!stack.empty()){
int current = stack.pop();
for(int i = 0; i < adj[current].size(); i++){
if(visited[adj[current].get(i)] == true){
continue;
}
visited[adj[current].get(i)] = true;
prev[adj[current].get(i)] = current;
if(adj[current].get(i) == end){
print(prev, start, end);
return;
}
stack.push(adj[current].get(i));
}
}
}
private void print(int[] prev, int start, int end) {
int last = prev[end];
if(last != -1 && end != start){
print(prev, start, last);
}
System.out.print(" " + end);
}
