数据结构实验报告-图
数据结构实验报告
图
一、实验目的
1、熟悉图的结构和相关算法。
二、实验内容及要求
1、编写创建图的算法。
2、编写图的广度优先遍历、深度优先遍历、及求两点的简单路径和最短路径的算法。
三、算法描述
1、图的邻接表存储表示：
对图的每个顶点建立一个单链表，第i个单链表表示所有依附于第i个点的边（对于有向图表示以该顶点为尾的弧）；链表的每个节点存储两个信息，该弧指向的顶点在图中的位置（adjvex）和指向下一条弧的指针（nextarc）。每个连表的头结点存储顶点的数据：顶点信息（data）和指向依附于它的弧的链表域。
存储表示如下：
typedef struct ArcNode {
int adjvex; // 该弧所指向的顶点的位置
struct ArcNode *nextarc;
// 指向下一条弧的指针
// InfoType *info; // 该弧相关信息的指针
} ArcNode;
typedef struct VNode {
char data; // 顶点信息
int data2;
int sngle;
ArcNode *firstarc;
// 指向第一条依附该顶点的弧
} VNode, AdjList[MAX_NUM];
typedef struct {
AdjList vertices;
int vexnum, arcnum;
int kind; // 图的种类标志
} ALGraph;
2、深度优先搜索：
假设初始态是图中所有定点未被访问，从图中的某个顶点v开始，访问此顶点，然后依次从v的未访问的邻接点出发深度优先遍历，直至途中所有和v有相同路径的点都被访问到；若图中仍有点未被访问，则从图中另选一个未被访问的点作为起点重复上述过程，直到图中所有点都被访问到。为了便于区分途中定点是否被访问过，需要附设一个访问标致数组visited [0..n-1]，将其初值均设为false，一旦某个顶点被访问，将对应的访问标志赋值为true。
2、广度优先搜索：
假设初始态是图中所有顶点未被访问，从图中的某个顶点v开始依次访问v的各个未被访问的邻接点，然后分别从这些邻接点出发以此访问他们的邻接点，并使“先被访问的邻接顶点”先于“后被访问的邻接顶点”被访问，直至图中所有已被访问过的顶点的邻接顶点都被访问。若图中仍有未被访问的顶点，选择另一个未被访问的顶点开始，重复上述操作，直到图中所有顶点都被访问。为了使
“先被访问的邻接顶点”先于“后被访问的邻接顶点”被访问，在次算法中加入一个队列，queue暂时存储被访问的顶点。
3、搜索简单路径：
利用深度优先搜索，以一个要搜索的起点v顶点为起始点，搜索到要找的终点s 结束。为了方便记录路径，此算法中加入栈。访问第v个顶点时将v入栈，以v 为顶点进行深度优先搜索，分别将其邻接点vi入栈，若找到s，将s入栈，若没有找到，将vi出栈；对vi+1深度优先搜索，直到找到s，或者图中所有顶点都被访问。
4、搜索最短路径：
搜索最短路径时，要记录被访问的顶点的上一个顶点在图中的位置，所以添加一个上一个顶点的标识single；访问v时将其标识置为-1；搜索从v到s的最短路径，从v开始进行广度优先搜索，直到找到s，将s以及它的之前的顶点依次入栈，直到将v入栈，然后将栈内元素输出。
四、程序代码：
#include
#include
#include
#define MAX_NUM 20
bool visited[MAX_NUM];//访问标致数组
bool found;
int fomer=0;
char v1,v2;
int tfind;
typedef struct ArcNode {
int adjvex; // 该弧所指向的顶点的位置struct ArcNode *nextarc;
// 指向下一条弧的指针// InfoType *info; // 该弧相关信息的指针
} ArcNode;
typedef struct VNode {
char data; // 顶点信息
int data2;
int sngle;
ArcNode *firstarc;
// 指向第一条依附该顶点的弧} VNode, AdjList[MAX_NUM];
typedef struct {
AdjList vertices;
int vexnum, arcnum;
int kind; // 图的种类标志
} ALGraph;
void DFS(ALGraph G,int v);
typedef struct qnode //队列类型
{
int data;
qnode *next;
}qnode,*queueptr;
typedef struct
{
queueptr front;
queueptr rear;
}linkqueue;
typedef struct stack//用栈存储路径
{
char *base;
char *top;
int stacksize;
int size;
}Stack;
Stack s;
int initstack(Stack &s)
{
s.base=(char*)malloc(40*sizeof(char));
s.top=s.base;
s.stacksize=40;
s.size=0;
return 1;
}
int push(Stack &s,char e)
{
.
*s.top++=e;
s.size++;
return 1;
}
int pop(Stack &s,char &e)
{
if(s.base==s.top)
e=*--s.top;
else {
e=*--s.top;
s.size--;
}
return 1;
}
void printstack(Stack s)
{
while(s.base!=s.top)
{
printf("%c ",*s.base);
s.base++;
}
printf("\n");
void printstack2(Stack s)
{
while(s.base!=s.top)
{
printf("%c ",*--s.top);
}
printf("\n");
}
int intitqueue(linkqueue &q)//初始化队列
{
q.front=q.rear=(queueptr)malloc(sizeof(qnode));
q.front->next=NULL;
return 1;
}
int emptyqueue(linkqueue q)//判断对了是否为空{
if (q.front==q.rear)
return 1;
return 0;
}
int enqueue(linkqueue &q,int e)//元素入队
queueptr p;
p=(queueptr)malloc(sizeof(qnode));
if(!p) exit(0);
p->data=e; p->next=NULL;
q.rear->next=p;
q.rear=p;
return 1;
}
int dequeue(linkqueue &q,int &e)//元素出队{
queueptr p;
if(q.front==q.rear) return 0;
p=q.front->next;
e=p->data;
q.front->next=p->next;
if(q.rear==p) q.rear=q.front;
free(p);
return 1;
}
int LocateVex(ALGraph &G,char v)
{
int i;
for(i=0;i if(G.vertices[i].data==v) return i; return -1; } int FirstAdjVex(ALGraph G,int v) { if(G.vertices[v].firstarc!=NULL) return G.vertices[v].firstarc->adjvex; return -1; } int NextAdjVex(ALGraph G,int v,int w) { while (G.vertices[v].firstarc->nextarc!=NULL) { if(G.vertices[v].firstarc->adjvex==w) return G.vertices[v].firstarc->nextarc->adjvex; else G.vertices[v].firstarc=G.vertices[v].firstarc->nextarc; } return -1; } void Create(ALGraph &G) { int i,j,k; char v1,v2; ArcNode *p,*q,*h; q=NULL; h=NULL; printf("输入节点个数和弧的个数:\n"); scanf("%d%d",&G.vexnum,&G.arcnum); for(i=0;i { fflush(stdin); printf("输入节点名称:\n"); scanf("%c",&G.vertices[i].data); G.vertices[i].firstarc=NULL; G.vertices[i].data2=i; } for(k=0;k { printf("输入弧：a,b:\n"); fflush(stdin); scanf("%c,%c",&v1,&v2); i=LocateVex(G,v1); j=LocateVex(G,v2); p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; p->nextarc=NULL; if (G.vertices[i].firstarc==NULL) G.vertices[i].firstarc=p; else { q=G.vertices[i].firstarc; while(q->nextarc!=NULL) q=q->nextarc; q->nextarc=p; } } } void DFSTraverse(ALGraph G)//深度遍历{ int v; for(v=0;v if(!visited[v]) DFS(G,v); printf("\n"); } void DFS(ALGraph G,int v)//深度遍历 { int w; visited[v]=true; printf("%c ",G.vertices[v].data); for(w=FirstAdjVex(G,v);(w>=0)&&(tfind==0);w=NextAdjVex(G,v,w)) { if(!visited[w]) DFS(G,w); } } void DFSTree(ALGraph G)//广度遍历 { int w,u,v; linkqueue q; intitqueue(q); for (v=0;v { if (!visited[v]) { visited[v]=true; printf("%c ",G.vertices[v].data); enqueue(q,v); } while (!emptyqueue(q)) { dequeue(q,u); for (w=FirstAdjVex(G,u);w>0;w=NextAdjVex(G,u,w)) if (!visited[w]) { visited[w]=true; printf("%c ",G.vertices[w].data); if(w>0) enqueue(q,w); } } } printf("\n"); } void DFS2(ALGraph G,int v)//用深度遍历算法实现搜索简单路径{ int w; char e; visited[v]=true; push(s,G.vertices[v].data); for(w=FirstAdjVex(G,v);(w>=0)&&(!found);w=NextAdjVex(G,v,w)) { if(G.vertices[w].data==v2) { found=true; push(s,G.vertices[w].data); } else if(!visited[w]) DFS2(G,w); } if(!found) pop(s,e); } void Simplepath(ALGraph G)//搜索简单路径 { printf("输入要搜索路径的两点：\n"); fflush(stdin); scanf("%c",&v1); fflush(stdin); scanf("%c",&v2);