数据结构图的深度遍历和广度遍历源程序

Dear 丶 2022-08-02 10:48 168阅读 0赞

\#include <stdio.h>  
\#include<string.h>  
\#include<malloc.h>  
\#define OVERFLOW -2  
\#define M 20   /\*最大顶点个数\*/  
typedef char VertexType\[20\];  
typedef int QElemType;  
typedef struct QNode  
\{  
char data;  
    struct QNode \*next;  
\}QNode, \*QueuePtr;  
  
  
typedef struct  
\{  
    QueuePtr front;  
    QueuePtr rear;  
\}LinkQueue;  
int InitQueue(LinkQueue &Q);  
int QueueEmpty (LinkQueue &Q);  
int EnQueue(LinkQueue &Q, int e);  
int DeQueue(LinkQueue &Q, int &e);  
  
  
int InitQueue(LinkQueue &Q)  
\{   
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));  
    if(!Q.front)   
return(OVERFLOW);  
    Q.front->next=NULL;  
return 1;   
\}  
  
  
  
  
int QueueEmpty (LinkQueue &Q)  
\{  
if(Q.front==Q.rear)  
return 1;  
    else  
return 0;   
\}  
  
  
  
  
int EnQueue(LinkQueue &Q,int e)  
\{    
QueuePtr p;  
    p=(QueuePtr)malloc(sizeof(QNode));  
    if (!p)   
return(OVERFLOW);  
    p->data=e;   
p->next=NULL;  
    Q.rear->next=p;  
    Q.rear=p;  
    return 1;   
\}  
  
  
  
  
int DeQueue(LinkQueue &Q, int &e)  
\{    
QueuePtr p;  
    if(Q.front==Q.rear)   
return 0;  
    p=Q.front->next;  
    e=p->data;  
    Q.front->next=p->next;  
    if(Q.rear==p)   
Q.rear=Q.front;  
    free(p);  
    return 1;   
\}  
  
  
  
  
  
  
  
  
/\*图的类型定义\*/  
typedef struct ArcCell  
\{  
int adj;      /\*图中有1/0表示是否有边，网中表示边上的权值\*/  
\}ArcCell, AdjMatrix\[M\]\[M\];  
typedef struct  
\{  
VertexType vexs\[M\];  /\*顶点向量\*/  
    AdjMatrix arcs;                  /\*邻接矩阵\*/  
    int vexnum,arcnum;                /\*图中当前顶点数和边数\*/  
\}MGraph;  
void CreateGraph(MGraph &G);  
int LocateVex(MGraph G,VertexType v);//确定v在G中的位置  
int FirstAdjVex(MGraph G,int v);//确定第一个相连的顶点  
int NextAdjVex(MGraph G,int v,int w);//确定下一个相连的顶点  
void PrintGraph(MGraph G);  
void Dfs(MGraph G, int v);  
void DfsTraverse(MGraph G);  
void BfsTraverse(MGraph G);  
/\*建立无向图的邻接矩阵\*/  
void CreateGraph(MGraph &G)  
\{   
int i,j,k;   
VertexType v1,v2;  
    printf("\\n请分别输入顶点数 弧数:");  
    scanf("%d %d",&G.vexnum,&G.arcnum);  
printf("输入 %d个 顶点:",G.vexnum);  
    for(i=0;i<G.vexnum;i++)     /\*输入顶点向量\*/  
    \{  
scanf("%s",G.vexs\[i\]);  
\}  
    printf("顶点列出\\n");  
    for(i=0;i<G.vexnum;i++)     /\*输出顶点向量\*/  
printf("%s\\n",G.vexs\[i\]);  
    for(i=0;i<G.vexnum;i++)     /\*矩阵初始化\*/  
for(j=0;j<G.vexnum;j++)  
       G.arcs\[i\]\[j\].adj=0;  
    printf("\\n请输入%d arcs(vi vj):\\n",G.arcnum);  
    for(k=0;k<G.arcnum;k++)       
    \{   
scanf("%s%s",v1,v2);  
        i=LocateVex(G,v1);    
j=LocateVex(G,v2);  
// printf("i=%d j=%d",i,j);  
        G.arcs\[i\]\[j\].adj=1;  
G.arcs\[j\]\[i\].adj=1;  
          
\}  
\}  
  
  
//确定顶点在矩阵中的下标  
int LocateVex(MGraph G,VertexType v)  
\{   
int i;  
    for(i=0;i<G.vexnum;i++)  
    if (strcmp(v,G.vexs\[i\])==0)   
return i;  
    return 0;  
\}  
  
  
/\* 查找第1个邻接点 \*/  
int FirstAdjVex(MGraph G,int v)  
\{   
int j;  
    for(j=0;j<G.vexnum;j++)  
    if(G.arcs\[v\]\[j\].adj==1)  
return j;  
    return -1;  
\}  
  
  
/\* 查找下一个邻接点 \*/  
int NextAdjVex(MGraph G,int v,int w)  
\{   
int j;  
    for(j=w+1;j<G.vexnum;j++)  
if (G.arcs\[v\]\[j\].adj==1)   
return j;  
return -1;  
\}  
  
  
/\*按邻接矩阵方式输出无向图\*/  
void PrintGraph(MGraph G)  
\{   
int i,j;  
    printf("图的邻接矩阵为:\\n");  
    for(i=0; i<G.vexnum; i++)  
    \{   
  
        for(j=0; j<G.vexnum; j++)  
\{  
printf("%4d",G.arcs\[i\]\[j\].adj);  
\}  
        printf("\\n");  
    \}  
\}  
  
  
/\*深度遍历\*/  
  
  
int visited\[M\];   
  
  
void Dfs(MGraph G, int v)  
\{  
int w;  
    visited\[v\]=1;  
    printf("%s ",G.vexs\[v\]);  
    for(w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w))  
if(!visited\[w\])   
Dfs(G,w);  
\}  
  
  
void DfsTraverse(MGraph G)  
\{   
int v;  
    for (v=0; v<G.vexnum; v++)  
        visited\[v\]=0;  
    for(v=0; v<G.vexnum; v++)  
        if (!visited\[v\])   
Dfs(G,v);  
\}  
  
  
/\* 广度遍历 \*/  
void BfsTraverse(MGraph G)  
\{   
int v,u,w;   
LinkQueue Q;  
for(v=0; v<G.vexnum; v++)   
visited\[v\]=0;  
InitQueue(Q);  
    for(v=0; v<G.vexnum; v++)  
if(!visited\[v\])  
        \{   
visited\[v\]=1;  
            printf("%s ",G.vexs\[v\]);  
       EnQueue(Q,v);  
            while(!QueueEmpty(Q))  
\{  
DeQueue(Q,u);  
                for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w))  
       if(!visited\[w\])  
                \{   
visited\[w\]=1;  
           printf("%s ",G.vexs\[w\]);  
           EnQueue(Q,w);  
                \}  
\}  
        \}  
\}  
  
  
/\*主函数\*/  
void main()  
\{  
    MGraph G;  
    CreateGraph(G);  
    PrintGraph(G);  
    printf("\\n深度遍历：\\n");  
DfsTraverse(G);  /\* 深度遍历 \*/  
    printf("\\n广度遍历：\\n");   
BfsTraverse(G);  /\* 广度遍历 \*/  
    printf("\\n");  
\}