关于数据结构:构造无向图及广度优先遍历连通图邻接矩阵非递归循环队列

35次阅读

共计 1724 个字符,预计需要花费 5 分钟才能阅读完成。

#include <iostream>
using namespace std;
#define MVNum 100                       
#define MAXQSIZE 100                                    
typedef char VerTexType;                      
typedef int ArcType;                      
bool visited[MVNum];                       
typedef struct{VerTexType vexs[MVNum];                
    ArcType arcs[MVNum][MVNum];              
    int vexnum,arcnum;                        
}Graph;
typedef struct{
    ArcType *base;                            
    int front;                                
    int rear;                            
}sqQueue;
void InitQueue(sqQueue &Q){Q.base = new ArcType[MAXQSIZE];
    if(!Q.base)     exit(1);                
    Q.front = Q.rear = 0;
}
void EnQueue(sqQueue &Q, ArcType e){if((Q.rear + 1) % MAXQSIZE == Q.front)
        return;
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXQSIZE;
}
bool QueueEmpty(sqQueue Q){if(Q.rear == Q.front)
        return true;
    return false;
}
void DeQueue(sqQueue &Q, ArcType &u){u = Q.base[Q.front];
    Q.front = (Q.front + 1) % MAXQSIZE;
}                                 
int LocateVex(Graph G , VerTexType v){for(int i = 0; i < G.vexnum; ++i)
        if(G.vexs[i] == v)
            return i;
        return -1;
}
// 创立无向图 
void CreateUDG(Graph &G){ 
    int i , j , k;
    cout <<"总顶点数 总边数:";
    cin >> G.vexnum >> G.arcnum;                            
    for(i = 0; i < G.vexnum; ++i){cout << "第" << (i+1) << "个点的名称:";
        cin >> G.vexs[i];                                
    }    
    for(i = 0; i < G.vexnum; ++i)                            
        for(j = 0; j < G.vexnum; ++j)   
            G.arcs[i][j] = 0;  
    for(k = 0; k < G.arcnum;++k){                        
        VerTexType v1 , v2;
        cout << "第" << (k + 1) << "条边附丽的顶点:";
        cin >> v1 >> v2;                                    
        i = LocateVex(G, v1);  j = LocateVex(G, v2);        
        G.arcs[j][i] = G.arcs[i][j] = 1;                
    }
}
int FirstAdjVex(Graph G , int v){
    int i;
    for(i = 0 ; i < G.vexnum ; ++i){if(G.arcs[v][i] == 1 && visited[i] == false)
            return i;
    }
    return -1;
}
int NextAdjVex(Graph G , int u , int w){
    int i;
    for(i = w ; i < G.vexnum ; ++i){if(G.arcs[u][i] == 1 && visited[i] == false)
            return i;
    }
    return -1;
}
// 广度优先遍历
void BFS (Graph G, int v){ 
    sqQueue Q;
    ArcType u;
    ArcType w;
    cout << G.vexs[v];    visited[v] = true;                          
    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 << G.vexs[w];   visited[w] = true;                
                EnQueue(Q, w);                                                
            }
        }
    }
}
int main(){
    Graph G;
    CreateUDG(G);
    cout << "遍历无向图的起始点:";
    VerTexType c;
    cin >> c;
    int i;
    for(i = 0 ; i < G.vexnum ; ++i){if(c == G.vexs[i])
            break;
    }
    cout << "广度优先搜寻遍历无向图:";
    BFS(G , i);
    return 0;
}

正文完
 0