图可以分为以下三种:
image.png
无向图： 就行朋友关系一样，你是我们的朋友，那么我也就是你的朋友；
有向图：有向图就像粉丝和偶像的关系，你是我的粉丝，我不一定是你的粉丝；
带权图：就像地铁站各个站点之间的关系，不仅仅是相互连接，站与站之间还有距离的差距。带权图又可以分为无向带权图和有向带权图。
图中的各个概念
图中的元素我们称之为顶点(vertex);顶点之间的连写称之为边；对于无向图来说，顶点连接的边的个数称之为度；对于有向图来说，指向顶点的边数称为入度；从顶点出来的边数称为出度
图的表示方法
图有两种表示方式：
邻接矩阵法：用矩阵来存储，如下图所示，优点就是定位简单，因为数组支持直接下标索引；缺点就是浪费空间，对于无向图有一半是没用的，对于稀疏图，好多空间闲置。
image.png
邻接表法：邻接表法如下，每个顶点所连接的顶点用链表连接起来。
image.png
图的最短路径查找
广度优先（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);
}
}
}
深度优先算法(DFS) 顾名思义就是一条分支走到底，遍历完之后再向上回溯走下一个分支。
java代码实现如下
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);
}
