邻接矩阵为存储结构 | 实现图的深度、宽度优先遍历

mGraph.cpp：

#include <iostream>
#include<stdio.h>
#include<stdlib.h>
#include "Queue.h"

using namespace std;

typedef int ElemType;
typedef struct{
    ElemType noEdge;                    //两顶点间没有边时的值
    int e;                             //当前边数
    int n;                              //当前顶点数
    ElemType **a;
}mGraph;                              //邻接矩阵的结构体

ElemType Init(mGraph *mg,int nSize,int noEdgeValue){        //初始化函数
    int i,j;
    mg->noEdge = noEdgeValue;
    mg->n = nSize;
    mg->e = 0;              //初始化时没有边
    mg->a = (ElemType **)malloc(sizeof(ElemType *)*nSize);           //生成长度为n的一位指针数组
    if(!mg->a){
        cout<<"Run out of Memory!"<<endl;
        return 0;
    }
    for(i=0;i<mg->n;i++){
        mg->a[i] = (ElemType *)malloc(sizeof(ElemType)*(mg->n));
        for(j=0;j<mg->n;j++){
        mg->a[i][j] = mg->noEdge;
        }
        mg->a[i][i] = 0;
    }
    return 0;
}

void Destroy(mGraph *mg){                   //释放内存函数
    int i;
    for(i=0;i<mg->n;i++){
        free(mg->a[i]);
    }
    free(mg->a);
}

ElemType Exist(mGraph *mg,int u,int v){                             //查询是否有该边
    if(u==v||mg->a[u-1][v-1]==mg->noEdge||u<1||v<1||u>mg->n||v>mg->n){
        cout<<"Not Exist!"<<endl;
        return 0;
        };
        cout<<"Exist!"<<endl;
        return 0;
}

ElemType Insert(mGraph *mg,int u,int v,int w){              //插入边函数、变量u是行号，v是列号，w是边的权重
    if(u<1||v<1||u>mg->n||v>mg->n||u==v){
        cout<<"Not Exist!"<<endl;
        return 0;
        }
    if(mg->a[u-1][v-1] !=mg->noEdge){
        cout<<"Dumplicate!"<<endl;
        return 0;
    }
    mg->a[u-1][v-1] = w;
    mg->e++;
    return 0;
}

ElemType Delete(mGraph *mg,int u,int v)                 //删除边
{
    if(u==v||mg->a[u-1][v-1]==mg->noEdge||u<1||v<1||u>mg->n||v>mg->n){
        cout<<"Not Exist!"<<endl;
        return 0;
    }
    else{
        mg->a[u-1][v-1] =mg->noEdge;
        mg->e--;
    }
    return 0;
}

void Print(mGraph *mg){                             //显示矩阵的函数
    int i,j;
    for(i=0;i<mg->n;i++){
        for(j=0;j<mg->n;j++){
            cout<<mg->a[i][j]<<" ";
        }
        cout<<endl;
    }

}

void DFS(int v,int *visited,mGraph mg)
{
    visited[v]=true;
    cout<<v+1<<" ";
    for(int i=0;i<mg.n;i++)
        if(mg.a[v][i]!=mg.noEdge&&mg.a[v][i]!=0&&!visited[i])
            DFS(i,visited,mg);
}

void DFS(mGraph mg){
    int i;
    int *visited = (int *)malloc(mg.n*sizeof(int));
    for(int i=0;i<mg.n;i++)
        visited[i]= 0;                  //预设所有结点均未被访问过
    for(i=0;i<mg.n;i++)
        if(!visited[i])
            DFS(i,visited,mg);
    delete []visited;
}

void BFS(int v,int *visited,mGraph mg)
{
    Queue q;
    Create(&q,mg.n);
    visited[v]=true;
    cout<<v+1<<" ";
    Insert(&q,v);
    while(!isEmpty(&q))
    {
        Front(&q,&v);
        Extract(&q);
        for(int i=0;i<mg.n;i++)
            if(mg.a[v][i]!=mg.noEdge&&mg.a[v][i]!=0&&!visited[i])
            {
                visited[i]=true;
                cout<<i+1<<" ";
                Insert(&q,i);
            }
    }
}

void BFS(mGraph mg)
{
    int i;
    int *visited = (int *)malloc(mg.n*sizeof(int));
    for(int i=0;i<mg.n;i++)
        visited[i] = 0;                  //预设所有结点均未被访问过
    for(i=0;i<mg.n;i++)
        if(!visited[i])
            BFS(i,visited,mg);
    delete []visited;
}



int main()
{
    int p1,p2;
    mGraph a;
    cout<<"Initialising..."<<endl;
    Init(&a,5,0);                       //初始化
    Print(&a);
    cout<<endl;
    cout<<"Inserting..."<<endl;
    Insert(&a,1,2,1);                      //插入
    Insert(&a,1,5,2);
    Insert(&a,4,3,3);
    Insert(&a,5,2,4);
    Insert(&a,5,4,5);
    Print(&a);
    cout<<endl<<"Depth first Searching..."<<endl;
    DFS(a);
    cout<<endl<<endl;
    cout<<endl<<"Breadth first Searching..."<<endl;
    BFS(a);
    cout<<endl<<endl;
    cout<<"Which edge do you want to search for?"<<endl;            //找边
    cin>>p1>>p2;
    Exist(&a,p1,p2);
    cout<<endl;
    cout<<"Which edge do you want to delete?"<<endl;                //删边
    cin>>p1>>p2;
    Delete(&a,p1,p2);
    Print(&a);
    cout<<endl<<"Destroying..."<<endl;                              //释放内存
    Destroy(&a);
    cout<<"Finished! Bye~~"<<endl;
    return 0;
}

Queue.cpp：

#include <iostream>
#include <stdlib.h>
#include <windows.h>
#include "Queue.h"
using namespace std;

/*
typedef int ElemType;
typedef struct{
    int front;          //指向队头元素的前一单元的下标位置
    int rear;           //指向队尾元素的下标位置
    int maxSize;        //表示队列中最多所允许存储的元素数量
    ElemType *element;  //存储队列元素一维数组首地址指针
}Queue;                 //队列结构型
*/

void Create(Queue *q,int max){      //创建一个能容纳max个单元的空队列
    q->front = 0;
    q->rear = 0;
    q->maxSize = max;
    q->element = (ElemType *)malloc(sizeof(ElemType)*max);
}

BOOL isFull(Queue *q){              //判断队列是否已满
    if((q->rear+1)%(q->maxSize) == q->front){
        cout<<"The queue is Full!"<<endl;
        return true;
    }
    else
        return false;
}

void Insert(Queue *q,ElemType x){               //在队尾插入元素
    if(!isFull(q)){
    q->rear = (q->rear + 1)%q->maxSize;         //key code
    q->element[q->rear] = x;
    }
    else
        cout<<"Insertion Failed!"<<endl;
}

BOOL isEmpty(Queue *q){                         //判断队列是否为空
    if(q->front == q->rear){
       // cout<<"Empty!"<<endl;
        return true;
    }
    else
        return false;
}

void Front(Queue *q,ElemType *x){                           //获取队头元素
    if(!isEmpty(q)){
        *x = q->element[(q->front+1)%q->maxSize];
    }
    else
        cout<<"There is no Front element!"<<endl;
}

void Print(Queue *q){                           //打印队列
    int i;
    for(i=q->front+1;i<=q->rear;i++){
            cout<<q->element[i]<<endl;
    }

}

void Extract(Queue *q){             //注意出队只能出队头
    if(!isEmpty(q)){
        q->front = (q->front+1)%q->maxSize;
    }
    else
        cout<<"Extraction failed!"<<endl;
}

void Clear(Queue *q){       //清空队列元素，但不释放空间
    q->front = q->rear = 0;
}

void Destroy(Queue *q){                         //释放队列空间
    q->maxSize = -1;
    q->front = q->rear = -1;
    free(q->element);
}
/*
int main(){
    int i;
    Queue q;
    Create(&q,5);
    cout<<"Queue Created!"<<endl;
    cout<<"Inserting..."<<endl;
    for(i=0;i<q.maxSize;i++){
        Insert(&q,i);
    }
    Print(&q);
    cout<<"Insertion Finished!"<<endl;
    cout<<"Now! lets look at the front element!"<<endl;
    Front(&q);
    cout<<"Now! Please extract the front element!"<<endl;
    Extract(&q);
    Print(&q);
    cout<<"Now! lets Clear the queue!"<<endl<<endl;
    Clear(&q);
    cout<<"Cleared queue has shown...."<<endl;
    cout<<"Destroy and Free the memory please..."<<endl;
    Destroy(&q);
    cout<<"Destroyed! Bye~~"<<endl;
    return 0;
}
*/

Queue.h：

#include <windows.h>
typedef int ElemType;
typedef struct{
    int front;          //指向队头元素的前一单元的下标位置
    int rear;           //指向队尾元素的下标位置
    int maxSize;        //表示队列中最多所允许存储的元素数量
    ElemType *element;  //存储队列元素一维数组首地址指针
}Queue;                 //队列结构型

void Create(Queue *q,int max);
void Insert(Queue *q,ElemType x);
BOOL isEmpty(Queue *q);
void Front(Queue *q,ElemType *x);
void Print(Queue *q);
void Extract(Queue *q);
void Clear(Queue *q);
void Destroy(Queue *q);