有向图的DFS和BFS遍历输出图的结构

Question

C语言数据结构，实现有向图的DFS和BFS遍历输出图的结构。

Answer 1

看看符不符合

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MaxVertexNum 100  
#define MaxSize 10 
//顶点数目的最大值 
bool visitedBFS[MaxVertexNum];//用于广度优先遍历的访问标记数组 
bool visited[MaxVertexNum];//用于深度优先遍历的访问标记数组 
typedef  char VertexType;//顶点数据类型
typedef int EdgeType;//带权图中边上权值的数据类型 //这样写有便于数据类型的修改，就是在这修改数据类型就可以，低耦合 
//邻接表
//边表结点 
typedef struct ArcNode{
    EdgeType adjNode;
    ArcNode *next; 
}ArcNode; 
//顶点表结点 
typedef struct VNode{
    VertexType data;
    ArcNode *first;
}VNode,AdjList[MaxVertexNum];
//图 
typedef struct ALGraph{
    AdjList vertices;
    int vexnum,arcnum;//顶点数弧数 
}ALGraph;
 
//创建有（无）向图 
void createGraph(ALGraph &g){
    printf("请输入顶点数和边数：");
    int n,m;
    scanf("%d%d",&n,&m);
    g.vexnum=n;
    g.arcnum=m;
    for(int i=0;i<g.vexnum;i++){//初始化顶点 
        g.vertices[i].data=i;
        g.vertices[i].first=NULL; 
    }
    printf("请输入边的信息(顶点是0~n-1)\n");
    int x,y;
    for(int i=0;i<g.arcnum;i++){
        scanf("%d%d",&x,&y);
        ArcNode *p =(ArcNode*)malloc(sizeof(ArcNode));
        p->adjNode=y;//将y录入边表，比如<1,2>将2录入边表 
        p->next=g.vertices[x].first;//将该边表结点的next域指向顶点表结点的first域
        g.vertices[x].first=p;//将顶点表的first域指向p 
        //如果是无向图的话应该把<y,x>也存储起来
        ArcNode *q=(ArcNode*)malloc(sizeof(ArcNode));
        q->adjNode=x;
        q->next=g.vertices[y].first;
        g.vertices[y].first=q;
    
    }
} 
 
//深度优先遍历图,从第v个顶点开始遍历 
void DFS_Graph(ALGraph g,int v){
    visited[v]=true;
    printf("%d  ",g.vertices[v].data); 
    ArcNode *p=g.vertices[v].first;
    int w;
    while(p!=NULL){
        w=p->adjNode;
        if(!visited[w]){
            DFS_Graph(g,w);//递归深度遍历 
        }
        p=p->next;
    }
} 
 
//广度优先遍历
//借助队列
//从v开始遍历 
void BFS_Graph(ALGraph g,int v){
    visitedBFS[v]=true;
    ArcNode *p;
    printf("%d  ",g.vertices[v].data);
    int que[MaxSize];
    int front=0,rear=0;
    rear=(rear+1)%MaxSize;
    que[rear]= v;
    int j;
    while(rear!=front){//当队列不空的时候 
        
        front=(front+1)%MaxSize;//出队 
        j =que[front];
        p =g.vertices[j].first;
        while(p!=NULL){
            if(!visitedBFS[p->adjNode]){//如果 是未被访问结点就入队，以便访问该层结点的下层结点 
            
                printf("%d  ",g.vertices[p->adjNode].data);
                visitedBFS[p->adjNode]=true;
                rear=(rear+1)%MaxSize;
                que[rear]=p->adjNode; 
            }
            p=p->next;//用的是邻接表，用p-next就可访问同层的相邻结点 
            
        }
        
    }
     
 
} 
  
int main(){
    ALGraph g;
    createGraph(g);
    printf("深度优先遍历顺序：\n"); 
    DFS_Graph(g,2); 
    printf("\n广度优先遍历顺序：\n");
    BFS_Graph(g,0); 
    
}