第一步：定义邻接表的储存方式（结构体）： data 那边放的是顶点集合右边放的是边的集合，其实也是点，只不过，两个点就可以看成一个边了是吧，比如第一行，左边表示 v0这个点，，右边就表示 v0 和  v1所构成的边， v0 和  v3点 所构成的边， 边的结构体： #include<bits/stdc++.h>#define MVNum 20                    //最大顶点数using namespace std;const int maxn = 100;bool visted[maxn];int topu[maxn];typedef struct ArcNode{    int adjvex;                     // 该边所指向顶点的位置    struct ArcNode *nextarc;        // 指向下一条边的指针    int info;                       // 和边相关的信息}ArcNode;点的结构体： typedef struct VNode{               // 顶点信息    int data;    int indegree;                    // 入度    int falg;                        // 序号    ArcNode *firstarc;              //指向第一条依附该顶点的边的指针}VNode , AdjList[MVNum];   图的结构体： typedef struct {    AdjList vertices;    int vexnum, arcnum;             // 图的当前顶点数和边数}ALGraph;前面不理解先别往下看 第二步：创建图： int LocateVex(ALGraph &G, VNode v,int flag){    int cnt = -1;    for (int i= 0;i < G.vexnum ;i++){        if(v.data == G.vertices[i].data && flag == G.vertices[i].falg){            cnt = i;            break;        }    }    return cnt;}void CreateHDG (ALGraph &G){    VNode v1, v2;    int flag1,flag2;    cout << "请输入有向连通图的总顶点数和总边数："<< endl;    cin >> G.vexnum >> G.arcnum;    //输入总顶点数，总边数    for (int i= 0;i < G.vexnum ; i++ ){         //输入各点，构造表头节点表        cout << "请输入当前所创建顶点的值" << endl;        cin >> G.vertices[i].data;                 // 输入顶点值        G.vertices[i].firstarc = NULL;            // 初始化表头节点的指针域为NULL        G.vertices[i].indegree = 0;        G.vertices[i].falg = i+1;    }    for (int k = 0 ; k < G.arcnum ; k++){           // 输入各边，构造邻接表        cout << "请分别输入当前所创建边所连接的两个顶点的值和序号（请输入四个数）"<<endl;        cin >> v1.data >> flag1 >> v2.data >> flag2;                // 输入一条边依附的两个顶点,和标志，防止两个顶点有相同值的情况，下面的locate函数不起作用        int  i =LocateVex(G, v1,flag1) ,j = LocateVex(G, v2,flag2);        G.vertices[j].indegree++;//        cout << i << " "<< j << endl;        //确定v1和v2在G中的位置，即顶点在G.vertices中的序号        ArcNode *p1 = new ArcNode;              // 生成一个新的边节点*p1        p1->adjvex = j;                         // 临界点序号为j        p1->nextarc = G.vertices[i] .firstarc;        G.vertices[i].firstarc = p1;        // 将新节点*p1,插入到顶点vj的边表头部    }}第三步： DFS: 注意，因为这个dfs没有回朔，所以只能遍历连通图 void DfS(ALGraph G, int v){    cout << G.vertices[v].data<<" ";    visted[v] = true;    ArcNode *p = G.vertices[v] .firstarc;    while(p!=NULL){        int w = p->adjvex;        if(!visted[w]) DfS(G, w);        p = p -> nextarc;    }}第四步：BFS : void NextAdjVex(ALGraph G , int u, int &w){    ArcNode *p = G.vertices[u].firstarc;    int flag =0;    while(p!=NULL){        w = p ->adjvex;        if(!visted[w]) {            flag = 1;            break;        }        p = p->nextarc;    }    if(flag == 0) w = -1;}queue<int> qu;    // 定义一个对列，c++ stl 内置了队列的数据结构，直接拿来用void Bfs(ALGraph G, int v){    cout << G.vertices[v].data<<" ";    visted[v] = true;    qu.push(v);    while(!qu.empty()){        int u =qu.front();        qu.pop();        ArcNode *p = G.vertices[u].firstarc;        int w;        if(!p){            w = -1;        }        else w = p ->adjvex;        for(  ; w >= 0 ;NextAdjVex(G, u, w) )            if(!visted[w]){                cout<< G.vertices[w].data <<" ";                visted[w] = true;                qu.push(w);            }    }}第五步：计算某个顶点的度： int CountDegree(ALGraph G,int v){    int cnt = 0;    ArcNode *p = G.vertices[v].firstarc;    while(p != NULL){        cnt ++;        p = p->nextarc;    }    return cnt;}第六步：拓扑排序： bool TUPUSort(ALGraph G){    stack<int >s;    for(int i=0;i < G.vexnum ;i++){        if(!G.vertices[i].indegree) s.push(i);    }    int cnt =0;    while(!s.empty()){        int i = s.top();        s.pop();        topu[cnt] = i;        ++cnt;        ArcNode *p = G.vertices[i].firstarc;        while(p!=NULL){            int k = p->adjvex;            --G.vertices[k].indegree;            if( G.vertices[k].indegree== 0) s.push(k);            p = p->nextarc;        }    }    if(cnt < G.vexnum) return false;    else return true;}完工 完整代码 ////  main.cpp//  第六次实验////  Created by 宋玉良 on 2020/12/2.//#include<bits/stdc++.h>#define MVNum 20                    //最大顶点数using namespace std;const int maxn = 100;bool visted[maxn];int topu[maxn];int cntt = 0,cnt1 = 0;typedef struct ArcNode{    int adjvex;                     // 该边所指向顶点的位置    struct ArcNode *nextarc;        // 指向下一条边的指针    int info;                       // 和边相关的信息}ArcNode;typedef struct VNode{               // 顶点信息    int data;    int indegree;    int falg;    ArcNode *firstarc;              //指向第一条依附该顶点的边的指针}VNode , AdjList[MVNum];            //AdjList 表示邻接表类型typedef struct {    AdjList vertices;    int vexnum, arcnum;             // 图的当前顶点数和边数}ALGraph;int LocateVex(ALGraph &G, VNode v,int flag){    int cnt = -1;    for (int i= 0;i < G.vexnum ;i++){        if(v.data == G.vertices[i].data && flag == G.vertices[i].falg){            cnt = i;            break;        }    }    return cnt;}void CreateHDG (ALGraph &G){    VNode v1, v2;    int flag1,flag2;    cout << "请输入有向连通图的总顶点数和总边数："<< endl;    cin >> G.vexnum >> G.arcnum;    //输入总顶点数，总边数    for (int i= 0;i < G.vexnum ; i++ ){         //输入各点，构造表头节点表        cout << "请输入当前所创建顶点的值" << endl;        cin >> G.vertices[i].data;                 // 输入顶点值        G.vertices[i].firstarc = NULL;            // 初始化表头节点的指针域为NULL        G.vertices[i].indegree = 0;        G.vertices[i].falg = i+1;    }    for (int k = 0 ; k < G.arcnum ; k++){           // 输入各边，构造邻接表        cout << "请分别输入当前所创建边所连接的两个顶点的值和序号（请输入四个数）"<<endl;        cin >> v1.data >> flag1 >> v2.data >> flag2;                // 输入一条边依附的两个顶点,和标志，防止两个顶点有相同值的情况，下面的locate函数不起作用        int  i =LocateVex(G, v1,flag1) ,j = LocateVex(G, v2,flag2);        G.vertices[j].indegree++;//        cout << i << " "<< j << endl;        //确定v1和v2在G中的位置，即顶点在G.vertices中的序号        ArcNode *p1 = new ArcNode;              // 生成一个新的边节点*p1        p1->adjvex = j;                         // 临界点序号为j        p1->nextarc = G.vertices[i] .firstarc;        G.vertices[i].firstarc = p1;        // 将新节点*p1,插入到顶点vj的边表头部    }}void DfS(ALGraph G, int v){    cntt ++;    cout << G.vertices[v].data<<" ";    visted[v] = true;    ArcNode *p = G.vertices[v] .firstarc;    while(p!=NULL){        int w = p->adjvex;        if(!visted[w]) DfS(G, w);        p = p -> nextarc;    }}void NextAdjVex(ALGraph G , int u, int &w){    ArcNode *p = G.vertices[u].firstarc;    int flag =0;    while(p!=NULL){        w = p ->adjvex;        if(!visted[w]) {            flag = 1;            break;        }        p = p->nextarc;    }    if(flag == 0) w = -1;}queue<int> qu;    // 定义一个对列，c++ stl 内置了队列的数据结构，直接拿来用void Bfs(ALGraph G, int v){    cnt1++;    cout << G.vertices[v].data<<" ";    visted[v] = true;    qu.push(v);    while(!qu.empty()){        int u =qu.front();        qu.pop();        ArcNode *p = G.vertices[u].firstarc;        int w;        if(!p){            w = -1;        }        else w = p ->adjvex;        for(  ; w >= 0 ;NextAdjVex(G, u, w) )            if(!visted[w]){                cnt1++;                cout<< G.vertices[w].data <<" ";                visted[w] = true;                qu.push(w);            }    }}int CountDegree(ALGraph G,int v){    int cnt = 0;    ArcNode *p = G.vertices[v].firstarc;    while(p != NULL){        cnt ++;        p = p->nextarc;    }    return cnt;}bool TUPUSort(ALGraph G){    stack<int >s;    for(int i=0;i < G.vexnum ;i++){        if(!G.vertices[i].indegree) s.push(i);    }    int cnt =0;    while(!s.empty()){        int i = s.top();        s.pop();        topu[cnt] = i;        ++cnt;        ArcNode *p = G.vertices[i].firstarc;        while(p!=NULL){            int k = p->adjvex;            --G.vertices[k].indegree;            if( G.vertices[k].indegree== 0) s.push(k);            p = p->nextarc;        }    }    if(cnt < G.vexnum) return false;    else return true;}int main(){    ALGraph G;    CreateHDG(G);    memset(visted, false, sizeof(visted));    int v;    cout << "请输入遍历开始点的序号："<<endl;    cin >> v;    cout << "深度优先遍历序列为：" <<endl;    DfS(G, v-1);    cout << endl;    if(cntt < G.vexnum){        cout <<"请从未遍历过的顶点开始遍历"<< endl;        int v1;        cout << "请输入遍历开始点的序号："<<endl;        cin >> v1;        DfS(G, v1-1);    }    cout << endl;    memset(visted, false, sizeof(visted));    cout << "广度优先遍历序列为： "<< endl;    Bfs(G, v-1);    cout << endl;    if(cnt1 < G.vexnum){        cout <<"请从未遍历过的顶点开始遍历"<< endl;        int v2;        cout << "请输入遍历开始点的序号："<<endl;        cin >> v2;        Bfs(G, v2-1);    }    cout << endl;    if(TUPUSort(G)){        cout << "拓扑排序成功，拓扑序列为："<<endl;        for(int i = 0; i<G.vexnum ;i++){            cout << topu[i]<<" ";        }    }    else{        cout << "此图无法构成拓扑序列";    }    cout << endl;}//7 10//0 1 2 3 4 5 6//0 2//0 4//1 2//1 3//2 5//3 5//2 4//2 6//5 6//4 6//0/*输入样例和输出样例：请输入有向连通图的总顶点数和总边数：4 4请输入当前所创建顶点的值2请输入当前所创建顶点的值3请输入当前所创建顶点的值5请输入当前所创建顶点的值4请分别输入当前所创建边所连接的两个顶点的值和序号（请输入四个数）2 13 2请分别输入当前所创建边所连接的两个顶点的值和序号（请输入四个数）2 1 5 3请分别输入当前所创建边所连接的两个顶点的值和序号（请输入四个数）5 3 4 4请分别输入当前所创建边所连接的两个顶点的值和序号（请输入四个数）4 4 2 1请输入遍历开始点的序号：0深度优先遍历序列为：2 5 4 3 2 5 3 4 此图无法构成拓扑序列*/