1 solutions
-
0
C :
#include <stdio.h> #include <string.h> int isvisited[51],mat[51][51],cnt,n; void dfs(int start){ if (cnt>=n) { return ; } cnt++; isvisited[start]=1; printf("%d ",start); for (int i=0;i<n;i++) { if (!isvisited[i]&&mat[start][i]==1) { dfs(i); } } } int main(){ int i,j; // freopen("1.txt","r",stdin); while (scanf("%d",&n)==1) { for (i=0;i<n;i++) { for (j=0;j<n;j++) { scanf("%d",&mat[i][j]); } } cnt=0; memset(isvisited,0,sizeof(isvisited)); for (i=0;i<n;i++) { if (!isvisited[i]) { dfs(i); } } printf("\n"); } // fclose(stdin); return 0; }
C++ :
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <limits.h> #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define OVERFLOW -1 typedef int Status; /* 函数结果状态代码,如OK等 */ #define INFINITY INT_MAX /* 用整型最大值代替∞ */ #define MAX_VERTEX_NUM 50 /* 最大顶点个数 */ typedef int VRType; typedef char InfoType; typedef int VertexType; typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */ typedef struct { VRType adj; /* 顶点关系类型。对无权图,用1(是)或0(否)表示相邻否; */ /* 对带权图,c则为权值类型 */ InfoType *info; /* 该弧相关信息的指针(可无) */ }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { VertexType vexs[MAX_VERTEX_NUM]; /* 顶点向量 */ AdjMatrix arcs; /* 邻接矩阵 */ int vexnum,arcnum; /* 图的当前顶点数和弧数 */ GraphKind kind; /* 图的种类标志 */ }MGraph; Status CreateUDG(MGraph *G) { /* 采用数组(邻接矩阵)表示法,由文件构造没有相关信息的无向图G */ int i,j; scanf("%d",&(*G).vexnum); for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */ (*G).vexs[i] = i; for(i=0;i<(*G).vexnum;++i) /* 初始化邻接矩阵 */ for(j=0;j<(*G).vexnum;++j) { scanf("%d",&(*G).arcs[i][j].adj); /* 图 */ (*G).arcs[i][j].info=NULL; /* 没有相关信息 */ } (*G).kind=AG; return OK; } int LocateVex(MGraph G,VertexType u) { /* 初始条件:图G存在,u和G中顶点有相同特征 */ /* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */ int i; for(i=0;i<G.vexnum;++i) if(u == G.vexs[i]) return i; return -1; } VertexType* GetVex(MGraph G,int v) { /* 初始条件: 图G存在,v是G中某个顶点的序号。操作结果: 返回v的值 */ if(v>=G.vexnum||v<0) exit(ERROR); return &G.vexs[v]; } int FirstAdjVex(MGraph G,VertexType v) { /* 初始条件: 图G存在,v是G中某个顶点 */ /* 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1 */ int i,j=0,k; k=LocateVex(G,v); /* k为顶点v在图G中的序号 */ if(G.kind==DN||G.kind==AN) /* 网 */ j=INFINITY; for(i=0;i<G.vexnum;i++) if(G.arcs[k][i].adj!=j) return i; return -1; } int NextAdjVex(MGraph G,VertexType v,VertexType w) { /* 初始条件: 图G存在,v是G中某个顶点,w是v的邻接顶点 */ /* 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号, */ /* 若w是v的最后一个邻接顶点,则返回-1 */ int i,j=0,k1,k2; k1=LocateVex(G,v); /* k1为顶点v在图G中的序号 */ k2=LocateVex(G,w); /* k2为顶点w在图G中的序号 */ if(G.kind==DN||G.kind==AN) /* 网 */ j=INFINITY; for(i=k2+1;i<G.vexnum;i++) if(G.arcs[k1][i].adj!=j) return i; return -1; } bool visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */ Status(*VisitFunc)(VertexType); /* 函数变量 */ void DFS(MGraph G,int v) { /* 从第v个顶点出发递归地深度优先遍历图G。算法7.5 */ VertexType w1,v1; int w; visited[v]=TRUE; /* 设置访问标志为TRUE(已访问) */ VisitFunc(G.vexs[v]); /* 访问第v个顶点 */ v1 = *GetVex(G,v); for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,w1 = *GetVex(G,w))) if(!visited[w]) DFS(G,w); /* 对v的尚未访问的序号为w的邻接顶点递归调用DFS */ } void DFSTraverse(MGraph G,Status(*Visit)(VertexType)) { /* 初始条件: 图G存在,Visit是顶点的应用函数。算法7.4 */ /* 操作结果: 从第1个顶点起,深度优先遍历图G,并对每个顶点调用函数Visit */ /* 一次且仅一次。一旦Visit()失败,则操作失败 */ int v; VisitFunc=Visit; /* 使用全局变量VisitFunc,使DFS不必设函数指针参数 */ for(v=0;v<G.vexnum;v++) visited[v]=FALSE; /* 访问标志数组初始化(未被访问) */ for(v=0;v<G.vexnum;v++) if(!visited[v]) DFS(G,v); /* 对尚未访问的顶点调用DFS */ printf("\n"); } Status visit(VertexType i) { printf("%d ",i); return OK; } int main() { int i,j,k,n; MGraph g; CreateUDG(&g); DFSTraverse(g,visit); return 0; }
Pascal :
program DFS; var v:array[0..100]of boolean; a:array[0..100,0..100]of integer; b:array[0..100]of integer; i,r,j,k,n:integer; procedure dfs(i:integer); var j:integer; begin v[i]:=true; b[k]:=i;inc(k); for j:=1 to n-1 do begin if (not v[j])and(a[i,j]=1)then dfs(j); end; end; {*******main*********} begin readln(n); fillchar(v,sizeof(v),false); for i:=0 to n-1 do for j:=0 to n-1 do begin read(a[i,j]); end; k:=0; for i:=0 to n-1 do if not v[i] then dfs(i); for i:=0 to n-1 do begin write(b[i],' '); end; writeln; end.
Java :
import java.util.Scanner; public class Main { private static Scanner s = new Scanner(System.in) ; public static void main(String[] args) { int n = s.nextInt() ; int a[][] = new int[n][n] ; boolean visited[] = new boolean[n] ; for (int i = 0; i < a.length; i++) { for (int j = 0; j < a.length; j++) { a[i][j] = s.nextInt() ; } } for (int i = 0; i < visited.length; i++) { a[i][i] = 1 ; } Graph g = init(a ,visited) ; deptSearch(g, 0) ; System.out.println() ; } public static Graph init(int a[][] , boolean visited[]){ Graph g = new Graph(a.length) ; g.visited = visited ; g.a = a ; return g ; } public static void deptSearch(Graph g,int x){ for (int i = 0; i < g.n; i++) { if(g.a[x][i] ==1&&g.visited[i]==false){ g.visited[i] = true ; visit(i) ; deptSearch(g, i) ; } } } public static void visit(int i){ System.out.print(i+" "); } } class Graph{ int n ; int a[][] = new int [n][n] ; boolean visited[] = new boolean[n] ; public Graph(int n) { this.n = n ; } }
- 1
Information
- ID
- 571
- Time
- 1000ms
- Memory
- 32MiB
- Difficulty
- (None)
- Tags
- # Submissions
- 0
- Accepted
- 0
- Uploaded By