//拓?fù)渑判?void TopsortbyQueue(ALGraph*G){
    for(int i=0; i< G->vexNum;i++)
        mark[i]=FALSE;
    using std::queue;
    queue<int> Q;
    cout<<"拓?fù)湫蛄袨?"<<endl;
    for(int i=0; i< G->vexNum;i++){
        if(G->Indegree[i].indegree==0)
            Q.push(i);}
        while(!Q.empty()){
            int v=Q.front();
            Q.pop();
            cout<<v;
            mark[v]=TRUE;
            for(Edge e=FirstEdge(G,v);isEdge(G,e);e=NextEdge(G,e)){
                G->Indegree[e.to].indegree--;
                if(G->Indegree[e.to].indegree ==0)
                    Q.push(e.to);
            }
        }
        for(int i=0;i< G->vexNum;i++)
            if(mark[i]==FALSE){
                cout<<endl;
                cout<<"還有頂點(diǎn)未訪問染簇，此圖有環(huán)参滴。"<<endl;
                break;
            }
}

4 總結(jié)#

明顯感覺到寫得多了對(duì)于語言的運(yùn)用更熟練了，也更有了設(shè)計(jì)算法需要的邏輯思想锻弓。這個(gè)寫的還算比較順_{隨著思維和語言能力提升砾赔，希望能在acm校選賽比賽上有好的發(fā)揮}過兩天來更新結(jié)果！

5 附錄#

鄰接矩陣：

鄰接矩陣測(cè)試結(jié)果

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<queue> 
using namespace std;

#define MaxVertexNum 100 /*最大頂點(diǎn)數(shù)設(shè)為100*/
typedef enum{FALSE,TRUE} Boolean;
Boolean mark[MaxVertexNum];

typedef char VertexType; /*頂點(diǎn)類型設(shè)為字符型*/
typedef int EdgeType; /*邊的權(quán)值設(shè)為整型*/

typedef struct {
    VertexType vexs[MaxVertexNum]; /*頂點(diǎn)表*/
    EdgeType edges[MaxVertexNum][MaxVertexNum]; /*鄰接矩陣，即邊表*/
    int numVertex,numEdge; /*頂點(diǎn)數(shù)和邊數(shù)*/
}Mgragh,*MGragh; /*Maragh 是以鄰接矩陣存儲(chǔ)的圖類型*/


typedef struct edge{
    int from,to,weight;
}Edge,*Edged;

void CreateMGraph(MGragh G){/*建立有向圖G 的鄰接矩陣存儲(chǔ)*/
int i,j,k,w;
char ch;
cout<<"請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)";
cin>>i>>j;
G->numVertex=i;
G->numEdge=j;

cout<<"請(qǐng)輸入頂點(diǎn)信息:"<<endl;

for (i=0;i<G->numVertex;i++) {cout<<"第"<<i<<"個(gè)點(diǎn):";cin>>G->vexs[i];} /*輸入頂點(diǎn)信息暴心，建立頂點(diǎn)表*/
for (i=0;i<G->numVertex;i++)
    for (j=0;j<G->numVertex;j++) 
        G->edges[i][j]=0; /*初始化鄰接矩陣*/

cout<<"請(qǐng)輸入每條邊對(duì)應(yīng)的兩個(gè)頂點(diǎn)的序號(hào):\n";

for (k=0;k<G->numEdge;k++){
    cout<<"v<i,j>:";
    cin>>i>>j; /*輸入e 條邊妓盲，建立鄰接矩陣*/
        G->edges[i][j]=1;
            }
}

void displaygraph(MGragh G){
int i,j;

for(i=0;i<G->numVertex;i++){
    for(j=0;j<G->numVertex;j++){
        cout<<G->edges[i][j]<<" ";}
    cout<<endl;
}
}

Edge FirstEdge(MGragh G,int oneVertex){
    Edge myEdge;
    myEdge.from=oneVertex;
    for(int i=0;i<G->numVertex;i++){
        if(G->edges[oneVertex][i]!=0){
            myEdge.to=i;
            myEdge.weight=G->edges[oneVertex][i];
            break;
        }
    }
    return myEdge;
}

Edge NextEdge(MGragh G,Edge preEdge){
    Edge myEdge;
    myEdge.from =preEdge.from ;
    if(preEdge.to <G->numVertex){
        for(int i=preEdge.to+1;i<G->numVertex;i++){
            if(G->edges[preEdge.from][i]!=0){
                myEdge.to =i;
                myEdge.weight =G->edges[preEdge.from ][i];
                break;
            }
        }
    }
    return myEdge;
}

bool isEdge(MGragh G, Edge myEdge){
    int test=0;
    for(int i=0;i<G->numVertex;i++){
        if(myEdge.to>=0&&G->edges[myEdge.from][myEdge.to]==1)return true;
    }
    return false;
}

//深度優(yōu)先周游    
void DFS(MGragh G, int v){
    mark[v]=TRUE;
    cout<<G->vexs[v];
    for(Edge e=FirstEdge(G,v);isEdge(G,e);e=NextEdge(G,e)){
        if(mark[e.to]==FALSE) DFS(G,e.to);
    }
}

void DFSM(MGragh G,int v){
    for(int i=0;i<G->numVertex;i++){
        mark[i]=FALSE;
    }
    DFS(G,0);
}

//廣度優(yōu)先周游
void BFS(MGragh G, int v){
    for(int i=0;i<G->numVertex;i++){
        mark[i]=FALSE;
    }
    using std::queue;
    queue<int>Q;
    cout<<G->vexs[v];
    mark[v]=TRUE;
    Q.push(v);
    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
        for(Edge e=FirstEdge(G,u);isEdge(G,e);e=NextEdge(G,e))
            if(mark[e.to]==FALSE){
                cout<<G->vexs[e.to];
                mark[e.to]=TRUE;
                Q.push(e.to);
            }
    }
}

int main(){
    Mgragh *Graph = (Mgragh *)malloc(sizeof(Mgragh));
    CreateMGraph(Graph);
    displaygraph(Graph);
    cout<<endl;
    BFS(Graph,0);
    cout<<endl;
    DFSM(Graph,0);
    system("pause");
    return 0;
}

鄰接表

鄰接表

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<queue> 
using namespace std;
#define MAX_VERTEXT_NUM 20
typedef enum{FALSE,TRUE} Boolean;
Boolean mark[MAX_VERTEXT_NUM];

typedef struct edge{
    int from,to,weight;
}Edge,*Edged;

typedef struct ArcNode{
    int adjvex;
    struct ArcNode *nextArc;
    int weight;
}ArcNode;

typedef struct VNode{
    char data;
    ArcNode *firstArc;
}VNode, AdjList[MAX_VERTEXT_NUM];

typedef struct Indegree{
    int indegree;
}Indegree,indegree[MAX_VERTEXT_NUM];

typedef struct{
    AdjList verTices;
    int vexNum;
    int arcNum;
    int kind;
    indegree Indegree;
}ALGraph;

typedef struct Dist{
    int index;
    int length;
    int pre;
}Dist,*Dijk;

edge FirstEdge(ALGraph *G,int oneVertex){
    Edge myEdge;
    myEdge.from=oneVertex;
    ArcNode *temp=G->verTices[oneVertex].firstArc;
    if(temp->nextArc!=NULL){
        myEdge.to=temp->nextArc->adjvex;
        myEdge.weight=temp->nextArc->weight;
    }
    return myEdge;
}

edge NextEdge(ALGraph *G,Edge preEdge){
    Edge myEdge;
    myEdge.from =preEdge.from;
    ArcNode *temp=G->verTices[preEdge.from].firstArc;
    while(temp->nextArc!=NULL&&temp->adjvex<=preEdge.to)
        temp=temp->nextArc;
    if(temp->nextArc!=NULL){
        myEdge.to=temp->nextArc->adjvex;
        myEdge.weight=temp->nextArc->weight;
    }
    return myEdge;
}

bool isEdge(ALGraph *G, Edge myEdge){
    int n=0;
    ArcNode *p;
    p=G->verTices[myEdge.from].firstArc;
    while(p){
        if(p->adjvex==myEdge.to){
            n=0;
        }else{
            n=1;
        }
        p=p->nextArc;
    }
    if(n==0){return true;}
    else{
        return false;
    }
}

void CreateGraph(ALGraph *G)
{
    int i,j,k,weight;
    ArcNode *arcNode;
    printf_s("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)：");
    cin>>G->vexNum;
    cin>>G->arcNum;
    //建立頂點(diǎn)表
    printf_s("建立頂點(diǎn)表\n");
    for (i = 0; i < G->vexNum; i++)
    {
        printf_s("請(qǐng)輸入第%d個(gè)頂點(diǎn):", i);
        cin>>G->verTices[i].data;
        arcNode = (ArcNode *)malloc(sizeof(ArcNode));
        arcNode->adjvex=i;
        arcNode->nextArc=NULL;
        G->verTices[i].firstArc=arcNode;
        G->Indegree[i].indegree=0;
    }
    //建立邊表
    printf_s("建立邊表\n");
    for (k = 0; k < G->arcNum; k++)
    {
        printf_s("請(qǐng)輸入（vi-vj）的頂點(diǎn)對(duì)序號(hào)");
        cin>>i;
        cin>>j;
        arcNode = (ArcNode *)malloc(sizeof(ArcNode));
        arcNode->adjvex = j;
        arcNode->nextArc = G->verTices[i].firstArc->nextArc;//插入表頭
        G->verTices[i].firstArc ->nextArc= arcNode;
        G->Indegree[j].indegree++;
    }
}

//顯示圖的鄰接表
void DisplayGraph(ALGraph *G)
{
    int i;
    for (i = 0; i < G->vexNum; i++)
    {
            cout<<G->Indegree[i].indegree;
            ArcNode *P= G->verTices[i].firstArc;
            printf_s("%d->", i);
        while (P != NULL)
        {
            printf_s("%d->", P->adjvex);
            P = P->nextArc;
        }
        printf_s("\n");
    }
}

//深度優(yōu)先周游
void DFSM(ALGraph *G,int i){
    ArcNode *p;
    cout<<G->verTices[i].data;
    mark[i]=TRUE;
    p=G->verTices[i].firstArc;
    while(p){
        if(mark[p->adjvex]==FALSE)
            DFSM(G,p->adjvex);
        p=p->nextArc;       
    }
}

void DFS(ALGraph *G){
    for ( int i=0; i<G->vexNum;i++)
        mark[i]=FALSE;
    for( int i=0; i<G->vexNum;i++)
        if(!mark[i])
            DFSM(G,i);
}

//廣度優(yōu)先周游
void BFS(ALGraph *G,int x){
    ArcNode *p;
    int w;
    using std::queue;
    queue<int> Q;
    for ( int i=0; i<G->vexNum;i++) {mark[i]=FALSE;}
    cout<<G->verTices[x].data;
    mark[x]=TRUE;
    Q.push(x);
    while(!Q.empty()){
        int v=Q.front();
        Q.pop();
        p=G->verTices[v].firstArc;
        while(p){
            int w=p->adjvex;
            if(mark[w]==FALSE){
                mark[w]=TRUE;
                cout<<G->verTices[w].data;
                Q.push(w);}
            p=p->nextArc;
            }
        }
}

//拓?fù)渑判?void TopsortbyQueue(ALGraph*G){
    for(int i=0; i< G->vexNum;i++)
        mark[i]=FALSE;
    using std::queue;
    queue<int> Q;
    cout<<"拓?fù)湫蛄袨?"<<endl;
    for(int i=0; i< G->vexNum;i++){
        if(G->Indegree[i].indegree==0)
            Q.push(i);}
        while(!Q.empty()){
            int v=Q.front();
            Q.pop();
            cout<<v;
            mark[v]=TRUE;
            for(Edge e=FirstEdge(G,v);isEdge(G,e);e=NextEdge(G,e)){
                G->Indegree[e.to].indegree--;
                if(G->Indegree[e.to].indegree ==0)
                    Q.push(e.to);
            }
        }
        for(int i=0;i< G->vexNum;i++)
            if(mark[i]==FALSE){
                cout<<endl;
                cout<<"還有頂點(diǎn)未訪問，此圖有環(huán)专普。"<<endl;
                break;
            }
}

int main(){
    int x;
    int num;
    string edge;

    ALGraph *Graph = (ALGraph *)malloc(sizeof(ALGraph));
    CreateGraph(Graph);
    DisplayGraph(Graph);
    DFS(Graph);
    BFS(Graph,0);

    TopsortbyQueue(Graph);
    system("pause");
}