图的广度优先搜索和深度优先搜索:
#include <iostream>
#include <queue>
#include <stdio.h>
#include <queue>
#include <stdlib.h>
#include <list>
using namespace std;
#define VERTEXNUM 100//最大顶点数
#define INF 65535
enum nodecolor {white,gray,black};
typedef struct node//参见算法导论322
{
int adjvex;//顶点位置
struct node *next;//指向下一条边的指针
}EdgeNode;
typedef struct vnode
{
char vertex;//顶点信息
EdgeNode *firstedge;//指向第一条依附该顶点的边的指针
nodecolor color;
int d;//广度优先中到第一个点的距离,深度优先中被发现的时间
int f;//深度优先中结束检查此结点的邻接表的时间
vnode* pi;//父结点
}AdjList[VERTEXNUM];
typedef struct
{
AdjList vertexs;//邻接表
int vernum,edgenum;//图中当前的顶点和边数
}Graph;
//建立邻接表
void MakeGraph(Graph *G)
{
int v1,v2;
int i,j,k;
cout<<"请输入图的顶点数和边数"<<endl;
cin>>G->vernum>>G->edgenum;
cout<<"请输入顶点信息(顶点号<CR>)每个顶点以回车作为结束:"<<endl;
for(i=0;i<G->vernum;++i)
{
//getchar();
cin>>G->vertexs[i].vertex;
G->vertexs[i].firstedge=NULL;//初始第一条边为空
}
cout<<"请输入每条边对应的两个顶点的序号(格式为i,j):"<<endl;
EdgeNode *p;
for(k=0;k<G->edgenum;k++)
{
cin>>i>>j;//读入边<vi,vj>的序号
p=(node*)malloc(sizeof(node));//生成新的结点
p->adjvex=j-1;
p->next=G->vertexs[i-1].firstedge;
G->vertexs[i-1].firstedge=p;//这3行是插入链表的操作
}
}
//广度优先遍历
void BFS(Graph *G,vnode *s)
{
int i;
queue<vnode *> Q;
EdgeNode *p;
vnode *u;
for(i=0;i<G->vernum;i++)
{
G->vertexs[i].d=INF;
G->vertexs[i].pi=NULL;
G->vertexs[i].color=white;
}
s->color=gray;
s->d=0;
s->pi=NULL;
Q.push(s);
while(!Q.empty())
{
u=Q.front();
Q.pop();//出队
p=u->firstedge;
while(p)
{
if(G->vertexs[p->adjvex].color==white)
{
G->vertexs[p->adjvex].color=gray;
G->vertexs[p->adjvex].d=u->d+1;
G->vertexs[p->adjvex].pi=u;
Q.push(&G->vertexs[p->adjvex]);
}
p=p->next;
}
u->color=black;
}
for(i=0;i<G->vernum;i++)
{
u=&G->vertexs[i];
cout<<"结点:"<<u->vertex<<"距离:"<<u->d<<"颜色:"<<u->color<<endl;
}
}
//深度优先遍历
void DFS_visit(Graph *G,vnode *u);
int t=0;//时间
list<vnode*> L;//用于拓扑排序
void DFS(Graph *G)
{
int i;
for(i=0;i<G->vernum;i++)
{
G->vertexs[i].d=INF;
G->vertexs[i].pi=NULL;
G->vertexs[i].color=white;
}
for(i=0;i<G->vernum;i++)
{
if(G->vertexs[i].color==white)
DFS_visit(G,&G->vertexs[i]);
}
for(i=0;i<G->vernum;i++)
{
vnode *u=&G->vertexs[i];
cout<<"结点:"<<u->vertex<<"开始:"<<u->d<<"结束:"<<u->f<<endl;
}
}
void DFS_visit(Graph *G,vnode *u)
{
EdgeNode *p;
u->color=gray;
u->d=++t;
p=u->firstedge;
while(p)
{
if(G->vertexs[p->adjvex].color==white)
{
G->vertexs[p->adjvex].pi=u;
DFS_visit(G,&G->vertexs[p->adjvex]);
}
p=p->next;
}
u->color=black;
u->f=++t;
L.insert(L.begin(),u);//用于拓扑排序
}
//拓扑排序
list<vnode*>& topological_sort(Graph* G)
{
DFS(G);
return L;
}
int main()
{
int j;
Graph *G=(Graph *)malloc(sizeof(Graph));
MakeGraph(G);
cout<<"请输入广度优先开始遍历的结点的序号:"<<endl;
cin>>j;
cout<<"广度优先遍历:"<<endl;
BFS(G,&G->vertexs[j-1]);
cout<<"深度优先遍历:"<<endl;
DFS(G);
return 0;
}
最小生成树:
//Kruskal const int maxint = 999999; typedef struct Road { int c1,c2;//a到b int value;//权值 }Road; int no; int line; Road road[100]; int node[101]; bool myCmp(const Road &a,const Road &b) { return (a.value<b.value); } int Find_Set(int n) { if(node[n]==-1) return n; else return Find_Set(node[n]);//其实就是沿着树找到根 } bool Merge(int s1,int s2) { int r1=Find_Set(s1); int r2=Find_Set(s2); if(r1==r2)//根相同就是属于同一棵树 return 0; if(r1<r2) node[r2]=r1; else node[r1]=r2; return 1; } int main() { freopen("input.txt","r",stdin); memset(node,-1,sizeof(node)); cout<<"Input the number of the node:"; cin>>no; cout<<"Input the number of the line:"; cin>>line; cout<<"Input the edge:"; for(int i=0;i<line;++i) { cin>>road[i].c1>>road[i].c2>>road[i].value; } sort(road,road+line,myCmp); int sum=0,count=0; for(int i=0;i<line;++i) { if(Merge(road[i].c1,road[i].c2)) { count++; sum+=road[i].value; } if(count==no-1) break; } cout<<sum<<endl; } //Prim const int INF=1001; int no,line; int arcs[101][101]; int dis[101],vis[101]; int _min; int main() { freopen("input.txt","r",stdin); cout<<"Input the number of the node:"; cin>>no; cout<<"Input the number of the line:"; cin>>line; for(int i=0;i<no;++i) for(int j=0;j<no;++j) arcs[i][j]=INF; cout<<"Input the edge:"; int p,q,len;//输入p,q两点及路径长度 for(int i=0;i<line;++i) { cin>>p>>q>>len; if(len<arcs[p-1][q-1])//有重边 { arcs[p-1][q-1]=len; arcs[p-1][q-1]=len;//表示无向图 } } memset(vis,0,sizeof(vis)); for(int i=1;i<no;++i) dis[i]=arcs[0][i]; vis[0]=1; int sum=0,rec=0; dis[0]=0; for(int i=1;i<no;++i) { _min=INF; for(int j=0;j<no;++j) if(!vis[j]&&dis[j]<_min) { rec=j; _min=dis[j]; } cout<<"min:"<<_min<<endl; sum+=_min; vis[rec]=1; for(int j=0;j<no;++j) if(!vis[j]&&arcs[rec][j]<dis[j]) dis[j]=arcs[rec][j]; } printf("%d\n",sum); return 0; }