【经典算法】:图的遍历算法的实现

àì夳堔傛蜴生んèń 2022-08-23 04:51 204阅读 0赞

\#include<stdio.h>  
  
\#include "StdAfx.h"  
\#define MAX 20  
\#include "malloc.h"  
int visited\[MAX\]; //访问标志数组  
  
typedef struct  
 \{  
    char vexs\[MAX\];  //顶点向量  
    int arcs\[MAX\]\[MAX\]; //邻接矩阵  
    int vexnum,arcnum; //图的当前顶点数和边数  
\}Graph;  
  
typedef struct Qnode  
\{  
    int data;  
    struct Qnode \*next;  
\}Qnode,\*Queueptr;  
typedef struct  
\{  
    Queueptr front;  
    Queueptr rear;  
\}Linkqueue;  
void InitQueue(Linkqueue &Q)  
\{  
    Q.front=Q.rear=(Queueptr)malloc(sizeof(Qnode));  
    if(Q.front)  
        Q.front->next=NULL;  
\}  
void EnQueue(Linkqueue &Q,int e)  
\{  
    Queueptr p;  
    p=(Queueptr)malloc(sizeof(Qnode));  
    if(p)  
    \{  
        p->data=e;  
        p->next=NULL;  
        Q.rear->next=p;  
        Q.rear=p;  
    \}  
\}  
int DeQueue(Linkqueue &Q)  
\{  
    int e;  
    Queueptr p;  
    if(Q.rear!=Q.front)  
    \{  
        p=Q.front->next;  
        e=p->data;     
        Q.front->next=p->next;  
        if(Q.rear==p)  
            Q.rear=Q.front;  
        free(p);  
    \}  
    if(Q.front==p)  
        Q.rear=Q.front;  
    return e;  
\}  
  
int Locatevex(Graph G,char v) //返回元素v的位置  
\{  
    int i;  
    for(i=0;i<G.vexnum;i++)  
        if(G.vexs\[i\]==v)  
            return i;  
        return -1;  
\}  
void CreateGraph(Graph &G)    //创建无向图的邻接矩阵  
\{                        
    int i,j,w,m,n;  
    char a,b,c;  
    printf("请输入图G的顶点数和弧数:");  
    scanf("%d%d",&G.vexnum,&G.arcnum);  
    getchar();  
    for(i=0;i<G.vexnum;i++)  
        visited\[i\]=0;  
    for(i=0;i<G.vexnum;i++)  
    \{    printf("请输入第%d个顶点信息:",i+1);                          
        scanf("%c",&G.vexs\[i\]);  
        getchar();                                        
    \}  
    for(i=0;i<G.vexnum;i++)                       
        for(j=0;j<G.vexnum;j++)  
            G.arcs\[i\]\[j\]=0;  
    for(i=0;i<G.arcnum;i++)  
    \{                   
        printf("请输入第%d条弧依附的两个顶点及权值: ",i+1);  
        scanf("%c %c %d%c",&a,&b,&w,&c);           
        m=Locatevex(G,a);  
        n=Locatevex(G,b);  
        G.arcs\[m\]\[n\]=w;  
        G.arcs\[n\]\[m\]=w;  
    \}  
\}  
void PrintMatrix(Graph G) //输出邻接矩阵  
\{  
    int i,j;  
    printf("\\n由图G生成的邻接矩阵如下:\\n");  
    for(i=0;i<G.vexnum;++i)  
    \{  
        for(j=0;j<G.vexnum;++j)  
            printf("%-2d",G.arcs\[i\]\[j\]);  
        printf("\\n");  
    \}  
\}  
  
int FirstAdiVex(Graph G,int v)    //图G中顶点v的第一个邻接顶点  
\{       
    int i;  
    if(v>=0&&v<G.vexnum)  
    \{    
        for(i=0;i<G.vexnum;i++)  
            if(G.arcs\[v\]\[i\]!=0)  
                return i;  
    \}  
    return -1;  
\}  
int NextAdVex(Graph G,int i,int j) //图G中顶点i的第j个邻接顶点的下一个邻接顶点  
\{  
    int k;  
    if(i>=0&&i<G.vexnum&&j>=0&&j<G.vexnum)  
    \{  
        for(k=j+1;k<G.vexnum;k++)  
            if(G.arcs\[i\]\[k\]!=0)  
                return k;  
    \}  
    return -1;  
\}  
void DFS(Graph G,int v) //从第v个顶点出发深度递归遍历图  
\{  
    int u;  
    printf("%2c",G.vexs\[v\]);  
    visited\[v\]=1;  
    u=FirstAdiVex(G,v);  
    while(u>=0)  
    \{  
        if(!visited\[u\])  
            DFS(G,u);  
        u=NextAdVex(G,v,u);  
    \}  
\}  
  
void BFS(Graph G)//广度非递归遍历  
\{  
    int i,w,k;  
    Linkqueue Q;                                      
    InitQueue(Q);  
    for(i=0;i<MAX;i++)  
        visited\[i\]=0;  
    for(i=0;i<G.vexnum;i++)  
        if(!visited\[i\])  
        \{  
            visited\[i\]=1;  
            printf("%2c",G.vexs\[i\]);  
            EnQueue(Q,i);           
            while(Q.front!=Q.rear)  
            \{  
                k=DeQueue(Q);       
                for(w=FirstAdiVex(G,k);w>=0;w=NextAdVex(G,k,w))  
                    if(!visited\[w\])  
                    \{  
                        visited\[w\]=1;  
                        printf("%2c",G.vexs\[w\]);  
                        EnQueue(Q,w);  
                    \}  
            \}  
        \}  
\}  
  
int main()  
\{  
    int m;  
    Graph G;  
    printf("无向图的创建及DFS和BFS的递归和非递归实现!\\n\\n");  
    while(1)  
    \{  
        printf("1.创建无向图!\\n");  
        printf("2.图的深度优先遍历!\\n");  
        printf("3.图的广度优先遍历!\\n");  
        printf("4.退出!\\n");  
        printf("请选择功能:");  
        scanf("%d",&m);      
        if(m==1)  
        \{  
            CreateGraph(G);  
            PrintMatrix(G);  
        \}  
        else if(m==2)  
        \{  
            printf("图G的深度递归优先遍历序列为:\\n");  
            DFS(G,0);  
            printf("\\n");  
        \}  
        else if(m==3)  
        \{  
            printf("图G的广度非递归优先遍历序列为:\\n");  
            BFS(G);  
            printf("\\n");  
        \}  
        else if(m==4)  
        \{  
           printf("成功退出!\\n");  
           break;  
        \}  
        else  
           printf("重新输入!\\n");  
    \}  
    return 0;  
\}