学步园

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