//这个程序是用邻接表建立一个图，然后再进行深度优先搜索， //我已经验证过建立图的程序没有什么错误，我怀疑可能是 //DFS()函数有问题，但是我也没有发现出什么问题，希望能够帮我看一下程序 #include"iostream.h" #include"malloc.h" #include"stdio.h" #include"stdlib.h" #define OK 1 #define ERROR -1 #define OVERFLOW -2 #define Null 0 #define MAX_VERTEX_NUM 20 typedef char Vertextype;//char类型 typedef struct ArcNode{//边结点 int adjvex; struct ArcNode *nextarc;//下一个结点 }ArcNode; typedef struct VNode{//顶点结点 Vertextype date;//图的顶点名 ArcNode *first; }VNode,Adjlist[MAX_VERTEX_NUM]; typedef struct {//以图的邻接表存储图 Adjlist vertices; int vexnum,arcnum;//顶点数和边数 }ALGraph; int visited[MAX_VERTEX_NUM];//访问数组标志 //.................................. //.................................... //.................................//找到输入顶点的位置 int Locatnode(Adjlist L,Vertextype node)//确定输入点在图中的位置 { int i=0; while(L[i].date !=node) i++; return i; }

CreatGraph(ALGraph &G) {//用邻接表存储一个图 cout<<"请输入图顶点的个数："<<endl; cin>>G.vexnum; cout<<"输入顶点："<<endl; int i; ArcNode *p; for(i=0;i<G.vexnum;i++)//对图进行初试化 { cin>>G.vertices[i].date;//输入顶点 p=(ArcNode*)malloc(sizeof(ArcNode));//建立带有带有头结点的邻接链表 p->nextarc=Null; G.vertices[i].first=p; } //输入邻接顶点 cout<<"输入边的个数："<<endl; cin>>G.arcnum;//输入边数 int k,j; char ch1,ch2; ArcNode *q; for(i=0;i<G.arcnum;i++)//建立邻接表 { cout<<"请输入邻接的两个顶点："<<endl; cin>>ch1>>ch2; k=Locatnode(G.vertices,ch1); j=Locatnode(G.vertices,ch2); p=G.vertices[k].first;//创建另一个以j为顶点的链表， q=(ArcNode*)malloc(sizeof(ArcNode)); q->adjvex=j;//将与k顶点相邻的顶点j输入 q->nextarc=p->nextarc;//在头结点与第一个顶点间插入元素 p->nextarc=q; //创建另一个以j为顶点的链表 p=G.vertices[j].first; q=(ArcNode*)malloc(sizeof(ArcNode)); q->adjvex=k;//将与k顶点相邻的顶点j输入 q->nextarc=p->nextarc;//在头结点与第一个顶点间插入元素 p->nextarc=q; } for(i=0;i<G.vexnum;i++)//初始化访问数组 visited[i]=false; } ArcNode *q;//定义一个变量 void DFS(ALGraph G,int i) //从第i个顶点遍历连通图 { visited[i]=true; cout<<G.vertices[i].date; for(q=G.vertices[i].first->nextarc;q;q=q->nextarc) { if(!visited[q->nextarc->adjvex]) DFS(G,q->adjvex); } } //。........................................... //.......................................... OUTGraph(ALGraph G)//从第一个顶点将图的邻接表输出 {int i; for(i=0;i<G.vexnum;i++) {cout<<G.vertices[i].date<<" "; for(q=G.vertices[i].first->nextarc;q;q=q->nextarc)

cout<<G.vertices[p->adjvex].date<<' '; cout<<endl; } } //。。。。。。。。。。。。。。。。。。。。。。。。。。。。 //。。。。。。。。。。。。。。。。。。。。。。。。。。。 void main() {ALGraph G; CreatGraph(G); DFS(G,0);//从第一个顶点遍历图，是连通图将整个土输出 }

#include<iostream.h> #include<stdio.h> #define maxsize 10 struct edge//边 { int adjvex;//下标 edge *next; }; struct node//顶点 { char data; edge *fedge; }; struct graph { node edgelist[maxsize]; int n; int e; }; struct qunode { int data; qunode *next; }; struct queue { qunode *front; qunode *rear; };

void initqueue(queue *qu) { qu->front=qu->rear=NULL; }

void enterqu(queue *qu,int v) { qunode *s=new qunode; s->data=v; if(!qu->rear) qu->front=qu->rear=s; else { qu->rear->next=s; qu->rear=s; } }

int outqu(queue *qu) { qunode *out; if(qu->front==qu->rear) { out=qu->front; qu->rear=qu->front=NULL; } else { out=qu->front; qu->front=qu->front->next; } return out->data; }

graph * create(graph *g) { int i,j; g=new graph; cout<<"输入顶点数:"; cin>>g->n; cout<<"边数:"; cin>>g->e; cout<<endl; for(i=1;i<=g->n;i++)//初始化图 { cout<<"输入顶点"<<i<<"的标记:"; cin>>g->edgelist[i].data; g->edgelist[i].fedge=NULL; } for(int k=0;k<g->e;k++) { cout<<"(i>=1)输入边(i,j):"; cin>>i>>j;//i begin node,j end node edge *s=new edge; s->adjvex=j; s->next=g->edgelist[i].fedge; g->edgelist[i].fedge=s; edge *r=new edge;//...........有向图 r->adjvex=i; r->next=g->edgelist[j].fedge; g->edgelist[j].fedge=r; } return g; }

void DFS(graph *g,int v,bool visited[])//从第v个顶点开始遍历 { cout<<g->edgelist[v].data<<" "; visited[v]=true; edge *p=g->edgelist[v].fedge; while(p) { if(visited[p->adjvex]==false) DFS(g,p->adjvex,visited); p=p->next; } } void DFSTraverse(graph *g,bool visited[])//深度优先遍历 { int k; for(int i=1;i<maxsize;i++) visited[i]=false; cout<<"输入开始访问的顶点:"; cin>>k; cout<<"深度优先遍历: "; cout<<g->edgelist[k].data<<" "; visited[k]=true; edge *p=g->edgelist[k].fedge; while(p)//第一层 { if(visited[p->adjvex]==false) DFS(g,p->adjvex,visited); p=p->next; } cout<<endl; }

void BFSTraverse(graph *g,bool visited[])//广度优先 { queue *qu=new queue; int v,k; initqueue(qu); for(int i=1;i<=g->n;i++) visited[i]=false; cout<<"输入开始访问的顶点:"; cin>>k; cout<<"广度优先遍历: "; cout<<g->edgelist[k].data<<" ";//从1开始进行遍历 visited[k]=true; enterqu(qu,k); while(qu->front!=NULL)//队列不空 { v=outqu(qu);//开始队中只有一个元素 edge *e=g->edgelist[v].fedge; while(e) { if(!visited[e->adjvex]) { cout<<g->edgelist[e->adjvex].data<<" "; visited[e->adjvex]=true; enterqu(qu,e->adjvex); } e=e->next; } } cout<<endl; }

void print(graph *g) { edge *p; cout<<"邻接表:"<<endl; for(int i=1;i<=g->n;i++) { cout<<i<<" "<<g->edgelist[i].data<<"=>"; p=g->edgelist[i].fedge; while(p) { cout<<"("<<p->adjvex<<","<<g->edgelist[p->adjvex].data<<")->"; p=p->next; } cout<<"^"<<endl; } }

void main() { bool visited[maxsize]; graph *g; g=create(g); print(g); DFSTraverse(g,visited); BFSTraverse(g,visited); }