#include <iostream> using namespace std; #define MAXNODE 64 // 图中顶点的最大个数 typedef char vertype; struct ArcNode // 弧（边）结点： { int adjvex; // 邻接点在顶点向量中的下标 ArcNode *next; // 指向下一邻接点的指针 }; struct VerNode // 顶点结点： { vertype vertex; // 顶点信息 ArcNode *firstarc; // 指向第一个邻接点的指针 }; struct AlGraph// 邻接表： { VerNode vertices[MAXNODE]; int vernum; //顶点的数目 int arcnum; // 边的数目 }; struct Queue//队列 { int elem; Queue *next; }; void QueueInit(Queue &Q) { Q.next=NULL; } void QueueIn(Queue &Q,int &v) { Queue *p=&Q; while(p->next) { p=p->next; } Queue *temp=new Queue; temp->elem=v; temp->next=p->next; p->next=temp; } bool QueueEmpty(Queue &Q) { if(Q.next) return true; else return false; } void QueueOut(Queue &Q,int &v) { Queue *temp; temp=Q.next; v=temp->elem; Q.next=temp->next; delete temp; } int GraphLocateVertex(AlGraph &G,int v) { return v-1; } void CreateAdjList(AlGraph &G)//此图为有向图 { int n; cout<<"请输入顶点数目"<<endl; cin>>n; G.vernum=n;//顶点初始化为n G.arcnum=0;//边数初始化为0 cout<<"请输入各个顶点的数据"<<endl; for(int i=0;i<n;i++) { cin>>G.vertices[i].vertex;//输入顶点信息 G.vertices[i].firstarc=NULL; } cout<<"请输入有联系的两顶点:输入方式如：第一个点和第二个点输入成：1 2"<<endl; int v1,v2; cin>>v1>>v2; int i,j; ArcNode *p=NULL; while(v1&&v2)//两顶点同时为0时结束 { i=GraphLocateVertex(G,v1); j=GraphLocateVertex(G,v2); p=new ArcNode(); p->adjvex=j; p->next=G.vertices[i].firstarc; G.vertices[i].firstarc=p; G.arcnum++;//边数加1 cin>>v1>>v2; } } int visited[MAXNODE];//访问标志数组 void visit(AlGraph &G,int v) { cout<<G.vertices[v].vertex<<" "; } //以下为深度优先遍历DFS int GraphFirstAdj(AlGraph &G,int v) { if(G.vertices[v].firstarc) return G.vertices[v].firstarc->adjvex; return -1; } int GraphNextAdj(AlGraph &G,int v,int w) { ArcNode *p=G.vertices[v].firstarc; while(p->adjvex!=w) { p=p->next; } p=p->next; if(p) return p->adjvex; else return -1; } void DFS(AlGraph &G,int v) { //从第v个顶点出发递归地深度优先遍历图G visited[v]=1; visit(G,v);//访问v顶点并将该顶点设为已访问 for(int w=GraphFirstAdj(G,v);w!=-1;w=GraphNextAdj(G,v,w))//-1退出 { if(!visited[w]) DFS(G,w);//对v的上文访问的邻接顶点w递归调用 } } void DFSTraverse(AlGraph &G) { for(int v=0;v<G.vernum;v++)//访问数组初始化 visited[v]=0; for(int v=0;v<G.vernum;v++) { if(!visited[v]) DFS(G,v);//对未访问的顶点调用DFS } } //以下为广度优先遍历BFS void BFSTraverse(AlGraph &G) { //广度优先遍历 for(int v=0;v<G.vernum;v++) visited[v]=0; Queue Q; QueueInit(Q);//辅助队列Q for(int v=0;v<G.vernum;v++) if(!visited[v]) { QueueIn(Q,v); visited[v]=1; visit(G,v); int u; while(!QueueEmpty(Q)) { QueueOut(Q,u);//对头元素出队列并置为u for(int w=GraphFirstAdj(G,u);w!=-1;w=GraphNextAdj(G,u,w)) { if(!visited[w]) { QueueIn(Q,w);//u的尚未访问的邻接顶点w入队列Q visited[w]=1; visit(G,w); } } } } } int main() { AlGraph G; CreateAdjList(G); DFSTraverse(G); cout<<endl; BFSTraverse(G); cout<<endl; cout<<G.vernum<<" "<<G.arcnum<<endl; cout<<endl; return 0; }
