基于邻接表的图的遍历
（1）建立一个邻接表存储的图；（2）输出图的邻接表；（3）输出各顶点的度（若是有向图，输出各顶点的入度、出度和度）；（4）对图进行深度优先、广度优先遍历。
【测试数据】
（1）
输入图的种类：2
输入图的顶点数和边数：5 5
输入各条边：0 1 0 3 1 2 2 3 2 4
（2）
输入图的种类：0
输入图的顶点数和边数：3 4
输入各条边：0 1 0 2 1 0 1 2
#include <iostream>
#include <malloc.h>
#include <queue>
using namespace std;
#define VertexType int
#define MaxVertexNum 20 //最大顶点数
queue<int>Q; //辅助队列
enum GraphType {
DG, UDG}; //DG表示有向图，UDG表示无向图
typedef struct ArcNode //边结点
{
int adjvex; //邻接点的下标
struct ArcNode *nextarc; //后继链指针
} ArcNode;
typedef struct VNode //顶点结点
{
VertexType data; //顶点数据
ArcNode *firstarc; //边链头指针
} VNode, AdjList[MaxVertexNum];
typedef struct
{
AdjList vertices; //邻接表
int vexnum,arcnum; //顶点数和边数
int kind; //图种类标志
} ALGraph;
//建立有向图
void CreateDGGraph(ALGraph &G)
{
// cout<<0<<endl;
int m, n; //边<Vm,Vn>的下标
ArcNode *vm, *vn; //构成边<Vm,Vn>的两个顶点
cout << "请输入顶点数和边数：";
cin >> G.vexnum >> G.arcnum;
//获取顶点信息
for(int i=0; i<G.vexnum; i++)
{
G.vertices[i].data=i;
G.vertices[i].firstarc=NULL;
}
//建立邻接表，采用头插法
for(int i=0; i<G.arcnum; i++)
{
cout << "请输入<Vi,Vj>的下标：";
cin >> m >> n;
vm=(ArcNode*)malloc(sizeof(ArcNode));
vm->adjvex=n;
vm->nextarc=NULL;
if(G.vertices[m].firstarc==NULL)
{
vn=G.vertices[m].firstarc=vm;
}
else
{
vn=vn->nextarc=vm;
}
}
}
//建立无向图
void CreateUDGGraph(ALGraph &G)
{
int m, n; //边<Vm,Vn>的下标
ArcNode *pe;
cout << "请输入顶点数和边数：";
cin >> G.vexnum >> G.arcnum;
//获取顶点信息
for(int i=0; i<G.vexnum; i++)
{
G.vertices[i].data=i;
G.vertices[i].firstarc=NULL;
}
//建立邻接表，采用头插法
for(int i=0; i<G.arcnum; i++)
{
cout << "请输入<Vi,Vj>的下标：";
cin >> m >> n;
pe=(ArcNode*)malloc(sizeof(ArcNode));
pe->adjvex=n;
pe->nextarc=G.vertices[m].firstarc;
G.vertices[m].firstarc=pe;
pe=(ArcNode*)malloc(sizeof(ArcNode));
pe->adjvex=m;
pe->nextarc=G.vertices[n].firstarc;
G.vertices[n].firstarc=pe;
}
}
void PrintALGraph(ALGraph &G)
{
ArcNode *p;
for (int i=0; i<G.vexnum; i++)
{
cout << "顶点" << G.vertices[i].data <<" : ";
for (p=G.vertices[i].firstarc; p!=NULL; p=p->nextarc)
cout << p->adjvex <<" ";
if (p==NULL)
cout << endl;
}
}
void PrintDU(ALGraph &G)
{
ArcNode *p;
if(G.kind==2)
for(int i=0; i<G.vexnum; i++)
{
cout<<"顶点："<<i;
int cnt=0;
cout<<" 度 ：";
for(p=G.vertices[i].firstarc; p!=NULL; p=p->nextarc)
cnt++;
if(p==NULL)
cout<<cnt<<endl;
}
else
{
int cnt1[G.vexnum]= {
0},cnt2[G.vexnum]= {
0},cnt[G.vexnum]= {
0};
for(int i=0; i<G.vexnum; i++)
{
cout<<"顶点："<<i;
cout<<" 出度 ：";
for(p=G.vertices[i].firstarc; p!=NULL; p=p->nextarc)
cnt1[i]++;
if(p==NULL)
cout<<cnt1[i];
cout<<" 入度 ：";
if(i!=G.vexnum-1)
{
ArcNode *pp;
pp=G.vertices[i].firstarc;
for(int j=0; j<G.vexnum; j++)
{
for(p=G.vertices[j].firstarc; p!=NULL; p=p->nextarc)
if(p->adjvex==pp->adjvex)
cnt2[i]++;
}
}
else
{
for(int j=0; j<G.vexnum-1; j++)
cnt2[i]+=cnt1[j]-cnt2[j];
}
cout<<cnt2[i];
cnt[i]=cnt1[i]+cnt2[i];
cout<<" 度 ："<<cnt[i]<<endl;
}
}
}
//求图中顶点v的第一个邻接点，若有则返回顶点下标。若v没有邻接点或图中不存在v，则返回-1
int FirstNeighbor(ALGraph G, int v)
{
ArcNode *next=G.vertices[v].firstarc;
if(next)
{
return next->adjvex;
}
return -1;
}
//返回除顶点v外的下一个顶点w
int NextNeighbor(ALGraph G, int v, int w)
{
ArcNode *next=G.vertices[v].firstarc;
while(next)
{
if(next->adjvex==w)break;
next=next->nextarc;
}
if(next)
{
ArcNode *nextNode=next->nextarc;
if(nextNode)
{
return nextNode->adjvex;
}
}
return -1;
}
void visit(ALGraph G, int v)
{
cout << G.vertices[v].data << " ";
}
bool visited[MaxVertexNum]; //访问标记数组
//从顶点v出发，采用递归，广度遍历图G
void BFS(ALGraph G, int v)
{
visit(G, v);
visited[v]=true; //设已访问标记
Q.push(v); //顶点v入队
while(!Q.empty())
{
v=Q.front();
Q.pop();
for(int w=FirstNeighbor(G, v); w>=0; w=NextNeighbor(G, v, w))
{
//检查v所以邻接点
if(!visited[w]) //w为v的尚未访问的邻接顶点
{
visit(G, w);
visited[w]=true; //设已访问标记
Q.push(w); //顶点w入队
}
}
}
}
//从顶点出发，进行广度优先遍历
void BFSTraverse(ALGraph G)
{
for(int i=0; i<G.vexnum; i++)
{
visited[i]=false; //访问标记数组初始化
}
for(int i=0; i<G.vexnum; i++) //从0号顶点开始遍历
{
if(!visited[i])
{
BFS(G, i); //vi未访问过，从vi开始BFS
}
}
}
//从顶点v出发，采用递归，深度遍历图G
void DFS(ALGraph G, int v)
{
visit(G, v); //访问v
visited[v]=true; //设已访问标记
for(int w=FirstNeighbor(G, v); w>=0; w=NextNeighbor(G, v, w))
{
//w为v的尚未访问的邻接顶点
if(!visited[w])
{
DFS(G, w);
}
}
}
//从顶点出发，进行深度优先遍历
void DFSTraverse(ALGraph G)
{
for(int i=0; i<G.vexnum; i++)
{
visited[i]=false; //访问标记数组初始化
}
for(int i=0; i<G.vexnum; i++) //从0号顶点开始遍历
{
if(!visited[i])
{
DFS(G, i); //vi未访问过，从vi开始DFS
}
}
}
int main()
{
printf("****菜 单****\n");
printf("0、有向图\n");
printf("2、无向图\n\n");
printf("输入图的种类:\n");
int tmp;
ALGraph G;
cin>>G.kind;
if(G.kind==0)
{
CreateDGGraph(G); //建立有向图
}
else if(G.kind==2)
{
CreateUDGGraph(G); //建立无向图
}
cout << "===========================" << endl;
PrintALGraph(G);
cout <<endl;
PrintDU(G);
cout <<endl;
cout << "广度遍历：";
BFSTraverse(G);
cout << endl;
cout << "深度遍历：";
DFSTraverse(G);
return 0;
}
携程公司氛围 85人发布
