图

图(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;
            }
        }
}
};