# 資料結構(0509)程式碼

**graph_1.c**

graph G {
    rankdir = LR;
    1 -- 2;
    1 -- 3;
    2 -- 3;
    2 -- 4;
    3 -- 5;
    4 -- 5; 
}

#include <stdio.h>
#define V 5
#define E 12
typedef struct node_to_node {
	int src;
	int dest;
} Edge;
void show_graph();
int A[V][V] = {0};

int main() {
	Edge edges[] = {{1,2},{1,3},{2,1},{2,3},{2,4},{3,1},
        {3,2},{3,5},{4,2},{4,5},{5,3},{5,4}};
	int i;
	for (i = 0; i < E ; i++) {
		A[edges[i].src - 1][edges[i].dest - 1] = 1;
	}
	show_graph();
	return 0;
}

void show_graph() {
	int i, j;
	for (i = 0; i < V; i++) {
		for (j = 0; j < V; j++) {
			printf("%2d", A[i][j]);
		}
		printf("\n");
	}
}

**is_path.c**

#include <stdio.h>
#define FALSE 0
#define TRUE 1
#define NODES 7
#define EDGES 9
int edge_list[EDGES][2]= {{0,1},{0,2},{1,3},{1,4},{2,1},{3,6},{4,6},{5,1},{5,6}};
int adjmat[NODES][NODES];
void make_adjmat(void);
int is_path(int va, int vb);

int main() {
	int src, dst;
	for (dst=0; dst<NODES; dst++) {
		printf("%4d", dst);
	}
	printf("\n");

	for (src=0; src<NODES; src++) {
		printf("%d: ", src);
		for (dst=0; dst<NODES; dst++) {
			make_adjmat();
			if (is_path(src,dst))
				printf("Yes ");
			else
				printf("No  ");
		}
		printf("\n");
	}
	return 0;
}

void make_adjmat() {
	int k;
	for (k=0; k<EDGES; k++)
		adjmat[edge_list[k][0]][edge_list[k][1]]=TRUE;
}

int is_path(int va, int vb) {
	int k, found;
	if (adjmat[va][vb]>0)
		return TRUE;
	found=FALSE;
	k=0;
	while ((k<NODES) && !found) {
		if (adjmat[va][k]>0) {
			adjmat[va][k]*=-1;
			found=is_path(k,vb);
			if (!found)
				adjmat[va][k]*=-1;
		}
		k++;
	}
	return found;
}

digraph G {
    rankdir = LR;
    0 -> 1;
    0 -> 2;
    1 -> 2;
    2 -> 0;
    2 -> 3;
    3 -> 3; 
}

**GraphBFS.cpp**

#include<iostream>
#include <list>
using namespace std;

class Graph {
		int V;
		list<int> *adj;
	public:
		Graph(int V);
		void addEdge(int v, int w);
		void BFS(int s);
};

Graph::Graph(int V) {
	this->V = V;
	adj = new list<int>[V];
}

void Graph::addEdge(int v, int w) {
	adj[v].push_back(w);
}

void Graph::BFS(int s) {
	bool *visited = new bool[V];
	for(int i = 0; i < V; i++)
		visited[i] = false;

	list<int> queue;

	visited[s] = true;
	queue.push_back(s);

	list<int>::iterator i;

	while(!queue.empty()) {
		s = queue.front();
		cout << s << " ";
		queue.pop_front();

		for (i = adj[s].begin(); i != adj[s].end(); ++i) {
			if (!visited[*i]) {
				visited[*i] = true;
				queue.push_back(*i);
			}
		}
	}
}

int main() {
	Graph g(4);
	g.addEdge(0, 1);
	g.addEdge(0, 2);
	g.addEdge(1, 2);
	g.addEdge(2, 0);
	g.addEdge(2, 3);
	g.addEdge(3, 3);

	cout << "Following is Breadth First Traversal "
	     << "(starting from vertex 2) \n";
	g.BFS(2);

	return 0;
}

**GraphDFS.cpp**

#include <bits/stdc++.h>
using namespace std;

class Graph {
	public:
		map<int, bool> visited;
		map<int, list<int> > adj;
		void addEdge(int v, int w);
		void DFS(int v);
};

void Graph::addEdge(int v, int w) {
	adj[v].push_back(w);
}

void Graph::DFS(int v) {
	visited[v] = true;
	cout << v << " ";
	list<int>::iterator i;
	for (i = adj[v].begin(); i != adj[v].end(); ++i)
		if (!visited[*i])
			DFS(*i);
}

int main() {
	Graph g;
	g.addEdge(0, 1);
	g.addEdge(0, 2);
	g.addEdge(1, 2);
	g.addEdge(2, 0);
	g.addEdge(2, 3);
	g.addEdge(3, 3);

	cout << "Following is Depth First Traversal "
	     << "(starting from vertex 2) \n";
	g.DFS(2);

	return 0;
}