1 /* DATE:2006-12-10 BY:snowhill */
2 /* 有向图的邻接表 表示 */
3
4 #include <iostream.h>
5 #include <stdlib.h>
6 typedef int VertexType ; //顶点数据类型
7 #define MAX_VERTEX_NUM 20 //最大顶点数
8 #define MAX_EDGE_NUM 40 //最大边数
9 int visited[MAX_VERTEX_NUM]; //访问标志数组
10
11 /*结点类型*/
12 struct ArcNode
13 {
14 int adjvex; //该弧所在的顶点位置
15 ArcNode *nextarc; //指向下一条弧
16 };
17 /* 表头结点定义*/
18 struct VNode
19 {
20 VertexType data; //顶点信息
21 ArcNode *firstarc; //指向第一条弧
22 };
23 typedef VNode AdjList[MAX_VERTEX_NUM];
24
25 /*图定义*/
26 struct ALGraph
27 {
28 AdjList vertices;
29 int vexnum,arcnum;
30 };
31 ALGraph G;
32
33 void CreateDG(ALGraph &G)
34 {
35 int i,j,k;
36 ArcNode *p;
37 cout<<"创建一个有向图:"<<endl;
38 cout<<"顶点数:"; cin>>G.vexnum; cout<<endl;
39 cout<<"边数:"; cin>>G.arcnum; cout<<endl;
40 /* 初始化 */
41 for(i=1;i<=G.vexnum;i++)
42 {
43 G.vertices[i].data=i;
44 G.vertices[i].firstarc=NULL;
45 }
46
47 for(k=1;k<=G.arcnum;k++)
48 {
49 cout<<"请输入第"<<k+1<<"条边:";
50 cin>>i>>j;
51 p=new ArcNode;
52 p->adjvex=j;
53 p->nextarc=G.vertices[i].firstarc;
54 G.vertices[i].firstarc=p;
55 }
56 }
57
58 void Disp(ALGraph G)
59 {
60 int i;
61 ArcNode *p;
62 cout<<"输出图为:"<<endl;
63 for(i=1;i<=G.vexnum;i++)
64 {
65 p=G.vertices[i].firstarc;
66 while(p!=NULL)
67 {
68 cout<<"("<<i<<","<<p->adjvex<<")";
69 p=p->nextarc;
70 }
71 cout<<endl;
72 }
73 cout<<"*******************************"<<endl;
74 }
75
76 void dfs(int v) //深度优先遍历
77 {
78 ArcNode *p=new ArcNode;
79 cout<<G.vertices[v].data<<"＊＊";
80 visited[v]=1;
81 p=G.vertices[v].firstarc;
82 while(p!=NULL)
83 {
84 if(!visited[p->adjvex])
85 dfs(p->adjvex);
86 p=p->nextarc;
87 }
88 }
89
90 void main()
91 {
92
93 int visited[20];
94 int v;
95 cout<<"/*"<<"G="<<&G<<"*/"<<endl;
96 CreateDG(G);
97 Disp(G);
98 for(int i=1;i<G.vexnum;i++)
99 visited[i]=0;
100 cout<<"请输入深度优先搜索的顶点:";
101 cin>>v;cout<<endl;
102 cout<<"深度优先序列:";
103 dfs(v);
104 cout<<endl;
105 }