验证中...
语言: C/C++
分类: 编程语言基础
最后更新于 2018-01-14 12:38
图遍历的演示.cpp
原始数据 复制代码
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include<iostream>
using namespace std;
#define VerStrLen 5
#define MaxVnum 30
typedef struct ArcNode{ //表结点
int adjvex;
int weight;
struct ArcNode *nextarc;
}ArcNode;
typedef struct Vnode{ //头结点
char *data;
ArcNode *firstarc;
}Vnode, *AdjList;
typedef struct {//邻接表
int vexnum,arcnum;
AdjList vertices;
}ALGraph;
bool visited[MaxVnum];
int Locate(ALGraph G, char *s)
{
int i;
for(i=0; i<G.vexnum; i++){
if(!strcmp(s, G.vertices[i].data))
return i;
}
return -1;
}
void create_AdjList(ALGraph &ALG)
{
FILE *fp;
int i,j;
if((fp = fopen("Graph.txt","r"))==NULL) {
printf("Could not open Graph.txt file\n");
exit(0);
}
fscanf(fp, "%d %d\n", &ALG.vexnum, &ALG.arcnum);
ALG.vertices = (AdjList)malloc(ALG.vexnum*sizeof(Vnode));
for(i=0; i<ALG.vexnum; i++){
ALG.vertices[i].data = (char *)malloc(VerStrLen*sizeof(char));
fscanf(fp, "%s", ALG.vertices[i].data);
ALG.vertices[i].firstarc = NULL;
}
for(int k = 0; k < ALG.arcnum;++k){ //输入各边,构造邻接表
char v1[VerStrLen] , v2[VerStrLen];
fscanf(fp, "%s %s\n", v1, v2); //输入一条边依附的两个顶点
i = Locate(ALG, v1); j = Locate(ALG, v2);
//确定v1和v2在G中位置,即顶点在G.vertices中的序号
ArcNode *p1=new ArcNode; //生成一个新的边结点*p1
p1->adjvex=j; //邻接点序号为j
p1->nextarc= ALG.vertices[i].firstarc; ALG.vertices[i].firstarc=p1;
//将新结点*p1插入顶点vi的边表头部
ArcNode *p2=new ArcNode; //生成另一个对称的新的边结点*p2
p2->adjvex=i; //邻接点序号为i
p2->nextarc= ALG.vertices[j].firstarc; ALG.vertices[j].firstarc=p2;
//将新结点*p2插入顶点vj的边表头部
}//for
fclose(fp);
}
void DFS(ALGraph G, int v)
{
ArcNode *p;
visited[v] = true;
printf("%s ", G.vertices[v].data);
for(p=G.vertices[v].firstarc; p; p=p->nextarc){
if(visited[p->adjvex]==false)
DFS(G, p->adjvex);
}
}
void DFSTraverse(ALGraph G, int i)
{
int v;
for(v=0; v<G.vexnum; ++v)
visited[v] = false;
DFS(G, i);
for(v=0; v<G.vexnum; ++v)
if(visited[v]==false)
DFS(G, v);
}
void BFSTraverse(ALGraph G, int i)
{
int v, u;
int *Q;
int front=0, rear=0;
ArcNode *p;
for(v=0; v<G.vexnum; ++v)
visited[v] = false;
Q = (int *)malloc(G.vexnum*sizeof(int));
if(visited[i]==false){
Q[rear++] = i;
visited[i] = true;
printf("%s ", G.vertices[i].data);
while(front != rear){
u = Q[front++];
for(p=G.vertices[u].firstarc; p; p=p->nextarc){
if(visited[p->adjvex]==false){
Q[rear++] = p->adjvex;
visited[p->adjvex] = true;
printf("%s ", G.vertices[p->adjvex].data);
}
}
}
}
for(v=0; v<G.vexnum; ++v)
if(visited[v]==false){
Q[rear++] = v;
visited[v] = true;
printf("%s ", G.vertices[v].data);
while(front != rear){
u = Q[front++];
for(p=G.vertices[u].firstarc; p; p=p->nextarc){
if(visited[p->adjvex]==false){
Q[rear++] = p->adjvex;
visited[p->adjvex] = true;
printf("%s ", G.vertices[p->adjvex].data);
}
}
}
}
free(Q);
}
int main()
{
ALGraph ALG;
int i, j, v,index;
create_AdjList(ALG);
cout << "无向连通图ALG创建完成!" << endl << endl;
char c[VerStrLen];
cout << "请输入遍历连通图的起始点:";
cin >> c;
index = Locate(ALG, c);
while(index == -1){
cout << "该点不存在,请重新输入!" << endl;
cout << "请输入遍历连通图的起始点:";
cin >> c;
index = Locate(ALG, c);
}
//邻接表深度优先搜索
printf("邻接表深度优先搜索序列: ");
DFSTraverse(ALG, index);
printf("\n");
//邻接表广度优先遍历
printf("邻接表广度优先搜索序列: ");
BFSTraverse(ALG, index);
printf("\n");
}

评论列表( 0 )

你可以在登录后,发表评论

搜索帮助

12_float_left_people 12_float_left_close