一：如何理解“图”
1，图和树一样都是非线性表数据结构，和树不同的是图是一种更加复杂的非线性表结构
2，树中的元素称之为节点，图中的元素则称之为顶点。
3，顶点可以与任意其他顶点建立关联，这种建立的关系叫做边，与顶点相连接的条数叫做顶点的度。
4，图可以分为有向图和无向图两种，有向图的边有方向。
5，在有向图中，度可以分为入度和出度（Out-degree）
6，带权图：在带权图中，每条边都有一个权重
无向图，有向图，网的领接矩阵
二：邻接矩阵存储方法
1，图最直观的一种存储方法是：邻接矩阵（Adjacency Matrix），邻接矩阵的底层依赖一个二维数组。
2，用邻接矩阵来表示一个图，虽然简单，直观，但是浪费存储空间。
①：对于无向图的二维数组中，如果将其对角线划分为上下两部分，那我们只需要利用上面或者下面这样的一半的空间就足够了，另一半白白浪费掉了。
②：若存储的是稀疏图（Sparse Matrix），即顶点很多，但每个顶点的边并不多，那邻接矩阵的存储方法就更加浪费空间了。
3，用邻接矩阵存储的优点：
①：存储方式简单，直接，因为基于数组，所以在获取两个顶点的关系时，就非常高效。
②：其次是计算方便。因为，可以将很多图的运算转换成矩阵之间的运算。如求解最短路径问题时会提到一个Floyd-Warshall算法，就是利用矩阵循环相乘若干次得到结果。
三：邻接表存储方法
无向图的邻接表表示
有向图的邻接表表示
1，对于稀疏图，邻接表（Adjacency List）可以解决邻接矩阵存储方式比较浪费内存空间的问题
2，邻接矩阵存储起来比较浪费空间，但使用比较节省时间，邻接表存储与之相反。
如图中，如果要确定是否存在从顶点2到顶点4的边，就需要遍历顶点2对应的链表，看那条链表中是否存在顶点4。但链表的存储方式对缓存不友好。
3，我们可以将邻接表中的链表改成平衡二叉查找树，实际开发中国还可选用红黑树。这样可以快速查找两个顶点之间是否存在边了。
4 邻接表表示不唯一。因为在各个结点的单链表中，各边结点的链接次序可以任意。
四：图的应用
如何存储微博，微信等社交网络中的好友关系？
1，微博，微信是两种“图”，前者是有向图，后者是无向图。
2，数据结构是为算法服务的，所以具体选择哪种存储方法，与期望支持的操作有关系。针对微博的用户关系，需要支持：
判断用户A是否关注了用户B;
判断用户A是否是用户B的粉丝
用户A关注用户B；
用户A取消关注用户B；
根据用户名称的首字母排序，分页获取用户的粉丝列表；
根据用户名称的首字母排序，分页获取用户的关注列表。
3，因为社交网络是一张稀疏图，使用邻接矩阵存储比较浪费存储空间，所以使用邻接表来存储。
4，但用一个邻接表来存储这种有向图是不够的，查找某个用户关注了哪些用户非常容易，但是如果想要知道某个用户都被哪些用户关注了，是非常困难的。
5，因此，需要一个逆邻接表。邻接表中存储了用户的关注关系，逆邻接表中存储的是用户的被关注关系。
6，对应到图上，邻接表中，每个顶点的链表中，存储的就是这个顶点指向的顶点，逆邻接表中，每个顶点的链表中，存储的是指向这个顶点的顶点。
五：深度优先DFS
图的深度优先伪代码看思路
1 通过visited[]标记顶点是否访问过。初始状态为FALSE：防止一些顶点被多次访问
2 需要借助一个递归工作栈，空间复杂度为O(|V|)
3 采用邻接矩阵存储的时候，每个顶点的邻接点所需要时间为O(|V|)，故算法时间复杂度为O(|V|^2)，采用邻接表表示时，邻接点需要时间为O(|E|)，访问顶点需要时间为O(|V|)，故总的时间复杂度为O(|V|+|E|)
4 注意对每个连通分量调用了一次BFS，不然可能存在只访问一个连通分量的问题：
DFS 算法一般思路
具体代码（图是邻接矩阵表示法+递归实现DFS）：
// Recursive dfs approach
void dfs(struct Graph *graph, int vertex)
{
struct node *adjList = graph->adjLists[vertex];
struct node *temp = adjList;
// Add vertex to visited list and print it
graph->visited[vertex] = 1;
printf("%d ", vertex);
// Recursively call the dfs function on all unvisited neighbours
while (temp != NULL)
{
int connectedVertex = temp->vertex;
if (graph->visited[connectedVertex] == 0)
{
dfs(graph, connectedVertex);
}
temp = temp->next;
}
}
对应无向图的遍历序列为abdehcfg
对应无向图的遍历序列为abdehcfg
完整代码参考：
github.com TheAlgorithms graphs dfs.c
算法：判断一个无向图G是否为一颗树 若是，则算法返回true：
判断一个无向图G是否为一颗树
算法：图的深度优先搜索DFS算法的非递归算法（图采用邻接表形式）
图的深度优先搜索DFS算法的非递归算法
算法：路径判断
算法：简单路径输出
六：广度优先BFS
类似于二叉树的层次遍历
BFS模拟图
通过伪代码看思路
关注点：
1 通过visited[]标记顶点是否访问过。初始状态为FALSE：防止一些顶点被多次访问
2 邻接表还是邻接矩阵，都需要借助队列，n个结点都需要入队一次，在最坏情况下，空间复杂度为O(|V|)
3 采用邻接表存储时，每个顶点访问一次，边至少访问一次，算法总时间复杂度为O(|V|+|E|) ,采用邻接矩阵存储的时候，算法时间复杂度为O(|V|^2)
4 注意对每个连通分量调用了一次BFS，不然可能存在只访问一个连通分量的问题
BFS算法一般思路
下图对应无向图的遍历序列为abcdefgh：
对应无向图的遍历序列为abcdefgh
具体代码（邻接矩阵表示法）：
void bfs(struct Graph *graph, int startVertex)
{
struct queue *q = createQueue();
// Add to visited list and put in queue
graph->visited[startVertex] = 1;
enqueue(q, startVertex);
printf("Breadth first traversal from vertex %d is:\n", startVertex);
// Iterate while queue not empty
while (!isEmpty(q))
{
printf("%d ", pollQueue(q));
int currentVertex = dequeue(q);
struct node *temp = graph->adjLists[currentVertex];
// Add all unvisited neighbours of current vertex to queue to be printed
// next
while (temp)
{
int adjVertex = temp->vertex;
// Only add if neighbour is unvisited
if (graph->visited[adjVertex] == 0)
{
graph->visited[adjVertex] = 1;
enqueue(q, adjVertex);
}
temp = temp->next;
}
}
}
完整代码参考链接：
github.com TheAlgorithms graphs bfs.c
BFS求解单源最短路径
BFS求解单源最短路径
网友评论