数据结构实验10

本博文来源于学校课堂实验，实验内容是：编程实现图的创建（基于邻接矩阵）和两种搜索算法，输出顶点序列

如果要BFS那就吧dfs注释掉，如果dfs那就把BFS注释掉

8 10
0 5 1
0 7 1
0 2 1
1 7 1
2 6 1
3 5 1
3 4 1
4 5 1
4 6 1
4 7 1

答案图省事共分为三个部分，BFS、DFS和队列和图，

#include
#include
#define MaxVertexNum 10
#define false 0
#define true 1
#define ERROR -1
typedef int WeightType;
typedef int DataType;
typedef struct GNode *PtrToGNode;
typedef int Position;
typedef int ElementType;
int Visited[MaxVertexNum]={false};
struct GNode {
    int Nv;  //一张图的顶点数
    int Ne; //一张图的边数
    WeightType G[MaxVertexNum][MaxVertexNum];
    DataType Data[MaxVertexNum];//存顶点的数据
};
typedef PtrToGNode MGraph;//以邻接矩阵存储的图类型

//初始化一个有VertexNum 个顶点但没有边的图
typedef int Vertex;//用顶点下标表示顶点，为整型
MGraph CreateGraph(int VertexNum)
{
    Vertex V, W;
    MGraph Graph;

    Graph = (MGraph)malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;

    //注意：这里默认顶点编号从0开始，到(Graph->Nv-1)
    for(V=0; VNv;V++)
        for(W=0; WNv;W++)
            Graph->G[V][W] = 0;
    for(int i =0;iNv;i++)
    {
        Visited[i]=false;
        Graph->Data[i]=i;
    }
    return Graph;

}
typedef struct ENode *PtrToENode;
struct ENode {
    Vertex V1,V2;//有向边
    WeightType Weight;//权值
};
typedef PtrToENode Edge;

struct QNode{
    ElementType *Data;
    int rear;
    int front;
    int MaxSize;
};
typedef struct QNode *Queue;

Queue CreateQueue(int MaxSize){
    Queue Q = (Queue)malloc(sizeof(struct QNode));
    Q->Data = (ElementType *) malloc(MaxSize * sizeof(ElementType));
    Q->front = Q->rear = 0;
    Q->MaxSize = MaxSize;
    return Q;

}
int IsFullQ(Queue Q){

    return ((Q->rear+1)%Q->MaxSize == Q->front);
}
void AddQ(Queue Q,ElementType item){
    if(IsFullQ(Q)){
        printf("Queue is fulln");
        return ;
    }
    Q->rear = (Q->rear+1) %Q->MaxSize;
    Q->Data[Q->rear] = item;
}
int IsEmptyQ(Queue Q){
    return (Q->front == Q->rear);
}
ElementType DeleteQ(Queue Q){
    if(IsEmptyQ(Q))
    {
        printf("Queue is emptyn");
        return ERROR;

    }else{
        Q->front = (Q->front+1)%Q->MaxSize;
        return Q->Data[Q->front];
    }
}
void InsertEdge(MGraph Graph, Edge E)
{
    Graph->G[E->V1][E->V2] = E->Weight;
    Graph->G[E->V2][E->V1] = E->Weight;
}
void BFS(MGraph Graph,Vertex S)
{
    Queue Q;
    Vertex V,W;
    Q = CreateQueue(MaxVertexNum);
    printf("%d->",Graph->Data[S]);
    Visited[S]=true;
    AddQ(Q,S);
    while(!IsEmptyQ(Q)){
        V = DeleteQ(Q);
        for(W=0;WNv;W++)
        {
            if(Graph->G[V][W]==1&&!Visited[W]){
                printf("%d-> ",Graph->Data[W]);
                Visited[W]=true;
                AddQ(Q,W);
            }
        }
    }

}
void BFStraverse(MGraph Graph)
{
    for(int i=0;iNv;i++){
        if(!Visited[i])
            BFS(Graph,i);
    }
}

typedef struct ENode *PtrToENode;

void DFS(MGraph Graph,int i)
{
    int j;
    Visited[i]=true;   //被访问的标记
    printf("%d->",Graph->Data[i]);
    for(int j=0;jNv;j++)
    {
        if(Graph->G[i][j]==1&&!Visited[j])   //边(i,j)存在且j顶点未被访问，递归
            DFS(Graph,j);
    }
}

//深度优先遍历
void DFStraverse(MGraph Graph)
{
    for(int i=0;iNv;i++){
        if(!Visited[i])
            DFS(Graph,i);
    }
}
MGraph BuildGraph()
{

    MGraph Graph;
    Edge E;
    Vertex V;
    int Nv,i;
    scanf("%d",&Nv);
    Graph = CreateGraph(Nv);
    scanf("%d",&(Graph->Ne));
    if(Graph->Ne != 0) {
        E = (Edge)malloc(sizeof(struct ENode));
        for(i=0;iNe;i++) {
            scanf("%d %d %d",&E->V1,&E->V2,&E->Weight);
            InsertEdge(Graph, E);
        }

    }
    
    return Graph;
}



int main()
{
    MGraph Graph = BuildGraph();
    int Nv = Graph->Nv;
    DFStraverse(Graph);
    printf("n");
    BFStraverse(Graph);
    return 0;
}