邻接矩阵、邻接表存储结构 遍历算法和图的广度优先搜索遍历

一、  实验内容

1）掌握图的邻接矩阵、邻接表存储结构表示及其创建算法

2）掌握图的深度优先搜索遍历算法和图的广度优先搜索遍历算法；

4）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；

二、  源程序

#include<iostream>
#include<string>

using namespace std;
#define OK 1
#define OVERFLOW -1
#define ERROR 0
#define MAXSIZE 100
int typedef Status;
//邻接矩阵存储
#define MaxInt 32767
#define MVNum 100
typedef char VerTexType;
typedef int ArcType;
typedef struct//邻接矩阵存储定义
{
    VerTexType vexs[MVNum];//char
    ArcType arcs[MVNum][MVNum];
    int vexnum, arcnum;
}AMGraph;
typedef struct
{
    int data[MAXSIZE];
    int front;        /* 头指针 */
    int rear;        /* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
}Queue;
Status DeQueue(Queue &Q, int &e){
    if (Q.front == Q.rear)return ERROR;
    e = Q.data[Q.front];
    Q.front = (Q.front + 1) % MAXSIZE;
    return OK;
}
int LocateVex(const AMGraph &g, const VerTexType &v)
{
    int i = 0;
    for (i = 0; i < g.vexnum; i++)
    {
        if (g.vexs[i] == v)
            break;
    }    if (i > g.vexnum)
    {
        fprintf(stderr, "no such vertex.\n");
        return -1;
    }
    return i;
}
Status InitQueue(Queue Q)
{
    Q.front = 0;
    Q.rear = 0;
    return  OK;
}
Status QueueEmpty(Queue Q)
{
    if (Q.front == Q.rear) /* 队列空的标志 */
        return true;
    else
        return false;
}
Status EnQueue(Queue Q, int e)
{ 
    if ((Q.rear + 1) % MAXSIZE == Q.front)        
    return ERROR;    Q.data[Q.rear] = e;            
    Q.rear = (Q.rear + 1) % MAXSIZE;    
    return  OK;
}

int FirstAdjVex(AMGraph &G, int &v)
{
    int i, j = 0, k;
    k = LocateVex(G, v);//k为顶点v在图G中的序号
    for (i = 0; i<G.vexnum; ++i)
    {
        if (G.arcs[k][i]!= j)
        {
            return i;
        }
    }
    return -1;
}
int NextAdjVex(AMGraph &G, int &v, int &w)
{
    int i, j = 0, k1, k2;
    k1 = LocateVex(G, v);//k1为顶点v在图G中的序号
    k2 = LocateVex(G, w);//k2为顶点w在图G中的序号
    
    for (i = k2 + 1; i<G.vexnum; ++i)
    {
        if (G.arcs[k1][i] != j)
        {
            return i;
        }
    }
    return -1;
}

Status CreateUDN(AMGraph &G)//邻接矩阵创建无向图
{
    int i = 0, j = 0,k=0,v1=0,v2=0,w=0;
    cout << "请输入总顶点数，总边数" << endl;
    cin >> G.vexnum >> G.arcnum;//当前点数，边数
    for ( i = 0; i < G.vexnum; ++i){
        cout << "输入点信息" << endl;
        cin >> G.vexs[i];//名字
    }
    for (i = 0; i < G.vexnum; ++i)
    {
        for (j = 0; j < G.vexnum; ++j){
            G.arcs[i][j] = MaxInt;
        }
    }
    for (k = 0; k < G.arcnum; ++k){
        cin >> v1 >> v2 >> w;
        i = LocateVex(G, v1); j = LocateVex(G, v2);
        G.arcs[i][j] = w;
        G.arcs[j][i] = G.arcs[i][j];
    }
    return OK;
}

bool visited[MVNum];
void DFS_AM(AMGraph G, int v)//邻接矩阵深度优先搜索遍历
{//从第v个顶点出发深度优先搜索遍历
    int w = 0;
    cout << v << endl; visited[v] = true;
    for (w = 0; w < G.vexnum; w++){
        if ((G.arcs[v][w] != 0) && (!visited[w]))
            DFS_AM(G, w);
    }
}


//广度优先
void BFS(AMGraph &G, int v){
    cout << v; visited[v] = true;
    Queue Q;
    Q.front = 0;
    int u, w;
    InitQueue(Q);
    EnQueue(Q, v);
    while (!QueueEmpty(Q)){
        DeQueue(Q, u);
        for (w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G,u,w)){
            if (!visited[w]){
                cout << w;
                visited[w] = true;
                EnQueue(Q, w);
            }
        }

    }

}





//邻接表
#define MVNum  100
//邻接表定义
typedef struct ArcNode{
    int adjvex;
    struct ArcNode *nextarc;
    int info;
}ArcNode;
typedef struct VNode{
    VerTexType data;
    ArcNode *firstarc;
}VNode,AdjList[MVNum];
typedef struct{
    AdjList vertices;
    int vexnum, arcnum;
}ALGraph;
int LocateVex(const ALGraph &g, const int &v)
{
    int i = 0;
    for (i = 0; i < g.vexnum; i++)
    {
        if (g.vertices[i].data == v)
            break;
    }    if (i > g.vexnum)
    {
        fprintf(stderr, "no such vertex.\n");
        return -1;
    }
    return i;
}

int FirstAdjVex(ALGraph &G, int &v)
{
    ArcNode * p;
    int v1;
    v1 = LocateVex(G, v);//v1为顶点v在图G中的序号
    p = G.vertices[v1].firstarc;
    if (p)
    {
        return p->adjvex;
    }
    else
    {
        return -1;
    }
}


//邻接表创建无向图
Status CreateUDG(ALGraph &G){
    int i = 0, j = 0, k = 0,v1,v2;
    cout << "输入总顶点数，总边数" << endl;
    for (i = 0; i < G.vexnum; ++i){
        cout << "输入顶点值" << endl;
        cin >> G.vertices[i].data;
        G.vertices[i].firstarc = NULL;

    }
    for (k = 0; k < G.arcnum; ++k){
        cout << "输入一条边依附的两个顶点" << endl;
        cin >> v1 >> v2;
        i = LocateVex(G, v1);
        j = LocateVex(G, v2);
        ArcNode *p1,*p2;
        p1 = new ArcNode;
        p2 = new ArcNode;
        p1->adjvex = j;
        p1->nextarc = G.vertices[i].firstarc; G.vertices[i].firstarc = p1;
        p2->adjvex = i;
        p2->nextarc = G.vertices[j].firstarc; G.vertices[j].firstarc = p2;

    }
    return OK;
}
void DFS_AL(ALGraph G, int v){
    cout << v; visited[v] = true;
    ArcNode *p;
    int w;
    p = G.vertices[v].firstarc;
    while (p != NULL){
        w = p->adjvex;
        if (!visited[w])DFS_AL(G, w);
        p = p->nextarc;
    }
}
int main(){
    AMGraph G1;
    CreateUDN(G1);
    DFS_AM(G1, 1);
    ALGraph G2;
    CreateUDG(G2);
    DFS_AL(G2, 1);
}