/**图的邻接表存储方式*/#include<iostream>#include<cstdio>#include<string.h>#include<string>#include<queue>#define TRUE 1#define FALSE 0#define OK1#define ERROR 0using namespace std;#define MAX_VERTEX_NUM 100#define MAXSIZE 100typedef string VertexType;typedef int Status;typedef int Element;//队列的结点结构typedef struct QNode{Element data;struct QNode * next;}QNode;//队列的链表结构typedef struct{QNode * queue_front; //队头指针QNode * queue_rear; //队尾指针}LinkQueue;//链队的初始化Status InitQueue(LinkQueue & Q){Q.queue_front=Q.queue_rear=(QNode *)malloc(sizeof(QNode));Q.queue_front->next=NULL;return OK;}//入队操作Status EnQueue(LinkQueue & Q,Element e){QNode * p;p=(QNode*)malloc(sizeof(QNode));p->data=e;p->next=NULL;Q.queue_rear->next=p;Q.queue_rear=p;return OK;}//出队操作Status Dequeue(LinkQueue & Q,Element & e){if(Q.queue_front==Q.queue_rear) return ERROR;QNode * p;p=Q.queue_front->next;//p指向队头元素e=p->data; //e保存队头元素的值Q.queue_front->next=p->next;//修改头指针//注意的是：在链队出队操作时，如果最后一个元素被删除，队尾指针也丢失了，需要对队尾指针重新赋值if(Q.queue_rear==p)Q.queue_rear=Q.queue_front;return e;}//遍历队列Status QueueTraverse(LinkQueue Q){QNode * p;p=Q.queue_front->next;while(p){cout<<(p->data)<<" ";p=p->next;}return OK;}//获取队头的元素Status get_QueueHead(LinkQueue Q,Element & e){if(Q.queue_front==Q.queue_rear){return ERROR;}else{e=Q.queue_front->next->data;return OK;}}/**判断队列是否为空*/Status IsEmpty(LinkQueue Q){if(Q.queue_front==Q.queue_rear)return TRUE;elsereturn FALSE;}queue<int>q;bool visited[MAX_VERTEX_NUM]={0};bool visited1[MAX_VERTEX_NUM]={0};typedef struct Arcnode //弧{/**该弧所指向的顶点的位置*/int adjvex;/**与边有关的信息(权值)*/int info;/**下一条以当前顶点为出度的弧*/struct Arcnode * nextarc;}/**弧*/Arcnode;typedef struct VNode//点{/**结点名字*/VertexType data;/**指向第一条依附于该顶点的出边*/Arcnode * firstarc;}/**点*/VNode,/**AdjList表示邻接表类型,点的集合*/AdjList[MAX_VERTEX_NUM];typedef struct//图{/**点的邻接表的数组*/AdjList vertices;/**图的当前顶点数*/int vexnum;/**图的当前边数*/int arcnum;}/**图*/ALGraph;/**加边*/void ArcAdd(ALGraph &G,int v1,int v2,int w)//加边{Arcnode *p,*q;//Arcnode是弧p = new Arcnode; //新建立一个结点pp->adjvex=v2; //p边指向顶点位置为v2的那个顶点p->info=w; //这条边的权重为wp->nextarc=NULL; //？q=G.vertices[v1].firstarc; //位置为v1这个点的第一条出边为qif(q==NULL){G.vertices[v1].firstarc=p; //若第一条依附v2顶点的弧还没有存在，则新加入的边作为第一条依附的弧}else //否则顺着链表向后查找{while(q->nextarc!=NULL)q=q->nextarc;q->nextarc=p;}}/**获取每个结点对应的存储位置标号*/int LocateVex(ALGraph G,string name){for(int i=0;i<G.vexnum;i++){if(name==G.vertices[i].data){return i;}}return -1;}/**建立带权无向图*/Status CreateUDN_2(ALGraph & G){cout<<"建立带权无向图，请依次输入总结点数，总边数：";cin>>G.vexnum>>G.arcnum;cout<<"请为从1至n个结点命名:"<<endl;for(int i=0;i<G.vexnum;i++){cin>>G.vertices[i].data;G.vertices[i].firstarc=NULL;}string v1,v2;int w;cout<<"请输入"<<G.arcnum<<"组相互依附的两结点与边权"<<endl;for(int k=0;k<G.arcnum;k++){cin>>v1>>v2>>w;int i=LocateVex(G,v1);int j=LocateVex(G,v2);ArcAdd(G,i,j,w); //无向边ArcAdd(G,j,i,w); //无向边}return OK;}/**第一个邻接点*@return 返回值是v的第一个邻接点顶点的位置；若没有邻结点则返回为"空"*/int FirstAdjVex(ALGraph G,int v){if(G.vertices[v].firstarc)//如果说对于点v，存在该点的一条出边{return G.vertices[v].firstarc->adjvex;//返回v顶点的一条出边指向的那个顶点的位置}else{return -1;}}/**相对与某一点的下一个邻接点*@return 返回值是v的（相对于w的）下一个邻接点；如果w是v的最后一个邻接点，则返回值为"空"*/int NextAdjVex(ALGraph G,int v,int w){Arcnode * p =G.vertices[v].firstarc; //边p是顶点v的第一条出边while(p->adjvex!=w&&p->nextarc!=NULL){p=p->nextarc;}if(p->nextarc==NULL){return -1;}return p->nextarc->adjvex;}/**打印邻接表*/void PrintGraph(ALGraph G){cout<<"图的创建完成，该图的邻接表表示如下："<<endl;cout<<"括号内表示边的权重——括号前面两个顶点组成边的权重,若权重为0表示没有权重"<<endl;Arcnode *p; //一条弧pfor(int i=0;i<G.vexnum;i++){if(G.vertices[i].firstarc==NULL){cout<<i<<": "<<G.vertices[i].data<<"-->NULL"<<endl;}else{p=G.vertices[i].firstarc;cout<<i<<": "<<G.vertices[i].data<<"-->";while(p->nextarc!=NULL){cout<<p->adjvex<<"("<<p->info<<")"<<"-->";p=p->nextarc;}cout<<p->adjvex<<"("<<p->info<<")"<<"-->NULL"<<endl;}}}/**深度优先搜索*/void DFS(ALGraph G,int v){int w = 0;Arcnode * p = NULL;cout<<v;visited[v]=1;p=G.vertices[v].firstarc;while(p!=NULL){w=p->adjvex;if(!visited[w]){DFS(G,w);}p=p->nextarc;}}/**广度优先搜索(使用标准库queue)*//*void BFS(ALGraph G,int v){cout<<v;visited1[v]=1;q.push(v);while(!q.empty()){int u = q.front();q.pop();Arcnode * p;p=G.vertices[u].firstarc;while(p!=NULL){if(!visited1[p->adjvex]){cout<<p->adjvex;visited1[p->adjvex]=1;q.push(p->adjvex);}p=p->nextarc;}}}*//**广度优先搜索(自己写的队列)*/void BFS1(ALGraph G,int v){LinkQueue queue1;InitQueue(queue1);cout<<v;visited1[v]=1;EnQueue(queue1,v);while(!IsEmpty(queue1)){int u=0;//u = get_QueueHead(queue1,u);//Dequeue(queue1,u);u=Dequeue(queue1,u);Arcnode * p ;p=G.vertices[u].firstarc;while(p!=NULL){if(!visited1[p->adjvex]){cout<<p->adjvex;visited1[p->adjvex]=1;EnQueue(queue1,p->adjvex);}p=p->nextarc;}}}int main(){ALGraph G;CreateUDN_2(G);PrintGraph(G);cout<<"深度优先搜素遍历如下:"<<endl;DFS(G,0);cout<<"广度优先搜素遍历如下:"<<endl;BFS1(G,0);return 0;}
注释还没写完，要考试了,唉…
参考两位大佬的资料，然后广度优先没用STL，用的自己之前写的链队
/kuronekonano/article/details/78657592 作者：kuronekonano
/Krismile_/article/details/84774256 作者：Krismile_
