#include <stdio.h>
#include <iostream.h>
#define INT_MAX 100
#define INFINITY INT_MAX // 最大值∞
#define MAX_VERTEX_NUM 20
typedef struct ArcCell
{
int adj; // VRType是顶点关系类型，对无权图，用1//或0表示相邻否；对带权图，则为权值类型
int *info; // 该弧相关信息的指针
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct MGraph
{
int vexs[MAX_VERTEX_NUM]; // 顶点向量
AdjMatrix arcs; // 邻接矩阵
int vexnum, arcnum; // 图的当前顶点数和弧(边)数
char kind; // 图的种类标志
}MGraph;
int LocateVex(MGraph &G, char &v)
{
int i;
for(i=0; i<G.vexnum; i++)
if(G.vexs[i]==v) return i;
return 0;
} // 最大顶点个数
int CreateUDG(MGraph &G) //创建无向网的邻接矩阵
{
int i, j, k, IncInfo;
char v1, v2, V;
printf("input the number for vexnum and arcnum:");
scanf("%d,%d", &G.vexnum, &G.arcnum); // IncInfo=0表示各弧不含其他信息
V=getchar(); //为了滤掉前面输入的空格符，后面亦同此原因
printf("input %d char for vexs \n",G.vexnum);
for(i=0; i<G.vexnum; ++i) //输入网中所有顶点
{
G.vexs[i]=getchar();
V=getchar();
}
for(i=0; i<G.vexnum; ++i) //初始化邻接矩阵
for(j=0; j<G.vexnum; ++j)
{
G.arcs[i][j].adj= 0 ;
G.arcs[i][j].info = NULL;
}
printf("input %d arc <char,char> \n", G.arcnum);
for(k=0; k<G.arcnum; k++)
{
printf("%d:\n",k);
scanf("%c,%c", &v1,&v2); //输入一条弧的两个顶点
V=getchar();
V=V;
i=LocateVex(G,v1);
j=LocateVex(G,v2);
if(i!=100 && j!=100)
{
G.arcs[j][i].adj = G.arcs[i][j].adj=1;
} //if
} //for
return 1;
}
void (* VisitFunc)(int v);
void DFSTraverse(MGraph G, void (*Visit)(int v))
{ // 对图G作深度优先遍历。
int v
VisitFunc = Visit;
for (v=0; v<G.vexnum; ++v)
visited[v] = 0; // 访问标志数组初始化
for (v=0; v<G.vexnum; ++v)
if (!visited[v]) DFS(G, v); // 对尚未访问的顶点调用DFS
}
void DFS (MGraph G, int v)
{
int w; // 从第v个顶点出发递归地深度优先遍历图G。
visited[v] = 1; VisitFunc(G,v); // 访问第v个顶点
for (w=FirstAdjVex(G, v); w!=-1; w=NextAdjVex(G, v, w) )
if (!visited[w]) DFS(G, w);
// 对v的尚未访问的邻接顶点w递归调用DFS
}
int FirstAdjVex(MGraph G, int v)
{
int k,f;
f=-1;
for (k=G.vexnum-1;k>=0;--k)
if(G.arcs[v][k].adj!=0)f=k;
return f;
}
int NextAdjVex(MGraph G, int v,int w)
{
int k,f;
f=-1;
for (k=w+1;k>=0;--k)
if(G.arcs[v][k].adj!=0)f=k;
return f;
}
main()
{
int i,Visited[1000];
MGraph G;
CreateUDG(G);
for(i=0;i<G.vexnum;i++)
{
for(int j=0;j<G.arcnum-1;j++)
{
printf("%d ",G.arcs[i][j].adj);
}
printf("\n");
}
printf("\n\n 二、深度遍历：\n");
for(i=1;i<= G.vexnum;i++)
Visited[i] = 0;
for(i = 1;i <= G.arcnum-1;i++)
if(Visited[i] == 0);
// DFS(G,i,Visited);
}
这个我做的代码。有很多错误，找不出，哪位高手帮帮小弟啊。
图的深度优先遍历序列
