#define MAXSIZE 20 #define FALSE 0 #define TRUE 1
#include #include #include using namespace std;
typedef int Status; //…………………………………………队列结构…………………… typedef struct qnode { int data; struct qnode *next; }qnode,*queueptr; typedef struct { queueptr front; queueptr rear; }linkqueue;
//…………………………………………邻接表结构………………………… typedef struct arcnode//弧结点 { int adjvex; //该弧指向的顶点的位置 struct arcnode *nextarc; //弧尾相同的下一条弧 }arcnode; typedef struct vnode//邻接链表顶点头接点 { char data; //结点信息 arcnode *firstarc; //指向第一条依附该结点的弧的指针 }vnode,adjlist;
//…………………………………………图结构………………………… typedef struct//图的定义 { adjlist vertices; int vexnum,arcnum; //顶点数，弧的条数 }algraph; //无向图
//…………………………………………链队列定义…………………… void InitQueue(linkqueue &q)//初始化队列 { q.rear=(queueptr)malloc(sizeof(qnode)); if(!q.front)exit(-1); //分配空间失败 q.front=q.rear; q.front->next = NULL; } Status Queue_empty(linkqueue q)//判断队为空 { if(q.front==q.rear) return TRUE; else return FALSE; } Status EnQueue(linkqueue &q,int e)//入队 { queueptr p; p = (queueptr)malloc(sizeof(qnode)); if(!p) exit(-1); //分配空间失败
p->data = https://www.it610.com/article/e; p->next = NULL; q.rear->next = p; q.rear = p; return TRUE; } Status DeQueue(linkqueue &q,int &e)//出队 { queueptr p; if( Queue_empty(q) ) return FALSE;
p = q.front->next; e = p->data; q.front->next = p->next; if(q.rear ==p)q.rear = q.front; free(p); return TRUE; }
//…………………………………………邻接表定义…………………… int localvex(adjlist G_L[],char v)//返回V的位置 { int i = 0; //printf("da = ‘%c’ v = ‘%c’\n",G_L[i].data,v); while(G_L[i].data != v) { //printf("da = %c ,v = %c",G_L[i].data,v); ++i; } //printf("i = %d\n",i); return i; }
void Print_G_L( algraph G,adjlist * G_L) { cout<<"————————图的邻接表——————"< for(int i=0; i { printf(" [%d] (%c) : ",i,G_L[i].data); arcnode * q = G_L[i].firstarc; while(q ) { printf(" %d",q->adjvex); q = q->nextarc; } printf("\n"); } } Status CreteAdj( algraph &G ,adjlist *G_L)//用邻接表存储图 { cout<>G.vexnum >>G.arcnum; for(int i=0; i < G.vexnum; i++) { printf("请输入图的第%d个顶点(大写字母A,B,C...)：",i+1);
cin>>G_L[i].data; //printf("dat = %c",G_L[i].data); } for(int i=0; i
for(int i=0; i < G.arcnum; i++) { char first_v,second_v; printf("请输入图的第%d条边,两顶点间逗号隔开(如‘A,B’不包括引号）:",i+1); getchar(); scanf("%c,%c",&first_v,&second_v);
//printf("fir = %c, sec = %c",first_v,second_v);
int loc1 = localvex( G_L,first_v); //第1个顶点下标 int loc2 = localvex( G_L,second_v ); //第2个顶点下标
//printf("loc1 = %d, loc2 = %d\n",loc1,loc2);
arcnode * p = (arcnode * )malloc(sizeof(arcnode)); if(!p) exit(-1); //first->second边 p->adjvex = loc2; p->nextarc = NULL; arcnode * q ; if( G_L[loc1].firstarc == NULL || G_L[loc1].firstarc->adjvex < p->adjvex) { p->nextarc = G_L[loc1].firstarc; G_L[loc1].firstarc = p; }//p插在第一个 else{ //寻找新非零元在航标中的插入位置 for( q = G_L[loc1].firstarc ; (q->nextarc)&&(q->nextarc->adjvex < p->adjvex ); q = q->nextarc ) ; //循环到合适位置，这是个空循环 p->nextarc = q->nextarc; q->nextarc = p; //完成行插入 }//else
arcnode * p2 = (arcnode * )malloc(sizeof(arcnode)); if(!p2) exit(-1); //second->first边 p2->adjvex = loc1; p2->nextarc = NULL; if( G_L[loc2].firstarc == NULL || G_L[loc2].firstarc->adjvex < p2->adjvex) { p2->nextarc = G_L[loc2].firstarc; G_L[loc2].firstarc = p2; }//p插在第一个 else{ //寻找新非零元在航标中的插入位置 for( q = G_L[loc2].firstarc ; (q->nextarc)&&(q->nextarc->adjvex < p2->adjvex ); q = q->nextarc ) ; //循环到合适位置，这是个空循环 p2->nextarc = q->nextarc; q->nextarc = p2; //完成行插入 }//else
} return TRUE; } void BFS( algraph G,adjlist G_L[] )//广度优先遍历 { int i,e; arcnode * p; int visit[MAXSIZE]; //标志元素是否已被访问过，0：未访问， 1：已访问 linkqueue q; InitQueue(q); for(i=0; i != G.vexnum; ++i)visit[i] = FALSE; cout<<"广度遍历为："; for(i=0; i!=G.vexnum; ++i) if( visit[i]==FALSE ) { visit[i] = TRUE ; cout<< G_L[i].data; EnQueue(q , i ); while( !Queue_empty(q) ) { DeQueue(q,e); for(p = G_L[e].firstarc; p; p = p->nextarc) { if( visit[p->adjvex]==FALSE ) //未访问 { visit[p->adjvex] = TRUE; cout<adjvex].data; EnQueue(q,p->adjvex); } }//for } //while } //if cout< return; } void DFS(adjlist G_L[],int v,int visit[]) {// 从顶点v出发，深度优先搜索遍历连通图 G cout< visit[v] = TRUE; arcnode * q = G_L[v].firstarc; while( q ) { if( !visit[q->adjvex]) DFS(G_L,q->adjvex,visit); q = q->nextarc; } } // DFS




int main() { algraph G; //图 adjlist G_L[MAXSIZE]; //图的邻接表 int visit[MAXSIZE] ={ FALSE }; //该数组用来标志对应下标的元素是否已被访问，初始 FALSE 未访问
CreteAdj( G ,G_L); Print_G_L(G,G_L); BFS(G,G_L); cout<<"深度遍历为："; DFS(G_L,0,visit); cout<

return 0; }