有向图的邻接表的建立,深度遍历并输出(c语言实现有向网)
有向图的邻接表的建立,深度遍历并输出(c语言实现有向网)
- [ ]为方便理解。 首先先为图的邻接表画一个模型,
- 邻接表可以分为两部分(1.表头节点,2.弧节点)
- 如上图,因为写的代码是有向网,所以选择上图,首先在脑海里建立一个模型
- 代码如下
#include<stdio.h>
#include<stdlib.h>
int visited[20]; //顶点的访问标志
//*邻接表用两部分表示 1顶点节点包含(data firstarc) 2弧节点包含(adjvex, *next weigh)
typedef enum {DG/*有向图*/,DN/*有向网*/,UDG/*无向图*/,UDN/*无向网*/} GraphKind;
typedef struct ArcNode{
int adjvex;//该弧指向顶点的位置
struct ArcNode *next;//指向下一条弧的指针
int weigh;//弧的权值
}ArcNode;
typedef struct vertexNode{
int data;//顶点数据
ArcNode * firstarc;//指向该顶点第一条弧的指针
}vertexNode;
typedef struct{
vertexNode vertex[20];
int vexnum;
int arcnum;//图的顶点数量和弧的数量
//GraphKind kind;//图的种类
} AdjList;
int creat(AdjList *a)
{
int i,j,n;
int sum;//sum和arcnum一样代表图中总的弧数
ArcNode *p1,*p2,c;
printf("请输入图顶点的总个数和弧的总个数\n");
scanf("%d %d",&a->vexnum,&a->arcnum);
sum=a->arcnum;
for(i=0;i<a->vexnum;i++)
a->vertex[i].firstarc=NULL;//初始化和顶点第一个相邻的弧为空;
for(i=0;i<a->vexnum;i++)
{
printf("***请输入第%d个顶点的值***\n",i);
scanf("%d",&a->vertex[i].data);
if(sum==0) continue;
printf("请输入和本顶点相关弧的个数\n");
scanf("%d",&n);
for(j=0;j<n;j++)
{
if(j==0)
{
int q;
p1=p2=( ArcNode*)malloc(sizeof(ArcNode));
//p1=p2=&c;
p1->next=p2->next=NULL;
a->vertex[i].firstarc=p1;
printf("请输入与第%d个顶点相邻的,第%d个相邻的弧顶点(位置) 以及弧的权值\n",i,j);
scanf("%d %d",&p1->adjvex,&p1->weigh);
//printf("%d %d",p1->adjvex,p2->weigh);
sum--;
}
else{
p2=(ArcNode*)malloc(sizeof(ArcNode));
p2->next=NULL;
p1->next=p2;
printf("请输入第%d个顶点 第%d个相邻的弧顶点 以及两个顶点间弧的权值\n",i,j);
scanf("%d %d",&p2->adjvex,&p2->weigh);
sum--;
}
}
printf("**************************\n");
}
}
void print( AdjList a)//输出矩阵
{
int i,j;
for(i=0;i<a.vexnum;i++)
{
ArcNode *p;
p=a.vertex[i].firstarc;
printf(" [%d]",a.vertex[i].data);
while(p)
{
printf("----->");
printf("[%d %d]",p->adjvex,p->weigh);
p=p->next;
}
printf("\n");
}
}
void traverseGraph( AdjList a){//深度优先遍历图
int i,j;
for(i=0;i<a.vexnum;i++)
visited[i]=0;//标志全部顶点为访问
for(i=0;i<a.vexnum;i++)
{
if(!visited[i])
DepthFirstSearch(a,i);
}
}
int DepthFirstSearch(AdjList a,int i){
ArcNode *p;
printf(" %d",a.vertex[i].data);
visited[i]=1;
p=a.vertex[i].firstarc;
while(p)
{
if(!visited[p->adjvex])
DepthFirstSearch(a,p->adjvex);
p=p->next;
}
}
int main()
{ AdjList a;
creat(&a);
print(a);//邻接表形式输出图
printf("***深度遍历图***\n");
traverseGraph(a); //深度优先遍历图
}
测试了下