消息关闭
    暂无新消息!






#include"stdio.h"
#include"stdlib.h"
#include"iostream"
using namespace std;
#define MAXN 100
int ans;
bool visit[10001];
typedef struct node{
int adjvex;
node *next;
}edgenode;

typedef struct {
char vertex;
edgenode *firstedge;
}vertexnode;

typedef vertexnode Adjlist[100];

typedef struct {
    Adjlist adjlist;
    int n,e;
}algraph;

void create (algraph *g)
{
int i,j,k,w,v;
edgenode *s;
printf("输入顶点数和边数");
scanf("%d,%d",&g->n,&g->e);

for (i=0;i<g->n;i++)
{
fflush(stdin);
printf("建立顶点表");
g->adjlist[i].vertex=getchar();
g->adjlist[i].firstedge=0;
 
}
printf("建立边表\n");
for (k=0;k<g->e;k++)
{

printf("读入v1,v2的顶点对序号");
scanf("%d,%d",&w,&v);
s=(edgenode*)malloc(sizeof(edgenode));
s->adjvex=w;
s->next=g->adjlist[v].firstedge;
g->adjlist[v].firstedge=s;
s=(edgenode*)malloc(sizeof(edgenode));
s->adjvex=v;
s->next=g->adjlist[w].firstedge;
g->adjlist[w].firstedge=s;
 
}
}

void create (algraph *);
void dfstraverse(algraph *g);
void dfs(algraph *g,int x);
int main (void)
{
algraph *g=(algraph*)malloc(sizeof(algraph));
create(g);
for (int i=0;i<g->n;i++)
{
printf("%d->",i);
while (g->adjlist[i].firstedge!=0)
{
printf("%d->",g->adjlist[i].firstedge->adjvex);
g->adjlist[i].firstedge=g->adjlist[i].firstedge->next;

}
puts("");
}
dfstraverse(g);
cout<<ans;
}
 

 void dfstraverse(algraph *g)
 {
   for (int i=0;i<g->n;i++) visit[i]=0;
    for (int j=0;j<g->n;j++)
      {
    if (visit[j]==0){
     dfs(g,j);
 ans++;} 
      }
 }
 void dfs(algraph *g,int x)
 {  cout<<"访问的顶点"<<x<<endl; 
  edgenode *s;
  visit[x]=1;
  s=g->adjlist[x].firstedge;
  while (s)
   {
    if (!visit[s->adjvex]) dfs (g,s->adjvex);
    s=s->next;
   }
 }

结果:

输入顶点数和边数4,2
建立顶点表0
建立顶点表1
建立顶点表2
建立顶点表3
建立边表
读入v1,v2的顶点对序号0,2
读入v1,v2的顶点对序号2,3
0->2->
1->
2->3->0->
3->2->
访问的顶点0
访问的顶点1
访问的顶点2
访问的顶点3
4
--------------------------------
Process exited with return value 0
Press any key to continue . . .5

1个回答

︿ 2
/*
楼主的问题,我在代码注释中说明了,下面的代码解决了你的问题,用你的测试数据,本次VS2005测试ok
*/



#include"stdio.h"
#include"stdlib.h"
#include"iostream"
using namespace std;
#define MAXN 100
int ans;
bool visit[10001];
typedef struct node {
int adjvex;
node *next;
}edgenode;

typedef struct {
int vertex;
edgenode *firstedge;
}vertexnode;

typedef vertexnode Adjlist[100];

typedef struct {
Adjlist adjlist;
int n, e;
}algraph;

void create(algraph *g)
{
int i, j, k, w, v;
edgenode *s;
printf("输入顶点数和边数");
scanf("%d,%d", &g->n, &g->e);

for (i = 0; i<g->n; i++)
{
fflush(stdin);
printf("建立顶点表");
//原来的vertex是char型,我把它改为int型,主要是输入char型,换行空格影响输入node的循环次数,
//如果是char型,按照你的4,2输入,实际上只执行2此循环初始化node,
scanf("%d",&g->adjlist[i].vertex);
//g->adjlist[i].vertex = getchar();
g->adjlist[i].firstedge = 0;

}
printf("建立边表\n");
for (k = 0; k<g->e; k++)
{

printf("读入v1,v2的顶点对序号");
scanf("%d,%d", &w, &v);
s = (edgenode*)malloc(sizeof(edgenode));
s->adjvex = w;
s->next = g->adjlist[v].firstedge;
g->adjlist[v].firstedge = s;
s = (edgenode*)malloc(sizeof(edgenode));
s->adjvex = v;
s->next = g->adjlist[w].firstedge;
g->adjlist[w].firstedge = s;

}
}

void create(algraph *);
void dfstraverse(algraph *g);
void dfs(algraph *g, int x);
int main(void)
{
algraph *g = (algraph*)malloc(sizeof(algraph));
create(g);
/***************************************************
问题处在我注释的这段代码,执行这段代码后,g->adjlist[i].firstedge就=0了,相当于没有邻接节点了,
所以就出现你说的问题了

******************************************************/
/*
for (int i = 0; i<g->n; i++)
{
printf("%d->", i);
while (g->adjlist[i].firstedge != 0)
{
printf("%d->", g->adjlist[i].firstedge->adjvex);
g->adjlist[i].firstedge = g->adjlist[i].firstedge->next;

}
puts("");
}
*/
dfstraverse(g);
cout << ans;
}


void dfstraverse(algraph *g)
{
for (int i = 0; i<g->n; i++) visit[i] = 0;
for (int j = 0; j<g->n; j++)
{
if (visit[j] == 0) {
dfs(g, j);
ans++;
}
}
}
void dfs(algraph *g, int x)
{
cout << "访问的顶点" << x << endl;
edgenode *s;
visit[x] = 1;
s = g->adjlist[x].firstedge;
while (s)
{
if (!visit[s->adjvex]) dfs(g, s->adjvex);
s = s->next;
}
}