#include <stdio.h> #include <stdlib.h> #include <queue> using namespace std; char vertex[20]; //深搜用栈,广搜用队列 typedef struct enode { //表结点 int nexttov; //相邻顶点 struct enode * nextedge; //相邻下一个表结点 }enode; typedef struct { //头结点 char vertex; //顶点信息 enode *firstedge; //第一条边(出度)/第一个表结点 }vnode; typedef struct { //图 int vnum,edgenum; vnode vnodestr[20]; //头结点信息数组 }graph; void creategraph(graph *g) { int i,from,to; enode *p,*pedge; printf("输入有向图顶点个数\n"); scanf("%d",&g->vnum); getchar(); printf("输入有向图顶点名字\n"); for(i=0;i<g->vnum;i++) { scanf("%c",&g->vnodestr[i].vertex); g->vnodestr[i].firstedge = NULL; //顶点的第一个表结点初始化空 } printf("输入有向图边个数\n"); scanf("%d",&g->edgenum); printf("输入有向图边信息\n"); printf("起点 终点\n"); for(i=0;i<g->edgenum;i++) { scanf("%d%d",&from,&to); pedge = (enode*)malloc(sizeof(enode)); //开空间给表结点 pedge->nextedge = NULL; pedge->nexttov = to; p = g->vnodestr[from].firstedge; if(!p) { g->vnodestr[from].firstedge = pedge; } else //尾插 { while(p->nextedge) { p = p->nextedge; } p->nextedge = pedge; } } } int findvsite(graph *g,char v) { int i; for(i=0;i<g->vnum;i++) { if(g->vnodestr[i].vertex==v) //返回顶点位序 return i; } return -1; } int getarcsnum(graph *g,int index) { int k = 0; enode *p = g->vnodestr[index].firstedge; if(index>=0&&index<g->vnum) { while(p) { k++; //有一个邻接点就是有一个出度 p = p->nextedge; } return k; } return -1; } int connected(graph *g,int from,int to) //看有没边 { enode *p = g->vnodestr[from].firstedge; if((from<0||from>=g->vnum) || (to<0&&to>=g->vnum)) return 0; while(p) { if(p->nexttov==to) return 1; //有邻接点就是有边 p = p->nextedge; } return 0; } /*void dfssearch0(graph *g) //非递归实现深搜 { int i,top = 0,k,m; int flag[20]; //记录顶点的下标 enode *p; for(i=0;i<20;i++) flag[i] = -1; //从第一个顶点开始 vertex[top++] = g->vnodestr[0].vertex; flag[0] = 0; while(top>0&&top<g->vnum){ if(!p) //退栈,从上一个顶点开始 i=flag[--m]; else m = i = flag[top-1]; p = g->vnodestr[i].firstedge; while(p) { for(k=0;k<top;k++) if(flag[k]==p->nexttov) break; if(k==top) { vertex[top] = g->vnode[p->nexttov].vertex; flag[top++] = p->nexttov; break; } p = p->nextedge; } } }*/ int visited1[20]; int visited2[20]; void dfs(graph g,int i) { enode *p; printf("访问节点%c\n",g.vnodestr[i].vertex); visited1[i] = 1; //访问了就标记1,不能再访问了 p = g.vnodestr[i].firstedge; while(p) { if(!visited1[p->nexttov]) { dfs(g,p->nexttov); } p = p->nextedge; } } void dfssearch(graph g) { int i,j; for(i=0;i<g.vnum;i++) { visited1[i] = 0; } for(j=0;j<g.vnum;j++) { if(!visited1[j]) { dfs(g,j); } } } void bfssearch(graph g) { queue<int> q; enode *p; int i,j,w; for(i=0;i<g.vnum;i++) { visited2[i] = 0; } for(j=0;j<g.vnum;j++) { if(!visited2[j]) q.push(j); //没访问过就入队 while(!q.empty()) { w = q.front(); //队头元素要先被访问 printf("%c ->",g.vnodestr[w].vertex); visited2[w] = 1; //访问完了就标记1,不能再访问了 q.pop(); //访问完了就出队给下一个元素 for(p=g.vnodestr[w].firstedge;p;p=p->nextedge) //找访问的元素的邻接点入队待访问 { if(!visited2[p->nexttov]) q.push(p->nexttov); } } } } int main() { graph g; creategraph(&g); printf("%d\n",findvsite(&g,'b')); printf("%d\n",getarcsnum(&g,1)); printf("%d\n",connected(&g,1,3)); printf("深搜-----\n"); dfssearch(g); printf("广搜-----\n"); bfssearch(g); printf("\n"); return 0; }