邻接图的优点就是，现用现申请，空间存储很灵活，并且需要的空间也很小。我们在做复杂网络时，通常也是用这种方法。缺点是不适合并行化，因为cuda只支持连续地址空间的拷贝。
数据结构
主要包括，边节点和顶点节点
typedef struct edgeNode{ int num; int weight; struct edgeNode * next; }edgeNode; typedef struct vertexNode{ char data; edgeNode * firstNode; }vertexNode,List[NUM]; typedef struct Graph{ List list; int numver,numedges; }Graph;
深度优先遍历
与矩阵图类似
void DFS(Graph *g,int i){ edgeNode *p = (edgeNode *)malloc(sizeof(edgeNode)); visited[i] = 1; printf("%c ",g->list[i].data); p = g->list[i].firstNode; while(p){ if(!visited[p->num]) DFS(g,p->num); p = p->next; } } void DFSTraverse(Graph *g){ int i; for(i=0;i<g->numver;i++) visited[i] = 0; for(i=0;i<g->numver;i++) if(!visited[i]) DFS(g,i); }
广度优先遍历
void BFSTraverse(Graph *g){ int i; edgeNode *p; Queue *q = (Queue *)malloc(sizeof(Queue)); for(i=0;i<g->numver;i++) visited[i] = 0; initQueue(q,0); for(i=0;i<g->numver;i++){ if(!visited[i]){ visited[i] = 1; printf("%c ",g->list[i].data); inQueue(q,i); while(getLength(q)){ int *tar = (int *)malloc(sizeof(int)); outQueue(q,tar); p = g->list[*tar].firstNode; while(p){ if(!visited[p->num]){ visited[p->num] = 1; printf("%c ",g->list[p->num].data); inQueue(q,p->num); } p = p->next; } } } } }
示例图
示例代码
1 #include <stdio.h> 2 #include <stdlib.h> 3 #define NUM 5 4 #define MAXSIZE NUM 5 6 typedef struct edgeNode{ 7 int num; 8 int weight; 9 struct edgeNode * next; 10 }edgeNode; 11 12 typedef struct vertexNode{ 13 char data; 14 edgeNode * firstNode; 15 }vertexNode,List[NUM]; 16 17 typedef struct Graph{ 18 List list; 19 int numver,numedges; 20 }Graph; 21 22 typedef struct Queue{ 23 int data[NUM]; 24 int front; 25 int rear; 26 }Queue; 27 28 void initQueue(Queue *q,int n); 29 void showQueue(Queue *q); 30 int getLength(Queue *q); 31 int inQueue(Queue *q,int num); 32 int outQueue(Queue *q,int *tar); 33 34 void createGraph(Graph *g); 35 void showGraph(Graph *g); 36 void add(Graph *g,int a,int b,int c); 37 void DFS(Graph *g,int i); 38 void DFSTraverse(Graph *g); 39 void BFSTraverse(Graph *g); 40 41 int visited[NUM]; 42 43 int main() 44 { 45 Graph * g = (Graph *)malloc(sizeof(Graph)); 46 createGraph(g); 47 showGraph(g); 48 printf("\n"); 49 DFSTraverse(g); 50 printf("\n"); 51 BFSTraverse(g); 52 return 0; 53 } 54 void add(Graph *g,int a,int b,int c){ 55 edgeNode *e; 56 57 e = (edgeNode *)malloc(sizeof(edgeNode)); 58 e->next = g->list[a].firstNode; 59 g->list[a].firstNode = e; 60 e->num = b; 61 e->weight = c; 62 63 e = (edgeNode *)malloc(sizeof(edgeNode)); 64 e->next = g->list[b].firstNode; 65 g->list[b].firstNode = e; 66 e->num = a; 67 e->weight = c; 68 69 g->numedges++; 70 71 72 } 73 74 void createGraph(Graph *g){ 75 int i; 76 for(i=0;i<NUM;i++){ 77 g->list[i].data = 65+i; 78 g->list[i].firstNode = NULL; 79 } 80 g->numver = NUM; 81 g->numedges = 0; 82 //添加顶点0的边 83 add(g,0,1,0); 84 add(g,0,2,0); 85 add(g,0,3,0); 86 add(g,0,4,0); 87 88 add(g,1,3,0); 89 add(g,1,4,0); 90 91 add(g,2,4,0); 92 93 add(g,3,4,0); 94 } 95 void showGraph(Graph *g){ 96 int i; 97 for(i=0;i<g->numver;i++){ 98 printf("g[%d] ",i); 99 edgeNode *p = (edgeNode *)malloc(sizeof(edgeNode)); 100 p = g->list[i].firstNode; 101 while(p){ 102 printf("->%d(%d)",p->num,p->weight); 103 p = p->next; 104 } 105 printf("->null\n"); 106 } 107 } 108 109 void DFS(Graph *g,int i){ 110 edgeNode *p = (edgeNode *)malloc(sizeof(edgeNode)); 111 visited[i] = 1; 112 printf("%c ",g->list[i].data); 113 p = g->list[i].firstNode; 114 while(p){ 115 if(!visited[p->num]) 116 DFS(g,p->num); 117 p = p->next; 118 } 119 } 120 void DFSTraverse(Graph *g){ 121 int i; 122 for(i=0;i<g->numver;i++) 123 visited[i] = 0; 124 for(i=0;i<g->numver;i++) 125 if(!visited[i]) 126 DFS(g,i); 127 } 128 void BFSTraverse(Graph *g){ 129 int i; 130 edgeNode *p; 131 Queue *q = (Queue *)malloc(sizeof(Queue)); 132 133 for(i=0;i<g->numver;i++) 134 visited[i] = 0; 135 initQueue(q,0); 136 for(i=0;i<g->numver;i++){ 137 if(!visited[i]){ 138 visited[i] = 1; 139 printf("%c ",g->list[i].data); 140 inQueue(q,i); 141 while(getLength(q)){ 142 int *tar = (int *)malloc(sizeof(int)); 143 outQueue(q,tar); 144 p = g->list[*tar].firstNode; 145 while(p){ 146 if(!visited[p->num]){ 147 visited[p->num] = 1; 148 printf("%c ",g->list[p->num].data); 149 inQueue(q,p->num); 150 } 151 p = p->next; 152 } 153 154 } 155 } 156 } 157 158 } 159 160 void initQueue(Queue *q,int n){ 161 int i; 162 q->front=0; 163 q->rear =0; 164 for(i=0;i<n;i++){ 165 q->data[q->rear]=2*i+1; 166 q->rear++; 167 } 168 } 169 void showQueue(Queue *q){ 170 int i; 171 int len=getLength(q); 172 printf("front-"); 173 for(i=0;i<len;i++){ 174 if(q->front+i<MAXSIZE) 175 printf("%d-",q->data[q->front+i]); 176 else 177 printf("%d-",q->data[q->front+i-MAXSIZE]); 178 } 179 printf("rear\n"); 180 } 181 int getLength(Queue *q){ 182 return (q->rear-q->front+MAXSIZE)%MAXSIZE; 183 } 184 int inQueue(Queue *q,int num){ 185 if((q->rear+1)%MAXSIZE == q->front) 186 return 0; 187 q->data[q->rear] = num; 188 q->rear = (q->rear+1)%MAXSIZE; 189 return 1; 190 } 191 int outQueue(Queue *q,int *tar){ 192 if(q->front == q->rear) 193 return 0; 194 *tar = q->data[q->front]; 195 q->front = (q->front+1)%MAXSIZE; 196 return 1; 197 }