【笔记】简单入门--图论
本帖最后由 hack_hu 于 2019-4-16 09:15 编辑# 数据结构中的图是什么？
文章内容来自于对**王争**老师[《数据结构与算法之美》](https://time.geekbang.org/column/article/70537)栏的学习整理。
**图**，通常用来表示复杂的关系，一对一、一对多或是多对多。
根据根据图中数据的对应关系可分为：
「**无向图**」，即 A 关联 B 时，B 同时关联 A。例：微信中当 A 是 B 好友时，B 一定也是 A 的好友（新版本中已支持双向删除好友）。这种关联是双向的。
「**有向图**」，即 A 关联 B 时，B 未必关联 A。例：微博中粉丝与博主的关系，粉丝关注了博主，但是博主未必关注了每一个粉丝。这种关联性是单向的。
「**带权图**」，除了表示 A 与 B 是否关联外还表示这种关联度的权重。例如：QQ 空间的好友亲密度。在基本的关联度上附加了其他属性，表示更为复杂的关系。
图中的每一个元素被称为：**顶点** 。顶点之间表示联系的被称为 **边**。而顶点所关联的顶点数被称为 **度**。
在有向图中，顶点 A 所指向的顶点数被称为 **出度**，而所有指向 A 的顶点数之和被称为顶点 A 的 **入度**。
# 表示方式
**邻接矩阵法**。即将图中 N 个定点的关系用 N*N 个点组成的表示彼此之间的关联关系
**邻接矩阵法**。通过 **数组** 的方式来表示图中各个顶点所对应的关系。
优点：可以通过下标快速获取图中两个顶点所对应的关系。
缺点：在 **稀疏图** 中会浪费大量的存储空间。（稀疏图：有联点远小于矩阵所能表示的点数，即矩阵中非 0 点数占矩阵的比例）
```java
class ArrayGraph // 数组表示无向表
{
private int[][] graph; // 矩阵表
public ArrayGraph(int n) // N 代表顶点数
{
graph = new int;
}
public void add(int a,int b) // a,b 代表关联的两个顶点
{
graph=1;
graph=1;
}
}
```
**邻接表法**。通过 **链表** 存储每一个顶点的 **出度** 信息。
优点，对于 **稀疏图** 减少了空间消耗。
缺点，对于 **浓密图** 数据的访问更慢。
```java
class ListGrapg{ // 邻接表法表示图
private LinkedList<Integer>[] graph;
public ListGrapg(int n){ // n 代表图的顶点数
graph = new LinkedList;
for(int i=0;i<n;i++)
{
graph = new LinkedList<>();
}
}
public void addLink(int a,int b){ // a,b 代表无向表顶点
graph.add(b);
graph.add(a);
}
}
```
# 图的搜索
## 广度优先遍历 BFS
**广度优先遍历** （Breath-First-Search）是图的搜索中最常用的遍历方式之一，常用于 **求最短路径**。
思路：
把图中的任意顶点看做一棵独立的「树」，顶点直接关联的顶点就是树的第二层，以此类推。在查找顶点与另一顶点的最短路劲其实就是从树的根节点依序向下遍历。
```java
public void bfs(int source,int target) // source 为搜索源， target 为搜索目标
{
if(source==target)
return ; // 若查找源即为查找目标则直接返回
boolean[] visted = new boolean; // visted 数组表示当前层是否遍历，若已遍历则设置为 true
visted = true;
Queue<Integer> queue = new LinkedList<>(); // 定义一个数据类型为整数的链表队列，将每次遍历的层加入队列
queue.add(source);
int[] pre = new int; // 定义数组存储遍历的顶点
Arrays.fill(pre, -1); // 将数组 pre 全部初始化为 -1
int dot;
int temp;
int index=0;
while(queue.size()!=0)
{
dot = queue.poll(); // 返回队列首顶点
for(int i=0;i<graph.size();i++)
{
temp = graph.get(i); // temp 为每一次遍历的顶点
if(visted) // 若该顶点已遍历过则跳过
continue;
pre = temp;
if(temp==target)
{
System.out.print(source+"->");
print(pre, 0, target); // 打印深度遍历的路径
return;
}
index++;
visted=true;
queue.add(temp);
}
}
}
public void print(int[] pre,int index,int target)
{
if(pre!=target)
{
System.out.print(pre+"->");
print(pre, index+1, target);
}
else{
System.out.print(target);
}
}
```
## 深度优先遍历 DFS
**深度遍历**（Deep-First-Search）。先按照一定顺序向下遍历，若一条路径遍历结束尚未找到，则返回上一分叉点继续遍历下一条路径，知道找到对应目标，结束遍历。
```java
public void dfs(int source,int target)
{
result = false ; // 将查找结果重置回 false
boolean[] visted = new boolean; // 验证该顶点是够已被访问
int[] pre = new int;
Arrays.fill(pre, -1);
recurDfs(source,target,visted,pre,0);
System.out.print(source+"->");
print(pre, 0, target);
}
public void recurDfs(int source,int target,boolean[] visted,int[] pre,int index) // 回溯法实现深度遍历
{
if(source==target)
{
pre=source;
return ; // 找到对应目标返回
}
visted=true;
for(int i=0;i<graph.size();i++)
{
int temp = graph.get(i);
if(visted)
continue;
pre=temp;
index++;
recurDfs(temp, target, visted, pre, index);
}
}
```
总结，深度遍历像俗话说的「一条道走到黑」，只要路还能往下走就会一直向下遍历，直到撞了南墙才会回头。（文章中出现错误，可以直接在评论中指出） :rggrg这是在哪copy的吗？ - -||图咋没了... 大标题广搜的缩写是BFS..... 谢谢分享 zjgt 发表于 2019-4-15 17:53
这是在哪copy的吗？ - -||图咋没了... 大标题广搜的缩写是BFS.....
只是写的时候打错了，后面解释的时候有放完整单词。 “邻接表法表示图”中 B 少了个点。 tsds 发表于 2019-11-14 07:50
“邻接表法表示图”中 B 少了个点。
你说的是第一个？这里没有往回指的 hack_hu 发表于 2019-11-14 09:09
你说的是第一个？这里没有往回指的
我指的是无向图的邻接表，B与A，D连通。 tsds 发表于 2019-11-14 12:36
我指的是无向图的邻接表，B与A，D连通。
你再仔细理解下呗，在描述 A 这个点的时候就已经列出来 A->B ，所以不再列出 B 点到 A 的关系 hack_hu 发表于 2019-11-14 21:55
你再仔细理解下呗，在描述 A 这个点的时候就已经列出来 A->B ，所以不再列出 B 点到 A 的关系
https://img-blog.csdnimg.cn/20190414163226879.png
无向图中
A:B->C
B:D
C:A->D
D:B->C->E
E:D
照你的说法，是不是要改成
A:B->C
B:D
C:D
D:E
E:
页:
[1]