悬赏100分解答3
已知一无向图G的邻接距阵如下,画出该图,并写出从第一个顶点开始深度优先得到的序列(序号从小到大排列)
0 1 0 1 0
1 0 1 1 0
G = 0 1 0 0 1
1 1 0 0 1
0 0 1 1 0

[解决办法]
1---
| |
2--4
| |
3 |
| |
5---

深度优先 1,2,3,5,4


[解决办法]
#define MAX ...
#define MAXVERTEX ...
#define ...

typedef struct {
...
}VRType
typedef struct {
int serial;
}InfoType;
typedef struct ArcCell{
VRType adj;
InfoType *info;

}ArcCell,AdjMatrix[MAXVERTEX][MAXVERTEX];

typedef struct {
VertexTypr vex[MAXVERTEX];
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph;


bool visited[MAX];
int visitseq[MAX];
void (*vf)(int v);
void FirstAdjvex(MGraph G,int v);
void NextAdjvex(MGraph G,int v,int w);
void DFS(MGraph G,int v)
{
static int i=0;
visited[v]=TRUE;
vf(v);
visitseq[i++]=G.arcs.info.serial;
for(int w=FirstAdjvex(G,v);w> =0;w=NextAdjvex(G,v,w))
if(!visited[w])DFS(G,w);
}
[解决办法]
刚学java不久，下面按着数据结构(C语言版)实现如下：
/**
* Depth first tranversing the graph
* @author zzuddy
* @date 03/23/2007
* @http://community.csdn.net/Expert/topic/5415/5415080.xml?temp=.2003595
*/
import java.util.*;
public class DFSTraverseGraph{
static int AdjMarix[][]={
{0 ,1, 0, 1, 0},
{1 ,0, 1, 1, 0},
{0 ,1, 0, 0, 1},
{1 ,1, 0, 0, 1},
{0 ,0, 1, 1, 0}
};
static boolean visited[] = new boolean[5];
public static void main(String [] args){
//traversing the graph
for(int v=0;v <5;v++)
visited[v]=false;
for(int v=0;v <5;v++){
if(!visited[v])
DFS(v);
}

}
public static void DFS(int vertex){
visited[vertex]=true;
//the visiting Function,here justing print the current vertex
System.out.println( "Tranversing:V "+vertex+ "( "+(vertex+1)+ ") ");
List <Integer> adjVertexs = adjList(vertex);
ListIterator <Integer> iter= adjVertexs.listIterator();
while(iter.hasNext()){
int nextAdjVertex = iter.next();
if(!visited[nextAdjVertex])
DFS(nextAdjVertex);

}

}
public static List <Integer> adjList(int vertex){
List <Integer> adjVertexs = new ArrayList <Integer> ();
//bad code
for(int i=0;i <5;i++){
int temp = AdjMarix[vertex][i];
if(temp==1){
adjVertexs.add(i);
}
}
return adjVertexs;
}
}
[解决办法]
1---2
| / |
4 3
\ /
5

有几种情况:1-> 2-> 3-> 5-> 4; 1-> 2-> 4-> 5-> 3; 1-> 4-> 5-> 3-> 2
1-> 4-> 2-> 3-> 5 看你执行的时候是那一条,当然了,每次试验也就只有一种情况啦