图
图(Graph)是由顶点的有穷非空集合和 顶点之间边 的集合组成，通常表示为: (Graph) G(V, E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。 图分无向图与有向图，根据图的边长，又分带权图与不带权图。
图的构造与表示:临接矩阵
#include<stdio.h>
int main(){
const int MAX_N = 5;//一共5个顶点
int Graph[MAX_N][MAX_N] = {0};//使用邻接矩阵表示
Graph[0][2] = 1;
Graph[0][4] = 1;
Graph[1][0] = 1;
Graph[1][2] = 1;
Graph[2][3] = 1;
Graph[3][4] = 1;
Graph[4][3] = 1;
printf("Graph:\n");
for(int i =0;i < MAX_N; i++){
for(int j = 0; j< MAX_N;j++){
printf("%d",Graph[i][j]);
}
printf("\n");
}
return 0;
}图的构造与表示：临接表
#include<stdio.h>
#include<vector>
struct GraphNode{
int label;
std::vector<GraphNode *> neighbors;
GraphNode(int x): label(x){};
};
int main(){
const int MAX_N = 5;
GraphNode *Graph[MAX_N];//5个顶点
for(int i = 0; i < MAX_N; i++){
Graph[i] = new GraphNode(i);
}
Graph[0]->neighbors.push_back(Graph[2]);
Graph[0]->neighbors.push_back(Graph[4]);
Graph[1]->neighbors.push_back(Graph[0]);
Graph[1]->neighbors.push_back(Graph[2]);
Graph[2]->neighbors.push_back(Graph[3]);
Graph[3]->neighbors.push_back(Graph[4]);
Graph[4]->neighbors.push_back(Graph[3]);
printf("Graph:\n");
for(int i = 0; i < MAX_N; i++){
printf("label(%d)",i);
for(int j = 0; j < Graph->neighbors.size();j++){
printg("%d",Graph[i]->neighbors[j]->label);
}
printf("\n");
}
for(int i =0; i< MAX_N; i++){
delete Graph[i];
}
return 0 ;
}图的深度优先遍历
从图中某个顶点v出发，首先访问该顶点，然后 依次从它的各个未被访问的 邻接点出发深度 优先搜索遍历图，直至图中所有和v有路径相通且未被访问的顶点都被访问到。 若此时尚有 其他顶点未被访问到，则另选一个未被访问的顶点作 起始点，重复上述过程，直至图中 所有 顶点都被访问到为止。
#include<stdio.h>
#include<vector>
struct GraphNode{
int label;
std::vector<GraphNode *> neighbors;
GraphNode(int x) : label(x){};
};
void DFS_graph(GraphNode *node, int visit[ ]){
visit[node->label] = 1;//标记已访问的顶点
printf("%d",node->label);
//访问相邻的且没有被访问的顶点
for(int i = 0; i < node->neighbors.size(); i++){
if(visit[node->neighbors[i]->label] == 0){
DFS_graph(node->neighbors[i],visit);
}
}
}
int main(){
const int MAX_N = 5;
GraphNode *Graph[MAX_N];//创建图的顶点
for(int i = 0; i < MAX_N ; i++){
Graph[i] = new GraphNode(i);
//添加图的边，注意添加边的顺序
Graph[0]->neighbors.push_back(Graph[4]);
Graph[0]->neighbors.push_back(Graph[2]);
Graph[1]->neighbors.push_back(Graph[0]);
Graph[1]->neighbors.push_back(Graph[2]);
Graph[2]->neighbors.push_back(Graph[3]);
Graph[3]->neighbors.push_back(Graph[4]);
Graph[4]->neighbors.push_back(Graph[3]);
int visit[MAX_N] = 0;//标记已访问的顶点
for(int i = 0; i < MAX_N; i++){
if(visit[i] == 0){//顶点没有被标记才会访问
printf("From label[%d] :",Graphp[i]->label);
DFS_graph(Graph[i],visit);
printf("\n");
}
}
for(int i = 0; i < MAX_N; i++){
delete Graph[i];
}
return 0;
}
}图的宽度优先遍历
从图中某个顶点v出发，在访问了 v之后依次访问v的各个未曾访问过的 邻接点，然后 分别从这些邻接点出发 依次访问它们的邻接点，并使得 “先被访问的顶点的邻接点 先 于后被访问的顶点的邻接点被访问 ”，直至图中所有 已被访问的顶点的邻接点 都被访 问到。如果此时图中尚有顶点 未被访问，则需要另选一个未曾被访问过的顶点作为新 的起始点，重复上述过程，直至图中所有顶点都被访问到为止。
void BFS_graph(GraphNode * node, int visit[]){
std::queue<GraphNode *>Q;
Q.push(node);
visit[node->label] = 1;
while(!Q.empty()){
GraphNode *node = Q.front();
Q.pop();
printf("%d",node->label);
for(int i =0; i < node->neighbors.size(); i++){
if(visit[node->neighbors[i]->label == 0]){
Q.push(node->neighbors[i]);
visit[node->neighbors[i]->label] = 1;
}
}
}
}课程安排
LeetCode 207. Course Schedule 已知有n个课程，标记从0至n-1，课程之间是有依赖关系的，例如希望完成A课程 ，可能需要先完成B课程。已知n个课程的依赖关系，求是否可以将n个课程全部 完成。
思考与分析
n个课程，它们之间有m个依赖关系，可以看成顶点个数为n，边个数为m的有向图。 图1:n = 3, m = [[0, 1], [0, 2], [1, 2]];可以完成。 图2:n = 3, m = [[0, 1], [1, 2], [2, 0]];不可以完成。 故，若有向图无环，则可以完成全部课程，否则不能。问题转换成，构建图，并判 断图是否有环。
方法一：深度优先搜索
在深度优先搜索时，如果正在搜索某一顶点(还未退出该顶点的递归深度搜索)，又 回到了该顶点，即证明图有环。
算法设计（无环）
#include<vector>
struct GraphNode{
int label;
std::vector<GraphNode *> neighbors;
GraphNode(int x): label(x){};
};
//节点访问状态，-1没有访问过，0代表正在访问，1代表访问结束
bool DFS_graph(GraphNode *node,std::vector<int> &visit){
visit[node->label] = 0;
for(int i = 0; i < node->neighbors.size();i++){
if(visit[node->neighbors[i]->label ]== -1){
if(DFS_graph(node->neighbors[i],visit) == 0){
return false;
}
}
else if(visit[node->neighbors[i]->label ]== 0){
return false;
}
}
visit[node->label] = 1;
return true;
}方法二：拓扑排序（宽度优先搜索）
在宽度优先搜索时，只将入度为0的点添加至队列。当完成一个顶点的搜索(从队 列取出)，它指向的所有顶点入度都减1，若此时某顶点入度为0则添加至队列，若完 成宽度搜索后，所有的点入度都为0，则图无环，否则有环。 入度：有多少个顶点指向该节点 出度：该节点指向几个节点
class Solution{
public:
bool canFinish(int numCourse,
std::vector<std::pair<int,int>>&prerequisites){
std::vector<GraphNode *>graph;
std::vector<int> degree;//入度数组
for(int i = 0; i < numCourse; i++){
degree.push_back(0);
graph.push_back(new GraphNode(i));
}
for(int i = 0; i < prerequisites.size(); i++){
GraphNode *begin = graph[prerequisites[i].second];
GraphNode *end = graph[prerequisites[i].first];
begin->neighbors.push_back(end);
degree[prerequisites[i].first]++;//入度++，即pair<课程1，课程2>，课程1的入度++
}
std::queue<GraphNode *>Q;
for(int i=0; i < numCourses;i++){
if(degree[i] == 0){
Q.push(graph[i]);
}
}
while(!Q.empty()){
GraphNode *node = Q.front();
Q.pop();
for(int i = 0; i < node->neighbors.size(); i++){
degree[node->neighbors[i]->label]--;
if(degree[node->neighbors[i]->label] ==0){
Q.push(node->neighbors[i]);
}
}
}
for(int i =0;i< graph.size();i++){
delete graph[i];
}
for(int i = 0; i< degree.size();i++){
if(degree[i]){
return false;
}
}
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.05.07 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录