邻接矩阵
------------data.txt-----------
7 12
0 0 1 0 0 0 0
1 0 0 0 0 0 0
0 1 0 0 0 1 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 1 1 1 0
------------code.cpp----------
\#include\
\#include\
\#define Max\_vnum 50
int visited[Max\_vnum];
typedef struct {int vexnum,arcnum;int arcs[Max\_vnum][Max\_vnum];}Graph;
void InitGraph(Graph &G)
{
FILE \*fin;
int i,j;
fin=fopen("data.txt","r");
fscanf(fin,"%d%d",&G.vexnum,&G.arcnum);
for(i=1;i\<=G.vexnum;i++)
for(j=1;j\<=G.vexnum;j++)
fscanf(fin,"%d",&G.arcs[i][j]);
fclose(fin);
return ;
}
void DFS(Graph G,int v)
{
int w=0;
visited[v]=1;
printf("%dn",v);
while(w\<=G.vexnum&&!G.arcs[v][++w]);
while(w\<=G.vexnum)
{
if(!visited[w])
DFS(G,w);
while(w\<=G.vexnum&&!G.arcs[v][++w]);
}
return ;
}
void DFSTraverse(Graph G)
{
for(int v=1;v\<=G.vexnum;v++) visited[v]=0;
for(v=1;v\<=G.vexnum;v++)
{
if(!visited[v])
DFS(G,v);
}
return ;
}
int main()
{
Graph G;
InitGraph(G);
DFSTraverse(G);
return 0;
}
邻接表
----------data.txt-----------
6 9
0 1 20
0 2 16
1 4 13
1 2 15
1 5 28
5 4 12
4 3 12
2 3 14
5 3 12
---------code.cpp----------
\#include\
\#include\
\#define Max\_vnum 50
int visited[Max\_vnum];
typedef struct ArcNode{
int adjvex;
double weight;
struct ArcNode \*next;
}ArcNode,\*AdjList[Max\_vnum];
typedef struct {
AdjList vertices;
int vexnum,arcnum;
}ALGraph;
void InitGraph(ALGraph &G)
{
FILE \*fin;
int adjvex,index;
double weight;
ArcNode \*p,\*ptem[Max\_vnum];
fin=fopen("data.txt","r");
fscanf(fin,"%d%d",&G.vexnum,&G.arcnum);
for(int j=0;j\
{
G.vertices[j]=(ArcNode\*)malloc(sizeof(ArcNode));
G.vertices[j]-\>next=NULL;
ptem[j]=G.vertices[j];
}
for(int i=0;i\
{
fscanf(fin,"%d%d%lf",&adjvex,&index,&weight);
p=(ArcNode\*)malloc(sizeof(ArcNode));
p-\>adjvex=adjvex;
p-\>weight=weight;
p-\>next=NULL;
ptem[index]-\>next=p;
ptem[index]=p;
}
fclose(fin);
return ;
}
void DFS(ALGraph G,int v)
{
ArcNode \*p;
visited[v]=1;
printf("%d n",v);
p=G.vertices[v]-\>next;
while(p!=NULL)
{
if(!visited[p-\>adjvex])
{
printf("weight=%7.2lfn",p-\>weight);
DFS(G,p-\>adjvex);
}
p=p-\>next;
}
return ;
}
void DFSTraverse(ALGraph G)
{
for(int v=0;v\
for(v=0;v\
{
if(!visited[v])
DFS(G,v);
}
return ;
}
int main()
{
ALGraph G;
InitGraph(G);
DFSTraverse(G);
return 0;
}
Comments