DFS BFS代码
#define maxnum 30
#include<bits_stdc++.h>
int visited[maxnum]={0};
using namespace std;
typedef struct bian//邊
{
??? int mark;//標記是否搜索
??? int ivex,jvex;//兩頂點位置
??? bian *ilink,*jlink;//指向兩頂點的其他邊
??? int info;//信息
} bian,*pbian;
typedef struct dian//點
{
??? char name;
??? bian *first;//指向邊
} dain;
typedef struct graph//圖
{
??? dian dj[maxnum];
} graph;
typedef struct//隊列
{
??? int base[maxnum];
??? int f;//front
??? int r;//rear
}que;
void initq(que &q)//初始化隊列
{
??? q.f=q.r=0;
}
void enq(que &q,int e)//隊尾插入
{
??? q.base[q.r]=e;
??? q.r=q.r+1;
}
void deq(que &q,int &e)//隊頭刪除
{
??? e=q.base[q.f];
??? q.f=q.f+1;
}
int getlc(graph &g,char c,int n)//將頂點信息轉化為位置
{
??? for(int i=0; i<n; i++)
??????? if(c==g.dj[i].name)
????? return i;
}
void creatgraph(graph &g,int &n)//圖的創建
{
??? int k,m;
??? cout<<"請輸入圖頂點個數:"<<endl;
??? cin>>n;
??? cout<<endl<<"請輸入頂點信息（名稱）:"<<endl;
??? for(k=0; k<n; k++)
??? {
??????? cin>>g.dj[k].name;
??????? g.dj[k].first=NULL;
??? }
??? cout<<endl<<"請輸入邊個數:"<<endl;
??? cin>>m;
??? char a,b;
?? int mark,i,j;
?? pbian p1,p2;
??? cout<<endl<<"請輸入邊關系:"<<endl;
??? for(k=0; k<m; k++)
??? {
??????? cin>>a>>b;
??????? i=getlc(g,a,n);
??????? j=getlc(g,b,n);
??????? p1=(pbian)malloc(sizeof(bian));
??????? p1->ivex=i;
??????? p1->jvex=j;
??????? p1->ilink=NULL;
??????? p1->jlink=NULL;
??????? p2=g.dj[i].first;
??????? if(p2==NULL)
????? ??? g.dj[i].first=p1;
??????? else
??????? {
??????????? mark=0;
??????????? while(mark==0)
? ??????????{
??????????????? if(p2->ivex==i&&p2->ilink==NULL) mark=1;
??????????????? else if(p2->jvex==i&&p2->jlink==NULL) mark=2;
??????????????? else if(p2->ivex==i) p2=p2->ilink;
??????????????? else p2=p2->jlink;
??????????? }
??????????? if(mark==1) p2->ilink=p1;
??????????? else p2->jlink=p1;
??????? }
??????? p2=g.dj[j].first;
??????? if(p2==NULL)
??????????? g.dj[j].first=p1;
??????? else
??????? {
??????????? mark=0;
??????????? while(mark==0)
??????????? {
??????????????? if(p2->ivex==j&&p2->ilink==NULL) mark=1;
??????????????? else if(p2->jvex==j&&p2->jlink==NULL) mark=2;
??????????????? else if(p2->ivex==j) p2=p2->ilink;
??????????????? else p2=p2->jlink;
??????????? }
??????????? if(mark==1) p2->ilink=p1;
??????????? else p2->jlink=p1;
??????? }
?? }
}
void disp(graph &g,int n)//顯示對應關系
{
??? cout<<"位置???? 名稱"<<endl;
??? for(int i=0; i<n; i++)
??????? cout<<i<<"??????? "<<g.dj[i].name<<endl;
}
void visit(graph &g,int v)//visit 函數
{
??? cout<<g.dj[v].name;
??? visited[v]=1;
}
void dfs(graph &g,int i)//dfs
{
??? if(visited[i]==0)
??? visit(g,i);
??? bian *p;
??? p=g.dj[i].first;
??? if(p==NULL)return ;
??? else
??? {
??????? int m=0;
??????? while(m==0)
??????? {
??????????? if(p->ivex==i)
??????????? {
??????????????? if(visited[p->jvex]==0)
???????? ???????{
??????????????????? dfs(g,p->jvex);
??????????????? }
??????????????? if(p->ilink==NULL)m=1;
??????????????? else p=p->ilink;
??????????? }
??????????? else
??????????? {
??????????????? if(visited[p->ivex]==0)
??????????????? {
????????????????? ??dfs(g,p->ivex);
??????????????? }
??????????????? if(p->jlink==NULL)m=1;
??????????????? else p=p->jlink;
??????????? }
??????? }//while
??? }//else
}
void bfs(graph &g)//bfs
{
??? int i,u;
??? bian *t;
??? cout<<"請輸入開始遍歷的點:"<<endl;
??? cin>>i;
??? que q;//隊列q
??? initq(q);
??? if(visited[i]==0)
??????? {
??????????? visit(g,i);
??????????? enq(q,i);
??????? }
??????????? while(q.f!=q.r)//隊不空
??????????? {
??????????? deq(q,u);
??????????? t=g.dj[u].first;
??????????? if(t==NULL)return;
??????????? int m=0;
??????????? while(m==0)
??????????? {
????????????? if(t->ivex==u)
????????????? {
??????????????? if(visited[t->jvex]==0)
??????????????? {
??????????????????? visit(g,t->jvex);
??????????????????? enq(q,t->jvex);
??????????????? }
??????????????? if(t->ilink==NULL)m=1;
??????????????? else t=t->ilink;
???????????? }
????????????? else
????????????? {
??????????????? if(visited[t->ivex]==0)
??????????????? {
??????????????????? visit(g,t->ivex);
??????????????????? enq(q,t->ivex);
??????????????? }
??? ????????????if(t->jlink==NULL)m=1;
??????????????? else t=t->jlink;
????????????? }
??????????? }//while
??????????? }//while
}
void clearr()
{
??? for(int i=0;i<maxnum;i++)
??? {
??????? visited[i]=0;
??? }
}
int main()
{
??? graph g;
??? int t=0;
??? int n;
??? creatgraph(g,n);
?? disp(g,n);
??? while(t!=3)
??? {
??????? cout<<endl<<"請選擇遍歷方式(1:DFS,2:BFS,3:QUIT):"<<endl;
??????? cin>>t;
??????? if(t==1)
??????? {
??????????? dfs(g,0);
??????????? clearr();
??????? }
??????? else if(t==2)
??????????? {
????? ??????????bfs(g);
??????????????? clearr();
??????????? }
??????? else if(t==3)
?????????? break;
??? }
??? return 0;
}
?
轉載于:https://www.cnblogs.com/wander-clouds/p/8443740.html
創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎總結
- 上一篇： 查看Redis集群所有节点内存工具
- 下一篇： 机器学习中的Bias、Variance