- #include<stdio.h>
- #include<stdlib.h>
- /*邻接表的结点数据结构*/
- typedef struct ArcNode
- {
- int adjvex;
- struct ArcNode * nextArc; //指向下一结点
- } ArcNode, *AdjList;
- /*图中结点数据结构*/
- typedef struct VNode
- {
- int data; //结点的值
- AdjList firstArc; //该节点邻接表的头指针
- } VNode;
- /*图的数据结构*/
- typedef struct
- {
- VNode vertices[20]; //顶点数组
- int vexnum; //顶点个数
- } Graph;
- void createGraph(Graph &G, int n) //引用参数要以&开头,否则运行出错,原因暂时不清楚
- {
- G.vexnum = n;
- int num;
- AdjList p;
- AdjList newNode;
- int i, j;
- printf("输入每个结点的值\\n");
- for (i = 0; i < G.vexnum; i++)
- scanf("%d", &G.vertices[i].data); //输入每个节点的值
- for (i = 0; i < G.vexnum; i++)
- G.vertices[i].firstArc = NULL;
- for (i = 0; i < G.vexnum; i++)
- {
- printf("输入V%d的邻接表中结点个数 ", i);
- scanf("%d", &num);
- if (num != 0)
- {
- printf("输入这%d个结点: ", num);
- p = (AdjList) malloc(sizeof (ArcNode));
- scanf("%d", &p->adjvex); //输入邻接表中的头结点
- p->nextArc = NULL;
- G.vertices[i].firstArc = p; //将头结点信息赋给结点i
- for (j = 1; j < num; j++)
- {
- newNode = (AdjList) malloc(sizeof (ArcNode));
- scanf("%d", &newNode->adjvex); //输入邻接表中除头尾结点外的中间结点
- p->nextArc = newNode;
- newNode->nextArc = NULL;
- p = newNode;
- }
- }
- }
- }
- void DFS(Graph G, int v, char * color[20])
- {
- // printf("DFS start\\n");
- AdjList cursor;
- int w, i;
- color[v] = "gray";
- cursor = G.vertices[v].firstArc; //cursor指向V的邻接表的头节点
- while (cursor)
- {
- w = cursor->adjvex;
- if (color[w] == "white") //节点为白色,即未被访问过
- {
- color[w] = "gray"; //将节点颜色标为灰色,说明正在对该节点访问
- printf("V%d:%d\\t", w, G.vertices[w].data);
- DFS(G, w, color); //接着从节点w开始遍历
- }
- cursor = cursor->nextArc;
- }
- color[v] = "black";
- }
- void dfsSweep(Graph G,char *color[20]){
- for(int i = 0;i < 20;i++)
- color[i] = "white";
- for(int i = 0;i < G.vexnum;i++){
- if(color[i] == "white"){
- printf("V%d:%d\\t",i,G.vertices[i].data);
- DFS(G,i,color);
- }
- }
- }
- int main(){
- Graph G;
- char * color[20];
- int n;
- printf("输入图G中元素的个数: ");
- scanf("%d",&n);
- createGraph(G,n);
- printf("深度优先遍历的节点顺序为\\n");
- dfsSweep(G,color);
- }
- //该片段来自于http://www.codesnippet.cn/detail/111120137037.html
来源: http://www.codesnippet.cn/detail/111120137037.html