数据结构 图
#include
#include
#define MaxInt 32767 //表示极大值，即∞
#define MVNum 100 //最大顶点数
#define OK 1
typedef char VerTexType; //假设顶点的数据类型为字符型
typedef int ArcType; //假设边的权值类型为整型
typedef int Status;
//矩阵
//图邻接矩阵的结构
typedef struct
{
VerTexType vexs[MVNum]; //顶点表
ArcType arcs[MVNum][MVNum]; //邻接矩阵
int vexnum,arcnum; //图的当前点数和边数
}AMGraph;
//图邻接矩阵的查找
int LocateVex(AMGraph G,VerTexType u)
{ /* 初始条件:图G存在,u和G中顶点有相同特征 */
/* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
int i;
for(i=0;i
return i;
return -1;
}
//图邻接矩阵的创建
Status CreateUDN(AMGraph &G) //采用邻接矩阵表示法，创建无向网G
{
int i,j,k,w;
char v1,v2;
printf("输入总顶点数，总边数:");
scanf("%d %d", &G.vexnum, &G.arcnum); //输入总顶点数，总边数
getchar();
for(i = 0; i
printf("输入第%d个顶点:",i+1);
scanf("%c",&G.vexs[i]);
getchar();
} //依次输入点的信息
for(i = 0; i
for(k = 0; k
printf("输入第%d条边依附的顶点及权值:",k+1);
scanf("%c %c %d",&v1,&v2,&w); //输入一条边依附的顶点及权值
getchar();
i = LocateVex(G, v1); j = LocateVex(G, v2); //确定v1和v2在G中的位置
G.arcs[i][j] = w; //边
G.arcs[j][i] = G.arcs[i][j]; //置
}
return OK;
}//CreateUDN
//图邻接矩阵的遍历
void DFS(AMGraph G, int v,int *visited) //图G为邻接矩阵类型
{
int w;
printf("%c %d\n",G.vexs[v],v); visited[v] = 1; //访问第v个顶点
for(w = 0;w
}
//表
//图邻接表的相关结构
typedef struct ArcNode //边结点
{
int adjvex; //该边所指向的顶点的位置
struct ArcNode* nextarc; //指向下一条边的指针
int inf
o; //权重
}ArcNode;
typedef struct VNode //顶点信息
{
VerTexType data; //字符信息
ArcNode* firstarc; //指向第一条依附该顶点的边的指针
}VNode, AdjList[MVNum]; //AdjList表示邻接表类型
typedef struct //邻接表
{
AdjList vertices;
int vexnum, arcnum; //图的当前顶点数和边数
}ALGraph;
//图邻接表的查找
int LocateVex2(ALGraph G,VerTexType u)
{ /* 初始条件:图G存在,u和G中顶点有相同特征 */
/* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
int i;
for(i=0;i
return i;
return -1;
}
//图邻接表的创建
Status CreateUDG(ALGraph &G)//采用邻接表表示法，创建无向图G
{
int i,k,j,w;
char v1,v2;
ArcNode* p1;
ArcNode* p2;
printf("输入总顶点数，总边数:");
scanf("%d %d", &G.vexnum, &G.arcnum); //输入总顶点数，总边数
getchar();
for(i = 0; i
printf("输入第%d个顶点:",i+1);
scanf("%c",&G.vertices[i].data); //输入顶点值
G.vertices[i].firstarc=NULL; //初始化表头结点的指针域为NULL
getchar();
}//for
for(k = 0; k
printf("输入第%d条边依附的顶点及权值:",k+1);
scanf("%c %c %d", &v1,&v2,&w); //输入一条边依附的两个顶点
getchar();
i = LocateVex2(G, v1); j = LocateVex2(G, v2);
p1=(ArcNode*)malloc(sizeof(ArcNode)); //生成一个新的边结点*p1
p1->adjvex=j; //邻接点序号为j
p1->info=w;
p1->nextarc= G.vertices[i].firstarc; G.vertices[i].firstarc=p1; //将新结点*p1插入顶点vi的边表头部
p2=(ArcNode*)malloc(sizeof(ArcNode)); //生成另一个对称的新的边结点*p2
p2->adjvex=i; //邻接点序号为i
p2->info=w;
p2->nextarc= G.vertices[j].firstarc; G.vertices[j].firstarc=p2; //将新结点*p2插入顶点vj的边表头部
}//for
return OK;
}//CreateUDG
//图邻接表的遍历
void DFS2(ALGraph G, int v,int *visited) //图G为邻接表类型
{
int w;
ArcNode* p;
printf("%c %d\n",G.vertices[v].data,v); visited[v] = 1; //访问第v个顶点
p=G.vertices[v].firstarc; //p指向v的边链表的第一个边结点
while(p!=NULL)
//边结点非空
{
w=p->adjvex; //表示w是v的邻接点
if(!visited[w]) DFS2(G, w,visited); //如果w未访问，则递归调用DFS
p=p->nextarc; //p指向下一个边结点
}
}
//主函数
void main()
{
printf("关于邻接矩阵的操作\n\n");
AMGraph G;
CreateUDN(G);
int visited[MVNum];
for(int i=0;i
printf("遍历结果为：\n");
DFS(G,0,visited);
printf("\n\n\n");
printf("关于邻接表的操作\n\n");
ALGraph E;
CreateUDG(E);
for(i=0;i
printf("遍历结果为：\n");
DFS2(E,0,visited);
}